Двоичная высота дерева

Question

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

Answer 1

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

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

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

Answer 2

Максимальная высота п и мин высота (IE идеальный бинарное дерево) является (логарифм по основанию 2 (п + 1)) - 1

Answer 3

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

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

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

Answer 4

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

Так что, возможно, лучше всего вы уточните, какой из них вам нужен.

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

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

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

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

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

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

Answer 5

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

Answer 6

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

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

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

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

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

Answer 7

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

Complete Binary Tree:
Тогда, с высоты 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 

(Л.Г.: логарифм 2)

Binary Tree (не обязательно полное):

Max height = N; 

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

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

Answer 8

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

С n-nodes Возможная минимальная высота: n-1.