問題タブ [red-black-tree]

最近読んだいくつかの本で二分木と二分探索について言及されているのを見てきましたが、私はまだコンピュータ サイエンスの研究を始めたばかりなので、アルゴリズムとデータを実際に扱うクラスをまだ受講していません。深刻な方法で構造。

典型的な情報源 (ウィキペディア、Google) を確認しましたが、(特に) 赤黒木の有用性と実装に関するほとんどの説明は、密集していて理解しにくいものでした。必要なバックグラウンドを持っている人にとっては完全に理にかなっていると思いますが、現時点ではほとんど外国語のように読めます.

では、プログラミング中に自分が行っている一般的なタスクのいくつかで、二分木が役立つのはなぜでしょうか? それ以外に、どのツリーを使用することを好みますか (サンプル実装を含めてください)、その理由は何ですか?

バイラルまたは制限的なライセンスなしで、効率的な C++ 間隔ツリーの実装 (ほとんどの場合、赤黒木に基づく) を見つけようとしています。クリーンで軽量なスタンドアロン実装へのポインタはありますか? 私が念頭に置いているユースケースでは、一連の間隔は最初からわかっており (100 万と言うでしょう)、特定の間隔と重なる間隔のリストをすばやく取得できるようにしたいと考えています。したがって、一度構築されたツリーは変更されません。迅速なクエリが必要なだけです。

Java クラス TreeMap は RB ツリーの実装を使用していると聞いています。この場合、TreeMap で順序、事前順序、および事後順序のツリー ウォークを行うにはどうすればよいでしょうか。

それとも、これは不可能ですか？

このページごとhttp://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx 「トップダウン削除」は、赤いノードを押し下げることによって積極的にツリーのバランスを取る赤黒ツリー ノード削除の実装です。ツリーを介して、削除されるリーフ ノードが確実に赤くなるようにします。葉ノードは必ず赤くなるため、ツリーの再バランスについて心配する必要はありません。赤い葉ノードを削除してもルールに違反することはなく、再調整するために追加の操作を実行する必要がないからです。バランスを取り、赤黒さを復元します。

「ボトムアップ削除」では、ツリーを下方向に通常のバイナリ検索を実行して削除するノードを見つけ、リーフ ノードを交換し (見つかったノードがリーフ ノードでない場合)、赤黒ツリー プロパティを復元します。赤黒のルール違反を修正しながら木を登ることによって。

トップダウン削除は再調整操作の数を最小限に抑えますか? トップダウンの削除が、ダウンの途中であまりにも多くの再カラーリングと再バランスを積極的に行う可能性はありますか?

このシナリオはどうですか: (x) は赤いノードを示します

16 を削除したい場合、ボトムアップの削除ではリバランスは行われませんが、トップダウンの削除では、ノードの色が完全に変更されてから、色の変更操作が不要であることがわかります。

反復 1:

反復 2:

反復 3:

次に反復 4 で、16 はすでに赤なので、押し下げる必要がないことがわかります。では、トップダウン削除は時間とスペースの効率が良いのでしょうか?

すべての AVL ツリーが赤黒ツリーのように着色できるという証明を探しています。誰か証明してくれませんか？

これは再ドラフトです。これが機能すると思いますか。特定の条件でテストしましたが、まだ失敗していません。

スティーブ・エッゲのシングルトンに関する記事を読んでいました。その中で彼は、先生がAVL木は悪だと言ったと述べています。赤と黒の木がより良い解決策であるというだけですか？

プログラマーとして、RBツリー、Bツリー、またはAVLツリーの使用をいつ検討する必要がありますか？選択を決定する前に考慮する必要がある重要なポイントは何ですか？

重要なポイントを参照して、なぜそれが他のものよりも選ばれるのか、各ツリー構造のシナリオで誰かが説明できますか？

標準のコンテナが適合しない場合に使用するための、リンクされたリスト/バイナリ ツリー メソッドのライブラリがあります。これには、赤黒ツリーの処理が含まれます。

メソッドの 1 つは、二重連結リストから完全にバランスのとれた単純なバイナリ ツリーに変換しますO(n)(アイテムの数が事前にわかっている場合)。このアルゴリズムは「フォールディング」として知られています。これは、Dr. Dobbs でかつて公開された二分木リバランス アルゴリズムの後半です。手順は基本的に...

• ツリーのサイズを考慮して、左右のサブツリーのサイズを決定します

• 左サブツリーの再帰

• リストからノードをポップして、ルートとして使用します

• 右のサブツリーの再帰

• サブツリーをルートにリンクする

赤黒木を作成する同様の方法もあります。原則は同じですが、再帰はノードの高さを追跡します。高さがゼロのノードは赤で作成され、その他はすべて黒で作成されます。開始時の高さの計算は、ツリー サイズの最高セット ビットに基づいており、完全にバランスの取れた(2^n)-1サイズのツリーが黒いノードのみを持つように調整されます (再帰は高さ 1 までしか下がりません)。

ここでのポイントは、リーフ レベルに赤いノードしかなく、最大で正確に半分のノードが赤いということです。

問題は、これは有効な赤黒木を生成する簡単な方法ですが、唯一のオプションではありません。完全にバランスの取れたツリーですべての葉が赤くなるのを避けることは、恣意的な選択でした。赤と黒のノードを交互に重ねることができます。または、場合によっては、完全にバランスが取れているサブツリーを見つけて、(赤いノードが必要な場合) サブツリーのルートをすべての葉ではなく赤にすることで、赤いノードの数を劇的に減らすことができます。

問題は、有効な赤黒木の形式を別の形式よりも選択する実際的な理由があるかということです。

これは純粋な好奇心です - 実際的な理由がないことはわかっていますが、この選択が重要な専門的なアプリケーションを知っている人はいますか?

次の機能を備えた、C# での赤黒ツリーの実装を探しています。

• O(log n) での検索、挿入、削除。
• メンバー型はジェネリックである必要があります。
• Comparer(T)でのサポート、その中のT異なるフィールドによるソート。
• ツリーでの検索は特定のフィールドを使用する必要があるため、 は受け入れませんがT、ソートするフィールド タイプは受け入れます。
• 検索は正確な値だけであってはなりません。下位/上位の検索をサポートする必要があります。

ありがとうございました。