問題タブ [red-black-tree]

boost::multi_index::multi_index_containerハードディスク ストレージの場合、赤黒木 (のようなもの) に基づくマルチ インデックス コンテナーが必要です。すべてのデータは、メモリではなくハードディスクに保存する必要があります。

記載されている条件が満たされるようなオープンソースのコンテナはありますか?

ノート。私は使用しますC++。

RedBlack Tree について調査していたところです。.Net 4.0 の SortedSet クラスが RedBlack ツリーを使用していることは知っていました。そこで、Reflector を使ってその部分をそのまま取り出して、RedBlackTree クラスを作成しました。今、この RedBlackTree と SortedSet に 40000 の連続した整数値 (0 から 39999 まで) を挿入していくつかのパフォーマンス テストを実行しています。次のように大きなパフォーマンスの違いがあることに驚いています。

その背後にある理由は何ですか？ところで、リリース構成のみでテストを実行しました。ここに小さなテストコードがあります

編集

抽出した RBTree のコードも共有して、診断を実行できるようにしたいと思います。

編集

他のデータ構造（私が作成したもの*、.netフレームワーク**からのもの）で同じ診断を実行したところ、興味深い結果が得られました

RBTree は上記と同じです (SortedSet クラスから取り除かれています)。私も 400000 の値で試しましたが、RBTree は FOREVER を取っているようです。理由は本当にわかりません。

赤黒木への挿入と削除のための反復アルゴリズムへのポインタを教えてください。.Net/C# で利用可能なすべてのアルゴリズムは再帰に基づいており、非常に多数のデータを処理することは信頼できません (したがって、挿入/削除のための多数の再帰の深さ)。反復に基づいたものを持っている人はいますか?

注 : Goletas.Collection は、大量のデータに対して非常に効率的な AVL ツリーの反復アルゴリズムを使用します。Red-Black Tree にも同様のことが必要です。

来週、アルゴリズムの試験があり、それに備えるための質問がありました。しかし、これらの質問の1つで私は困惑しました。

「7つの黒いノードと10の赤いノードで赤黒木を描くことができますか？なぜですか？」

すぐに答えられるように思えますが、気が進まないです。

CRLSは、n個の内部ノードを持つRBツリーの最大の高さを示します：2 * lg（n + 1）。

この補題だけで問題は解決できると思いますが、よくわかりません。

任意のヒント？

赤黒 (RB) ツリーの用途は何ですか? RB Tree のみを使用でき、他のデータ構造を使用できないアプリケーションはありますか?

本質的にハッシュベースのルックアップである現在のインデックス作成の実装よりも高速であるかどうかをテストしたいので、インデックス作成にツリー構造を使用して実験することを考えています。

Bツリー、AVLツリー、赤黒ツリーのパフォーマンスに関するさまざまな質問や記事を読んだことがありますが、パフォーマンスの面でそれらの違いはあまりわかりません。

人々が推奨するツリー構造とその理由は何ですか？理想的には、既存の.Net実装が利用可能である必要がありますが、必要に応じて独自の実装を行うことを嫌がりません。

RB で複数のノードを削除できるアルゴリズムはありますか、または RB からノードを削除する唯一のアルゴリズムは、次の方法でそれを行うことです:
1. 1 つを削除し、
2. 必要に応じてツリーを修正します。

一部のCPUスケジューラで実行するタスクを選択するために使用されるさまざまなアルゴリズムに適用されるため、2つの違いを理解しようとしています。

所要時間が最も短いプロセスを左側に配置し、左側から実行するノードを選択する RB ツリーと、それらを最短のジョブから順に配置するキューの違いは何ですか?

すぐに使用できるものはどこにありますか? さらに言えば、「標準」データ構造の優れたコレクションをご存知ですか?

赤黒は実装が簡単であることは別として。

すべての操作 (挿入、削除、検索) は、両方のツリーで O(log n) の時間の複雑さを持っているようです。私が見逃しているこれらの操作の間に特定の違いはありますか?

「red-black」「2-3 tree」をグーグルで検索しても、2 つの比較は見つかりません。

赤黒が一般的に最高と考えられていることを理解するようになりました. ([編集] 赤黒が AVL ツリー (同じカテゴリ) よりも高速である理由の 1 つは、「永続的なデータ構造への適用」の効率であると聞いたことがあります。効率の再調整によるものですが、そうではありません。私の質問に答えないでください..）