より複雑なバイナリ検索ツリーを作成する

Question

バイナリ検索ツリーのルートとなる番号が与えられます。次に、バイナリ検索ツリーに挿入する必要があるN要素の配列が与えられます。配列がソートされた順序である場合、時間の複雑さはN^2です。私ははるかに良い複雑さ（NlogNと言う）で同じ木構造を取得する必要があります。私はそれをたくさん試しましたが、解決できませんでした。誰かが助けることができますか？

Answer 1

辞書で単語を検索する場合は、辞書を半分ほど開き、そのページを見ます。検索語が辞書の第1または第2の半分にあるかどうかがわかります。繰り返して、各パスの残りの単語の半分を削除し、すぐに1つの単語に絞り込みます。 40億語の辞書には約32回のパスが必要です。

バイナリ検索ツリーは同じ原則を使用します。見上げるだけでなく、挿入することもできます。ツリーが縮退しない限り、挿入はO（log N）です。 ツリーの縮退を防ぐには、 "赤"と "黒"ノードのシステムを使用します（色は従来のものです）。 のいずれかの色を長時間実行することはできません。完全な説明は、実装がここに

https://github.com/MalcolmMcLean/babyxrc/blob/master/src/rbtree.c https://github.com/MalcolmMcLean/babyxrc/blob/master/src/rbtree.h

である私の本、基本的なアルゴリズム

http://www.lulu.com/spotlight/bgy1mm

であるしかし、あなたは赤、黒 木について知りたい場合、あなたは、いくつかの説明が必要になりますそれから。

Answer 2

私はすべての数字が異なると仮定します（そうでない場合は、代わりにペア（数値、インデックス）を使用できます）。

要素「X」を挿入したいとします。それが今までの最小/最大の要素であれば、それがどこに行くのか明確です。

a = max y: y in tree and y < Xととしましょう。私はそれを主張します：

1. これらのうちの1つは、もう一方の祖先です。

2. aには適切な子供がいないか、bには左の子供がいません。

証明：

1. が、それはそうでないようにしましょう。 Let​​。 aがその左側のサブツリーにあり、bが右側のサブツリーにあるので、a < l < bです。矛盾。

2. aをbの祖先とする。 bに左の子がある場合c。 a < c < bより。矛盾（他の場合も同様に扱われる）。

だから、解決策は、このように書きます：

1. レッツ・A（私はC++でstd::setまたはTreeSetのようLOWER_BOUND操作で効率的な組を意味ツリーに既にある要素のセットを保ちますJava）。

2. は、すべての挿入時に上記のように（O(log N)時間にセットのLOWER_BOUND操作を使用して）aとbを見つけるのをしてみましょう。彼らの1人には適切な子供がいません。それが新しい要素が行くところです。

複雑さの合計は明らかにO(N log N)です。