バイナリ検索ツリーの平均高さ

Question

1000個のランダムな整数を追加すると、バイナリ検索ツリーの平均高さはどのように計算されますか？平均の高さは何ですか？

Answer 1

あなたはこの再帰的な定義を使用して、バイナリツリーの高さを計算することができます。経験的に、このような木の平均高さを測定するために

height(empty) = 0 
height(tree) = 1 + max(height(tree.left), height(tree.right)) 

一つの方法は、繰り返し空のツリーを作成し、1000個のランダムなアイテムを追加することですそれ。上記の関数を使用して各試行の高さを測定し、平均します。

あなたの仕事は、おそらく二分木の平均高さの公式を見つけることだと思っています。

Answer 2

それは追加される順序によって異なります。最小値から開始すると、新しい値がすべて右の子BSTに追加されるため、ツリーが深くなります。最初に最大値を追加すると、右側が空である間に左側の子は深くなります。

Answer 3

どのような種類のバランスの取れたツリー構造（赤黒のツリーなど）を使用しているかによって異なります。乱数をバイナリツリーに挿入しているので、平均深さがlog2（1000）程度であると予想するのが妥当でしょう - したがって、値10と11は「正常」です。私はそれがどれほど遠く離れているのかは分かりません。おそらく幾分深い、10レベルより浅い。均衡のない極端なケースは1000深度です。それは乱数で起こることはまずありません。

Answer 4

あなたが使用しているツリーに関係なく、平均高さはlog2（1000）になります。挿入された数字の順番によって、実際の高さは変わるかもしれませんが、ランダムに分布した数字を仮定すると、実際の値は予想値に近似します（log2 （1000））

Answer 5

この質問は実際には難しいです。答えは1000ではないでしょう。なぜなら、log2（1000）もツリーがどのように成長するかによってはそれほど難しくありません。

ツリーをステップ実行してintを追加すると、ツリーが単純にlog2（1000）よりも大きくなります。

通常の確率分布に関連しているように見えるので、統計者に相談してください。それらは反復されたランダムな事象（頭部1単位、尻尾は左）の多くによって生成され、乱数の値は木が葉に落ち着くまで繰り返されます。

Answer 6

この質問は、実際にツリーを生成せずにこれを確実に実行できるかどうかを私に尋ねました。

N個のユニークな数字の可能なすべての順列を単純に実装されたバイナリツリーに追加した場合の平均的な高さの答えを計算するアプリケーションを作成できました。

私が得た回答はこのグラフにあります。

 
N  Average Height 
2  2 
16 7.039 
32 9.280 
64 11.679 
256 16.783 
343 17.896 

Granitebolshevikが正しい（X軸は、ツリー内の項目の数は、青い線は平均の高さであり、赤線が最適可能高さである）ことが可能です余計な機能をバランスさせることなく、単純に実装されたツリーが最適な高さになることは統計的には考えられません。

アルゴリズムの複雑さはO（N^2）であり、本当に大きな数を計算するのに十分速いわけではありません。

Answer 7

例えば、数値の近似値の数がありますが、この質問に簡単な答えがあるように表示されません。：

Devroye、リュック。 "バイナリサーチツリーの高さに関するノート" Journal of the ACM（JACM）33.3（1986）：489-498。

Reed、Bruce。 msgstr "ランダムなバイナリ検索ツリーの高さです。" Journal of the ACM（JACM）50.3（2003）：306-332。

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap13.htm

これらの近似は、一般的に形を取る：A ln n - B ln ln n + C

どこA~4.311と

B~1.953だから、おそらく言うことは最も有用なものランダムな挿入のための平均の高さはO(log n)であるということです、実際に数値近似が必要な場合は、(4.311 ln n - 1.953 ln ln n)は大きなnに対して十分に近いと思います。

n=1000については、約26となり、これは他の場所で報告されている実験結果とよく似ています。