1000 個のランダムな int を追加するときに、二分探索木の平均高さをどのように計算しますか? 平均身長は？
質問する
14452 次
7 に答える
4
次の再帰的な定義を使用して、二分木の高さを計算できます。
height(empty) = 0
height(tree) = 1 + max(height(tree.left), height(tree.right))
このようなツリーの平均高さを経験的に測定する 1 つの方法は、空のツリーを繰り返し作成し、そこに 1000 個のランダムなアイテムを追加することです。上記の関数を使用して各試行の高さを測定し、それらを平均します。
おそらくあなたの仕事は、二分木の平均高さの式を見つけることだと思います。
于 2009-05-14T03:19:44.147 に答える
4
これは、バランスの取れたツリー構造 (赤黒ツリーなど) を使用しているかどうかによって異なります。二分木に乱数を挿入しているので、平均深さは約 log2(1000) であると予想するのが合理的です。したがって、値 10 と 11 は「正常」になります。そこからどれだけ逸脱できるかはわかりません。10 レベルよりも浅く、場合によってはやや深くなります。バランシングを行わない極端なケースは、深さ 1000 です。これは、乱数では起こりそうにありません。
于 2009-05-14T03:22:46.277 に答える
3
この質問に対する単純な答えはないように見えますが、いくつかの数値近似があります。たとえば、次のとおりです。
デヴロイ、リュック。「二分探索木の高さについて」Journal of the ACM (JACM) 33.3 (1986): 489-498.
リード、ブルース。「ランダム二分探索木の高さ」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=1000は、約26- が得られます。これは、他の場所で報告された実験結果に非常にうまく適合します。
于 2013-03-25T06:31:18.610 に答える
1
実際、この質問はトリッキーです。答えは 1000 にはなりません。これはありそうもないことですが、log2(1000) もありそうにありませんが、ツリーの成長方法によってはなおさらです。
ツリーをステップ実行して int を追加し、単純に追加すると、ツリーはほぼ常に log2(1000) よりも高くなります。
これは正規確率分布に関連していると思われるため、統計学者に相談してください。これらは、多数の反復ランダム イベント (ヘッドは 1 ユニット右、テールは左) によって生成され、ランダムな整数の値は、ツリーがリーフに落ち着くときにツリーを反復します。
于 2009-05-14T04:53:12.003 に答える
0
追加される順序によって異なります。最小値から開始すると、すべての新しい値が正しい子 BST に追加されるため、ツリーはより深くなります。最初に最大値を追加すると、左側の子は深くなり、右側は空になります。
于 2009-05-14T03:18:37.517 に答える
-2
誰かが前に述べたように、使用しているツリーに関係なく、平均の高さは log2(1000) になります。挿入された数値の順序によって実際の高さが異なる場合があることは事実ですが、あなたが言及したランダムに分散された数値を想定すると、実際の値は多くの場合、期待値に近似します(これもlog2です(1000))
于 2009-05-14T04:38:08.093 に答える