В моем классе Java мы изучаем сложность различных типов коллекций.
Вскоре мы будем обсуждать бинарные деревья, о которых я читал. Книга утверждает, что минимальная высота бинарного дерева составляет , но не дает дополнительных объяснений.
Может кто-нибудь объяснить, почему?
data-structures
binary-trees
discrete-mathematics
trees
CodyBugstein
источник
источник
Ответы:
Бинарное дерево имеет 1 или 2 дочерних элемента в неконечных узлах и 0 узлов в конечных узлах. Пусть в дереве будет узлов, и мы должны расположить их таким образом, чтобы они все еще формировали правильное двоичное дерево.n
Не доказывая, я утверждаю, что для максимизации высоты данные узлы должны быть расположены линейно, то есть каждый неконечный узел должен иметь только одного дочернего элемента:
Здесь формула для вычисления отношения высоты с точки зрения количества узлов проста. Если - высота дерева, то h = n - 1 .h h=n−1
Теперь, если мы попытаемся построить бинарное дерево из узлов с минимальной высотой (всегда сводимой к полному бинарному дереву), мы должны упаковать как можно больше узлов на верхних уровнях, прежде чем перейти к следующему уровню. Итак, дерево принимает вид следующего дерева:n
Начнем с частного случая, .n=2m−1
Мы знаем, что
Также легко доказать, что уровень, на котором могу иметь не более 2 i узлов.i 2i
Используя этот результат в приведенной выше сумме, мы находим, что для каждого уровня от 0 до m существует соответствующий член 2 i - 1 в разложении 2 m - 1 . Это означает, что полное двоичное дерево 2 m - 1 узлов полностью заполнено и имеет высоту, h ( 2 m - 1 ) = m - 1 , где h ( n ) = высота полного двоичного дерева с n узлами.я 0 м 2я - 1 2м- 1 2м- 1 ч ( 2м- 1 ) = м - 1 h ( n ) = N
источник
источник
Чтобы сохранить минимальную высоту, легко увидеть, что нам нужно заполнить все уровни, кроме, возможно, последнего. Почему? в противном случае мы могли бы просто переместить узлы последнего уровня в пустые слоты на верхних уровнях.
Теперь представьте, что у меня есть неуказанное количество бинов, и я даю вам один бин за раз и прошу вас построить двоичное дерево с минимально возможной высотой. К тому времени, как вы полностью заполнили последний уровень, или, по крайней мере, один бин на последнем уровне, может закончиться. Допустим, у вас есть высота дерева h в этой точке.
источник