二分木の高さについて

二分木の高さについて

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


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


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

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


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

No.1 ベストアンサー 回答者： ohtawa 回答日時： 2010/08/16 18:19

完全２分木のときは

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 回答日時： 2010/08/16 22:14

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

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