c - 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) = 4
  ...

編集: ウィキペディアによると、ルート ノードは (かなり非直感的に?) 高さにカウントされないため、式は になりますCEIL(log2(n+1))-1。

Answer 2

CEIL(log2(n+1))-1 を実行する必要はありません。

COMPLETE バイナリ ツリーの場合、答えは単純に FLOOR(log2(n)) です。

• 1ノードは0を与える
• 2 ノードで 1
• 3 ノードで 1
• 4 ノードで 2
• 5 ノードで 2
• 6 ノードで 2
• 7 ノードで 2
• 8 ノードで 3
• ...
• 15 ノードで 3
• 16 ノードで 4
• ...

Answer 3

Joachimが提供する式を使用するか、単純にフロアログ（h）を実行できると思います...これは、バイナリツリーに対して実行できる最良のケースです...したがって、たとえばツリーがいっぱいの場合はできませんこれは必ずしも真であると言います...また、CSでは、遭遇するほとんどすべてのログが基数2であることを覚えておいてください