バイナリ検索ツリー

Question

最初に空のBSTで始まり、 'n'個のランダムな挿入を行うためのアルゴを提示します。挿入する値を取得するために一様乱数ジェネレータを使用します。結果のBSTの高さを測定し、 log2n.n = 100,500,1000,2000,3000 ....、10000に対してこれを行います.nの関数としてheight/log2nを入力します。比率はほぼ一定（約2）でなければなりません。これがそうであることを確認してください。

私の理解：
は今、我々はすべてのBSTの高さが「n」はlog2nあるtree.Ifの要素数は、それが左/右斜めに傾いた木です、そして高さが同じであることを知っています〜 'n'。したがって、ここで高さを測定すると、挿入のために想定する高さはランダムです。つまり、比率は常に2周ぐらいになります。
私はこれに対して私の頭を叩いています。

Answer 1

左斜め/右斜め木の場合、高さは「n」に等しくなります。私たちはここに高さを測定あれば、どのような高さ我々は、挿入のために想定する必要があり、そのようなバイナリツリーの高さはnある

ランダムです。ここでは何もする必要はありません。また、完全にバランスBSTの高さは、ログ（n）は（いない一般的には）あなたの質問に来

---

ですが、私はあなたがランダムにバイナリツリーを構築の高さを見つけるために求めていると仮定します。その場合、特定のバイナリツリーの高さを計算する必要はありません。

スキューされた木の高さがnであっても、均一なランダム分布で生成されている可能性は非常に低いです。したがって、ランダムなBSTの高さを計算すると、O（log n）になります。正確な計算のために

、参照してください Randomly build BST has logarithmic height