こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

二分木の高さについて

二分木の高さについて

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


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


また逆に2)、高さhの二分木のもつ要素の最大と最小はいくつなのでしょうか?

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


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

投稿日時 - 2010-08-16 17:16:44

QNo.6113581

すぐに回答ほしいです

質問者が選んだベストアンサー

完全2分木のときは
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

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

投稿日時 - 2010-08-16 18:19:32

ANo.1

このQ&Aは役に立ちましたか?

2人が「このQ&Aが役に立った」と投票しています

回答(2)

ANo.2

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

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

投稿日時 - 2010-08-16 22:14:14

あなたにオススメの質問