Царям

The height of a node is the length of the longest downward path to a leaf from that node.

ну вот же. Черным по белому написано. Длина пути - это количество ребер в нем, если че.

не царское это дело - писать и разрабатывать программы...

Все цари в пасьянс и косынку режутся и сидят на выньХР...

И? Из этого следует, что высота листа равна нулю, не? А уточнение я сделал в предположении о том, что кто-то мог считать иначе.

В том смысле, что минимальное из тех вещественных чисел, что сопоставлены с каждым узлом

ну тогда вроде определяющим является число p. оно всегд меньше или равно сопутствующему q.

И? Из этого следует, что высота листа равна нулю, не? А уточнение я сделал, в предположении о том, что кто-то мог считать иначе.

А в итоге никто ничего не понял.

Не, прочитай самый первый пункт списка. Числа p и q — дополнительные характеристические числа, которые нужны, чтобы ограничить все множество деревьев.

Вот здесь: Царям (комментарий)

n = 3,

Высота равна 2 = n - 1. Есть n листьев. Есть n-1 «вершина» (не-лист).

Можно несколько упростить задачу и уменьшить количество деревьев, если выбросить q. Тогда число возможных вещественных значений, которые может принимать некоторое число (обозначим его за g) в узле равно n-1. Для поддеревьев n1+n2 = n. Для дерева по ссылке это выполняется.

Не, прочитай самый первый пункт списка. Числа p и q — дополнительные характеристические числа, которые нужны, чтобы ограничить все множество деревьев.

тогда собсно и деревья только для этого и нужны. У тебя же нет тогда никакой связи между числом в вершине и структурой дерева.

ищи обыкновенной сортировкой. Получишь в итоге скорость (n!)log(n!), если я нигде не ошибся.

Основной мой интерес здесь состоит в том, есть ли детерминированный алгоритм поиска, который был бы быстрее частичного перебора или сортировки.

нет тогда никакой связи между числом в вершине и структурой дерева

Получается, что есть много деревьев, у которых корневые поддеревья глубины до n-3 совпадают.

То есть для дерева (которое единственно)

     A
    / \
   B   C
      / \
     D   E

Есть еще дерево

     A
    / \
   F   G
  / \
 H   I

Короче, пойду я дальше думать над формализацией :)

Получается, что есть много деревьев, у которых корневые поддеревья глубины до n-3 совпадают.

как так? Ты же говоришь, что есть три числа в каждой вершине: одно вещественное и два других: p и q.

Совпадают с точностью до вещественных чисел. Очевидно, что p и q не совпадают при этом.

Совпадают с точностью до вещественных чисел. Очевидно, что p и q не совпадают при этом.

так какое же тогда отношение порядка между вершинами?

A <= B, если gA <= gB, где gi — вещественное число в вершине

Еще никто не написал?

И, да, очевидныый перебор со сложность O(n * кол-во деревьев) оптимален.

Тогда всё равно можно было бы упростить жизнь поиску запоминанием минимального элемента дерева непосредственно при его добавлении.

тогда анон выше прав. если высота дерева = числу внутренних узлов, а листья не содержат информации вообще, то твое дерево - односвязный список.

вангую, что если рассуждать дальше, у тебя ответ к задаче будет не алгоритм, а натуральное число (точнее, функция от p и q). колись, это не по информатике задали, а по алгебре?попробуй упростить свое ТЗ. возможно, кодить вообще не придется

это не по информатике задали, а по алгебре

Не, это по ПАХТу задали :)

В идеале я надеюсь и правда обойтись без вычислений.

Вы все анскильные лалки, задача разбивается на подзадачи, которые должны влезать в L2 кеш, иначе это днище.

Чо-то или лыжи не едут или зачем ты вообще листья приплел, если во всех плюс бесконечность, а высота дерева нам известна? Их же можно при любых раслкадах игнорировать просто считая, что деревья имеют высоту n-3 и выкинув все рассуждения про листья.

Вобщем почитал тред и понял, что никто не понял зачем у тебя там листья...

Потому что они там есть. То, что их можно отбросить — это хорошо, но изначально они там есть.

С формулировкой у тебя вообще плохо.

A <= B, если gA <= gB, где gi — вещественное число в вершине

Из этого же следует что у тебя минимум каждого дерева в корне. Разве нет?

Это отношение порядка на множестве вершин

Ну может не совсем O(n * m), сложность обхода такого дерева все таки больше, чем O(n), но не намного.

Тебе в любом случае придётся прикоснуться к каждому из деревьев, иначе есть риск, что максимум доставляет именно то дерево, к которому ты не даже прикасался.

Нужно ли для каждого дерева вычислять его минимум? Не обязательно, вычисление можно оборвать, как только станет ясно, что это дерево не вносит вклада в конечный результат.

max_value = -inf
foreach tree in trees
   min_value = +inf
   foreach leaf in tree
      min_value = minimum(min_value, get_value(leaf))
      if(min_value < max_value) break;
   max_value = maximum(max_value, min_value)

Да ничего не дополнял. Давай так, у тебя есть два множества A и B. Тебе нужно найти max{min A, min B}. Пусть, ты вычислил min A и нашел какой-то элемент b из множества B такой, что b < min A. Тогда дальше множество B ты можешь не просматривать. max{min A, min B} = min A

Не можешь, ведь тебе надо вычислить сам min A.

Не надо.

Ты в курсе, что такое минимакс (максимин)?

Не надо.

Как ты узнаешь минимум множества, не обходя все множество?

Очевидно, ответ на вопрос зависит от того, как организовано множество. Иначе так же можно спросить: «Как ты найдешь значение в множестве, не обходя все множество?», не учтя тот факт, что множество упорядочено.

Очевидно, ответ на вопрос зависит от того, как организовано множество.

в сабжевом случае оно никакой внутренней структуры не имеет. То есть, допустим, представлено неупорядоченным списком. Никакого способа гарантировать, что среди оставшихся элементов не найдется меньшего - не существует.

Нам не нужно узнавать минимум. Нам нужно узнать максимум среди минимумов.

две страницы о деревьях/списках, и ни одного лиспера/схемера в треде?

Куда катится этот мир... :)

Я лиспер, и я в треде.

две страницы о деревьях/списках, и ни одного лиспера/схемера в треде?

Сколько нужно лисперов, чтобы объяснить топикстартеру, что он некорректно составил задачу?

может, если он опишет алгоритм генерации своих «деревьев», будет более понятно?

две страницы о деревьях/списках, и ни одного лиспера/схемера в треде?

Вроде же сам ТС — клинический скобкодрочер, не?

Каждое поддерево с корнем равным корню данного дерева есть встречается как корневое поддерево еще в как минимум (n - m - 1)! деревьях.

Попробуй всё-таки внятно сформулировать, что у тебя за структура такая. Мычание на этой и предыдущей страничках на вменяемую формулировку никак не тянут. И работает поэтому только принцип GIGO.

Не можешь, ведь тебе надо вычислить сам min A.

min A надо вычислить, но вот min B уже можно и не вычислять

Я бегло читал тему и ничего не понял. ТС так и не объяснил толком, какие у него деревья. Может в субботу, если у меня будет мороз или дождь я и попытаюсь разобраться в данной теме, а пока я вижу лишь хаотичные списки, никак не связанные между собой, с непонятным и ненужным никому листом где-то посередине. Есть только бинарные деревья, а то что бинарным деревом можно обозвать любое дерево, узел которого имеет не более, чем 2 листа/подузла помочь ничем не может.

buddhist, напиши, как твое дерево правильно называется (как препод твой его назвал, иначе это непонятно-что и кроме тупого перебора (возможно с альфа-бета отсечением, если в деревьях есть какая-то минимальная логика, когда с некоторого момента ветвь можно дальше не рассматривать) вариантов нет).

как препод твой его назвал

Нет никакого препода, это практическая задача

я попробовал сгенерировать случайное не-поисковое не-отсортированное бинарное дерево

для случая, когда в дереве миллион узлов:
числа также выбираются случайно в диапазоне до миллиона
глубина у дерева получается 24
максимальная ширина - порядка 300000 узлов
тупой проход по всему дереву, он же поиск, выполняется на средней машинке за секунду

для случая, когда в дереве 10 миллионов узлов:
числа также выбираются случайно в диапазоне до 10 миллионов
глубина у дерева получается 28
максимальная ширина - уже порядка 3000000
поиск выполняется за 13 секунд

банальное не-отсортированное дерево можно сконвертировать в bst-дерево
в последнем случае, для 10 миллионов узлов, конвертация, причем в ту же форму, у меня заняла порядка 10 секунд
зато поиск максимума стал практически мгновенным