二分木の高さについて

質問

二分木の高さについて

このカテゴリでいいのか迷ったのですが。。。

１）、葉を含めて節点の総数がNであるような二分木の高さの範囲、というのはどういったのものなのでしょうか？

また逆に２）、高さｈの二分木のもつ要素の最大と最小はいくつなのでしょうか？

導き方も含めてお答えいただけると助かります。

ちなみに１）の自分の答えは完全二分木のときはlogn、最悪にバランスが取れていない時がnです。

回答No.1

ohtawa · ベストアンサー

完全２分木のときは
s = 1 + 2^1 + 2^2 + + 2^h =(2^(h+1)-1)/(2-1)= 2^(h+1)-1

h + 1 = log( s + 1 )
h = log( s + 1 ) - 1
log は　2　の対数

もっともアンバランスのときは

s = h + 1

h = s - 1

でどうでしょうかね
高さの定義にもよるでしょうね

回答No.2

asuncion

＞１）の自分の答えは完全二分木のときはlogn、最悪にバランスが取れていない時がnです。

だとすると、ノードの数が２個（完全二分木の場合もバランスが最悪の場合も同じ形）のとき、
おかしなことになりませんか？