data-structures - 二分木の高さの範囲

Question

二分木の可能な高さがlogN <= Height <=N-1 (N はノードの数) であることを数学的に証明できます。しかし、この答えを 1 ～ 2 文で説明するにはどうすればよいでしょうか。

Answer 1

最小の高さと最大の高さが発生する 2 つのケースを考えてみましょう。

最小の高さ: 各非リーフ ノードに正確に 2 つの子がある場合

最大の高さ: 各非リーフ ノードにちょうど 1 つの子がある場合、つまり線形の場合

Answer 2

完全にバランスの取れたツリー (非リーフ ノードに 2 つの子がある) のサイズは N=2^n-1 ノード、log2(N)=n レベルです。

ツリーの退化したケース (すべてのノードに 1 つの子がある) はリストであり、サイズ N には N レベルがあります。