Почему минимальная высота бинарного дерева

10

В моем классе Java мы изучаем сложность различных типов коллекций.

Вскоре мы будем обсуждать бинарные деревья, о которых я читал. Книга утверждает, что минимальная высота бинарного дерева составляет , но не дает дополнительных объяснений.log2(n+1)1

Может кто-нибудь объяснить, почему?

CodyBugstein
источник
Я объясняю это здесь stackoverflow.com/a/13093274/550393
2cupsOfTech

Ответы:

11

Бинарное дерево имеет 1 или 2 дочерних элемента в неконечных узлах и 0 узлов в конечных узлах. Пусть в дереве будет узлов, и мы должны расположить их таким образом, чтобы они все еще формировали правильное двоичное дерево.n

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

                              O 1
                              |
                              O 2
                              |
                              O 3
                              |
                              O 4
                              |
                              O 5
                              |
                              O 6
                              |
                              O 7
                              |
                              O 8

Здесь формула для вычисления отношения высоты с точки зрения количества узлов проста. Если - высота дерева, то h = n - 1 .hh=n1

Теперь, если мы попытаемся построить бинарное дерево из узлов с минимальной высотой (всегда сводимой к полному бинарному дереву), мы должны упаковать как можно больше узлов на верхних уровнях, прежде чем перейти к следующему уровню. Итак, дерево принимает вид следующего дерева:n

                              O
                              |1
                              |
                       O------+-----O
                       |2           |3
                       |            |
                   O---+---O    O---+----O
                   |4      |5    6        7
                   |       |
               O---+--O    O
                8      9    10

Начнем с частного случая, .n=2m1

Мы знаем, что

20+21+22+...+2m1=2m1

Также легко доказать, что уровень, на котором могу иметь не более 2 i узлов.i2i

Используя этот результат в приведенной выше сумме, мы находим, что для каждого уровня от 0 до m существует соответствующий член 2 i - 1 в разложении 2 m - 1 . Это означает, что полное двоичное дерево 2 m - 1 узлов полностью заполнено и имеет высоту, h ( 2 m - 1 ) = m - 1 , где h ( n ) = высота полного двоичного дерева с n узлами.я0м2я-12м-12м-1час(2м-1)знак равном-1час(N)знак равноN

час(2м)знак равном2м-1(2m1)+1=2mmm1m

h(2m)=m,
h(2m+1)=m+1
h(2m+11)=m

nZ,2mn<2m+1

mh(n)<m+1

mlog2(n)<m+1
m=log2(n)

N,N[2м,2м+1)

час(N)знак равномзнак равножурнал2(N)

NZ

журнал2(N+1)-1Nжурнал2(N)N

Анураг Калия
источник
19

N

41+12+122+12223

узлызнак равно1+2+22+23+,,,+2глубиназнак равноΣКзнак равно0глубина2Кзнак равно1-2глубина+11-2,

узлызнак равно2глубина+1-1,
узлы+1знак равно2глубина+1журнал2(узлы+1)знак равножурнал2(2глубина+1)знак равноглубина+1журнал2(узлы+1)-1знак равноглубина,
MikeDan
источник
4

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

Теперь представьте, что у меня есть неуказанное количество бинов, и я даю вам один бин за раз и прошу вас построить двоичное дерево с минимально возможной высотой. К тому времени, как вы полностью заполнили последний уровень, или, по крайней мере, один бин на последнем уровне, может закончиться. Допустим, у вас есть высота дерева h в этой точке.

20+21+22+23++2часзнак равно2час+1-1N,
часзнак равноЛ.Г.(N+1)-1,
user1234
источник