Что такое средняя высота журнала n?

Я узнал, что высота деревьев Random-BST/Red-Black и некоторых других деревьев равна O(log n).

Я удивляюсь, как это может быть. Допустим, у меня есть такое дерево

Двоичное дерево

Высота дерева по сути является глубиной дерева, которая в данном случае будет равна 4 (оставляя родительскую глубину). Но как люди могли сказать, что высота может быть представлена ​​понятием O(log n)?

Я очень люблю алгоритмы, и этот момент меня сильно смущает. Где я упускаю суть?


algorithm tree binary-search-tree
person sriram    schedule 09.09.2012    source источник
comment
возможный дубликат Высоты двоичного дерева   -  person Kristopher Micinski    schedule 09.09.2012
comment
@KristopherMicinski: Не может быть!   -  person sriram    schedule 09.09.2012
comment
поясните, почему нельзя? Похоже, ответ тот же, формулу можно доказать индукцией по структуре деревьев, базовый случай — лист, индуктивный случай предполагает два поддерева. Это называется полным бинарным деревом, но обычно O(log n) будет верхней границей.   -  person Kristopher Micinski    schedule 09.09.2012
comment
@KristopherMicinski: Итак, вы обычно говорите, что максимальная высота дерева может составлять n, а минимальная высота - O(log n) в случае красно-черных деревьев и других деревьев, которые самобалансируются. Я прав или что-то здесь не так?   -  person sriram    schedule 09.09.2012
comment
конечно, если у вас есть n узлов, вырожденный случай — это цепочка, которая имеет n узлов, а нижняя граница высоты (а не верхняя граница, как я уже говорил ранее, это была опечатка) — это нижняя граница. Вы можете доказать это индуктивно, используя принцип, который я только что упомянул.   -  person Kristopher Micinski    schedule 09.09.2012
comment
@KristopherMicinski: Круто. Ваши комментарии кажутся правильными. Почему нельзя поставить это как ответ?   -  person sriram    schedule 09.09.2012
comment
Проверьте Big O(h) vs. Big O(logn) в деревьях. Я попытался объяснить разницу с помощью розыгрыша двух действительных бинарных деревьев поиска - одно балансирует, а другое нет.   -  person amit    schedule 09.09.2012
comment
см. мой ответ здесь: stackoverflow .com/questions/2307283/   -  person 2cupsOfTech    schedule 27.10.2012

Ответы (2)


arrow_upward
1
arrow_downward

Как я объяснил в комментарии, бинарное дерево может иметь несколько вариантов:

  • В вырожденном случае бинарное дерево представляет собой просто цепь, а его высота равна O(n).
  • В лучшем случае (для большинства алгоритмов поиска) полное бинарное дерево обладает тем свойством, что для любого узла высота поддеревьев одинакова. В этом случае длина будет равна полу log(n) (основание 2 или основание k для k ветвей). Вы можете доказать это индукцией по размеру дерева (структурная индукция в конструкторах)
  • В общем случае у вас будет смесь из них, построенное дерево, в котором любой узел имеет подветвь с возможной разной высотой.
person Kristopher Micinski    schedule 09.09.2012
comment
Я думаю, что функция высоты действительно должна использовать floor, а не ceiling. Возьмем, к примеру, случай перехода от n=3 к n=4: если вы используете ceiling, то высота не изменится, но если вы используете floor, высота правильно изменится с 1 на 2. - person DaoWen; 09.09.2012
comment
@DaoWen ага, забыл на самом деле нарисовать и поспешно написал интуитивно :) - person Kristopher Micinski; 09.09.2012

arrow_upward
2
arrow_downward

В сложности алгоритма переменная n обычно относится к общему количеству элементов в коллекции или участвует в каком-либо вычислении. В данном случае n — это общее количество узлов в дереве. Итак, на картинке, которую вы разместили n=31. Если высота дерева равна O(log n), это означает, что высота дерева пропорциональна журналу n. Поскольку это двоичное дерево, вы должны использовать логарифмическую базу 2.

⌊log₂(31)⌋ = 4

Следовательно, высота дерева должна быть около 4, что и соответствует вашему примеру.

person DaoWen    schedule 09.09.2012
comment
это правильно, но немного вводит в заблуждение, как правило, эта формула используется только с потолком логарифма, поэтому вы всегда говорите только о целых числах, и, как я объяснил в своем комментарии, это верхняя граница, которая верна только в случае полного бинарного дерева. - person Kristopher Micinski; 09.09.2012
comment
Также обратите внимание, что разница между различными базами журналов — это просто постоянный фактор, поэтому вы не видите базу, записанную в большой нотации O. - person Laurence Gonsalves; 09.09.2012
comment
@LaurenceGonsalves в этом случае действительно имеет значение, потому что база журнала зависит от фактора ветвления. - person Kristopher Micinski; 09.09.2012
comment
@Kristopher Micinski - Спасибо за хорошее замечание - я обновил свой ответ. Однако я почти уверен, что использование здесь floor дает более четкий ответ, чем ceil. - person DaoWen; 09.09.2012
comment
Основание полезно в объяснении, но внутри большого О это не имеет значения. Увеличение коэффициента ветвления на константу просто уменьшает сбалансированную высоту на постоянный коэффициент. (Вы можете доказать это, используя законы логарифмов.) Например, переключение с коэффициента ветвления 2 на коэффициент ветвления 8 просто увеличивает высоту сбалансированного дерева на 1/3. То есть O(log_8(n)) = O(1/3 * log_2(n)), и поэтому мы могли бы полностью исключить базу: O(log(n)) - person Laurence Gonsalves; 09.09.2012
comment
@LaurenceGonsalves да, в отношении сложности это правильно, но если вам действительно нужно вычислить нижнюю границу (например, для выделения памяти или чего-то еще ..), то это будет иметь значение, я говорю, что здесь важно больше, чем большой -О сложности.. - person Kristopher Micinski; 09.09.2012