私はBalanced BSTに関する理論的な質問があります。パーフェクトバランスバイナリ検索ツリー
ノード2^k - 1を持つPerfect Balanced Treeを通常のunbalanced BSTから構築したいと考えています。私が考えることができる最も簡単な解決策は、並べ替えられたArray/Linked listを使用して、配列をサブ配列に再帰的に分割し、そこからPerfect Balanced BSTを構築することです。
しかし、ツリーサイズが非常に大きい場合は、同じサイズのArray/Listを作成して、この方法で大量のメモリを消費する必要があります。
もう1つの選択肢は、要素ごとに要素を挿入し、ツリーバランス係数に応じてツリーをローテーションとバランスさせる回転機能を使用することです - 左右のサブツリーの3つの高さ。
私の疑問は、私の仮定について正しいのですか？不完全なBSTから完全なBSTを作成する他の方法はありますか？
完全にバランスの取れた検索ツリーが必要な非常に良い状況はまだありませんでした。あなたのケースに本当に必要な場合は、それについて聞きたいと思います。通常、ほぼ均衡のとれたツリーを作成する方がよいでしょう。
検索ツリーが大きい場合は、既存の構造をすべて破棄するのは良い考えではありません。回転関数を使用すると、既存の構造のほとんどを保存しながら、よりバランスのとれたツリーを得る良い方法です。しかし、通常、完全に不均衡なツリーがないことを確認するのに適したデータ構造を使用します。いわゆる自己バランスのとれた木。
たとえば、AVLツリー、赤黒ツリーまたはスプレイツリーがあります。これは、回転のわずかに異なるバリアントを使用して、ツリーのバランスを保ちます。
本当に完全に不均衡なツリーがある場合は、別の問題が発生する可能性があります。あなたのケースでは、それをAVLの方法で回転させるのがおそらくそれを修正する最良の方法です。
AVLなどのツリーは、完全にではないため、このコンテキストでどのように役立つかわかりません。あなたがforwardとbackwardポインタの代わりにleftとrightポインタを使用して、ツリーノードのうち、二重リンクリストを構築することができ
。そのリストをソートし、ツリーを下から上に再帰的に構築し、リストを左から右に消費します。
サイズ1のツリーを構築するのは簡単です。一番左のノードをリストから削除してください。あなたのサイズNのツリーを構築することができれば
さて、あなたはまた、サイズ2N+1のツリーを構築することができますサイズNの別のツリーを構築し、その後、その後、単一ノードをかみ切る、サイズNのツリーを構築します。シングノードは大きなツリーのルートになり、2つの小さなツリーは左右のサブツリーになります。リストがソートされるので、ツリーは自動的に有効な検索ツリーになります。
これは2^k-1以外のサイズでも簡単に修正できます。
更新：あなたは、検索ツリーから始めているので、あなたがO(N)時間とO(log N)スペース（ちょっとした工夫でおそらくO(1)のスペース）で直接からソートされたリストを構築し、また木のボトムアップを構築することができますO(N)時間であり、O(log N)（またはO(1)）スペースです。
メモリが拘束されている場合、O（log n）時間のAVLツリーで実行できる分割操作と結合操作を使用できます。
注文統計を維持することができた場合は、中央値で分割し、LHSとRHSを完全にしてから参加させることができます。
（再帰的バージョン）の擬似コードは
これはO（N）時間とO空間（ログn）に実装することができる、私は信じているであろう。
大まかなツリーがあり、既存の構造をほとんど変更せずにツリーを変換したい場合は、回転関数の中には完璧な意味があります。 - 結果は本当に完璧にバランスを取らなければならないのですか？質問の背景は何ですか？ – michas
はい、完全にバランスが取れている必要があります。これは学術プロジェクトの一部です。 「回転機能」とはどういう意味ですか？私が知る限り、実装が簡単な4つの回転関数があります。 – OlejkaKL
異なる種類のツリーは、わずかに異なる回転方法を使用します。たとえば、AVLと赤黒の木を比較します。 – michas