Высота бинарного дерева

Question

Мне нужна общая формула для расчета минимальной высоты двоичного дерева и максимальной высоты двоичного дерева. (не двоичное дерево поиска)

Answer 1

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

Так что, может, лучше уточнить, какой вам нужен.

В дискретной математике деревья классифицируются как m-арные деревья, поэтому бинарное дерево - это 2-арное дерево. Также на любой данной высоте, может быть не более 2 ^ h = L (уходит). Это важно заметить, так как это подтверждает, что корень находится на нулевой высоте, следовательно, 2 ^ 0 = 1 лист ... 1 вершина ... корень.

Таким образом, учитывая n вершин, высота дерева определяется по формуле n = 2 ^ (h + 1) - 1

Поскольку вы ищете h, вы должны взять log2 с обеих сторон формула n = 2 ^ (h + 1) - 1

Для полного бинарного дерева максимальная высота log2 (n + 1) = log2 (2 ^ (h + 1)) это равно потолку (log2 (n + 1) - 1) = h

Для неполного двоичного дерева максимальная высота = (n - 1) поэтому, если у вас есть n вершин, корень должен быть вычтен, чтобы получить максимальная высота из-за предыдущей формулы (2 ^ h = L)

Для минимальных высот, экстраполировать из приведенных выше правил.

Answer 2

N - количество узлов.
H - высота бинарного дерева.

Полное двоичное дерево:
Тогда при H высота N будет лежать между:

2^H <= N <= (2^(H+1) - 1)

Таким образом, решая это неравенство; мы получаем:

H <= lg(N)  and  H >= (lg(N+1) - 1)

Следовательно, мы наконец получаем:

H = floor( lg(N) ) = ceil( (lg(N+1) - 1) )   //as H is integer

(lg: база журнала 2)

Двоичное дерево (необязательно завершено):

Max height = N;  

Min Height = floor( lg(N) ) = ceil( (lg(N+1) - 1) )

Мы получаем минимальную высоту, когда двоичное дерево завершено.

Answer 3

Если у вас N элементов, минимальная высота двоичного дерева будет log2 (N) + 1.

Для полного двоичного дерева максимальная высота будет N / 2.

Для неполного двоичного дерева максимальная высота будет равна N.

Answer 4

Если корень может иметь любое количество листьев до 2 (0,1,2), то:

• Максимальная высота n-1 . Это тот случай, когда у вашего дерева только один лист. Ни один узел не имеет более одной ветви.
• Минимальная высота равна [log2 (n)] , где [x] - целая часть x.

Чтобы получить минимальную высоту, каждый корень должен иметь как можно больше ветвей. В этом случае вы заметите, что для n = 1 высота = 0; для n = 2 до n = 3, высота = 1; для n = 4 до n = 7 высота = 2; для n = 8 до n = 15, высота = 3 и т. д.

Таким образом, вы можете заметить, что для каждого n существует такое p, что:

2 ^ p <= n <2 ^ (p + 1) и p = высота, поэтому height = [log2 (n)] </p>

Answer 5

Подумайте, как может измениться структура дерева.

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

Так как это звучит как домашнее задание, я оставлю это там.

Answer 6

При n-nodes возможная максимальная высота floor(log(n)) = ceil (log(n+1))-1.

При n-nodes возможная минимальная высота составляет n-1.

Answer 7

Минимальная высота h = потолок (log (n + 1) / log (2) -1) для любого двоичного дерева.

Answer 8

Максимальная высота равна n, а минимальная высота (т.е. идеальное двоичное дерево) равна (log base 2 (n + 1)) - 1