tree - 確率と漸近

Question

二分探索木に対して、n個の同一の入力がある場合を考えてみましょう。ノードを挿入する際に、 x.leftとx.rightからランダムに選択します。

clrs (12-1-(d)) には、このセットアップの予想実行時間を導き出すよう求める質問があります。直観的に、答えは単純に O(n lg n) です。しかし、どうやってそれを証明するのですか？

アドバイスをいただければ幸いです。

月。