Какова высота полного двоичного дерева с N узлами?

Question

Какова высота полного двоичного дерева с N узлами? Я ищу точный ответ и значение пола или потолка.

Answer 1

Это CEIL(log2(n+1))-1

• 1 узел дает log2 (2) = 1
• 3 узлов дает log2 (4) = 2
• 7 узлов дает log2 (8) = 3
• 15 узлов дает log2 (16) = ...

EDIT: Согласно Википедии, корневой узел (а не по-Intuitiv ely?) не учитывается в высоте, поэтому формула будет CEIL(log2(n+1))-1.

Answer 2

Я думаю, вы можете использовать формулу, предложенную Joachim, или просто сделать пол журнала (h) ... это лучший случай, который вы можете сделать для любого двоичного дерева ... таким образом, если вы, например, заполнены, не может сказать, что это обязательно верно ... Также помните, что в CS почти каждый журнал, с которым вы сталкиваетесь, имеет базу 2

Answer 3

Вам не нужно делать CEIL (log2 (n + 1)) - 1 ,

Для полного двоичного дерева, ответ просто: ПОЛ (log2 (п))

• 1 узел дает 0
• 2 узлов дает 1
• 3 узлов дает 1
• 4 узла дает 2
• 5 узлов дает 2
• 6 узлов дает 2
• 7 узлов дают 2
узлы дают 3
• ...
• 15 узлов дают 3
• 16 узлов дают
• ...