確率と漸近線

Question

バイナリ検索ツリーの場合、同じ入力がある場合を考えてみましょう。ノードを挿入しながら、x.leftおよびx.rightからランダムに選択します。

clrs（12-1-（d））に質問があり、このセットアップの予想される実行時間を得るように求められます。直感的には、答えは単にO（n lg n）です。しかし、どうすればそれを証明できますか？

何かアドバイスありがとうございます。

月。

Answer 1

このプロセスが完了した後、最終的なツリーがあるとします。行番号1,2,3、...、nを使用してツリー内の各ノードにラベルを付け、結果のツリーがバイナリ検索ツリーになるようにします。さて、各要素がどこで終わったのかを知って、木を構築するプロセスを再生することを想像してみてください。トレースアウトするプロセスは、数値に基づいて各要素に対して通常のBST挿入を行うのと同じ結果に終わります。ですから、この問題は以下の問題と同じになります。要素1,2,3、...、nのランダムな並べ替えをバイナリ検索ツリーに挿入すると、実行する予定の時間はどれくらいですか？そう？

この問題の解決方法を既に知っていれば、完了です。そうでない場合は、このプロセスが要素1、2、3、...、nの配列に対してランダム化されたクイックソートを実行するのと同等であることに気づくことが大変です。これを見るための1つの方法があります。ツリーのルート要素は、選択された最初のピボット要素に対応します。挿入されるすべての要素は、それに対して比較され、左または右のサブツリーに入れられます。ルートの左の子は、最初のピボットよりも小さい要素の再帰呼び出しで選択されたピボットに対応します。最初のピボットよりも小さいすべての要素が左側のピボットと比較されます。帰納法を使用してこの議論を形式化することができます。長さnの任意の配列に対して、要素1,2,3、...、nのランダム置換をバイナリ検索ツリーに挿入するときに行われる比較の数が、木構造で与えられたパターンに従った構造のピボットを使ってその配列に対してquicksortを実行します。

この接続が完了すると、ランダム化されたクイックソートの予想コストはΘ（n log n）であるため、完了です。