c# - レッドブラックツリーとマルチマップ

Question

多くのコンパイラでは、のような標準データ構造Setが背後で Red-Black-Trees を使用し、Map複数の重複したキーを格納します。Multimapmultimap

以下の引用について質問があります。

「赤黒木はキーを一意に格納し、各キーに DataValue を 1 つだけバインドします」

score 5 · Accepted Answer

1) いいえ、そうではありません。

2) キーを複数の値にマップするために単一のマッピング赤黒ツリーを変更するのは簡単です。2 番目のデータ構造とマッピングキー -> コレクションを使用するだけで済みます。

たとえば、文字列から int にマッピングする代わりに、文字列から int のベクトルにマッピングできます。または、int のリンクされたリストへの文字列。または、単一マッピング RBT への文字列。後で：）。

#1 の再検討: 技術的には、キーを単一の値にマッピングするだけで、値だけが直接マッピングされた型にはなりません。「DataValue」と見なすものに応じて、はい、ステートメントは真です。

また、補助データ構造は実際には必要ありません。トラバーサルを単純化するだけです。基本的に重複に対応するために、親/左と親/右の間の厳密な小なり/大なり関係の代わりに、一方の側にも等しいものを含めます。

例えば：

      5
   3     7
 3

score 3 · Accepted Answer

ノードの両側にある子に、親より小さくも大きくもないキーを含めることができます。そうしないと、ひどくバランスを失う可能性があるため、両側で平等を許可する必要があります--- n 個の等しいキーから作成されたツリーの高さは n になります。

c# - レッド ブラック ツリーとマルチマップ