c++ - std::map が赤黒木として実装されるのはなぜですか?

Question

が赤黒木std::mapとして実装されるのはなぜですか?

バランスの取れた二分探索木(BST)がいくつかあります。赤黒木を選択する際の設計上のトレードオフは何でしたか?

Answer 1

おそらく最も一般的な 2 つの自己均衡ツリー アルゴリズムは、Red-Black ツリーとAVL ツリーです。挿入/更新後にツリーのバランスを取るために、両方のアルゴリズムは、ツリーのノードを回転させて再バランスを実行するローテーションの概念を使用します。

両方のアルゴリズムで挿入/削除操作は O(log n) ですが、赤黒木の場合、ローテーションの再調整はO(1)操作ですが、AVL ではこれはO(log n)操作です。 Red-Black ツリーは、リバランス ステージのこの側面でより効率的であり、より一般的に使用される理由の 1 つです。

Red-Black ツリーは、Java や Microsoft .NET Framework から提供されるものを含め、ほとんどのコレクション ライブラリで使用されます。

Answer 2

それは本当に使い方次第です。通常、AVL ツリーにはリバランスのローテーションが多くあります。そのため、アプリケーションに挿入操作と削除操作がそれほど多くなくても、検索に重点が置かれている場合は、AVL ツリーがおそらく適切な選択です。

std::mapノードの挿入/削除と検索の速度の間で合理的なトレードオフが得られるため、赤黒ツリーを使用します。

Answer 3

AVL ツリーの最大高さは 1.44logn ですが、RB ツリーの最大高さは 2logn です。AVL に要素を挿入すると、ツリーのある時点での再調整が行われる可能性があります。リバランスにより挿入が終了します。新しいリーフを挿入した後、そのリーフの祖先をルートまで、または 2 つのサブツリーの深さが等しいポイントまで更新する必要があります。k 個のノードを更新する必要がある確率は 1/3^k です。リバランスは O(1) です。要素を削除すると、複数回の再調整が必要になる場合があります (ツリーの深さの半分まで)。

RB ツリーは、二分探索ツリーとして表される次数 4 の B ツリーです。B ツリーの 4 ノードは、同等の BST で 2 つのレベルになります。最悪の場合、ツリーのすべてのノードが 2 ノードであり、葉までの 3 ノードのチェーンが 1 つしかありません。その葉は根から 2logn の距離にあります。

ルートから挿入ポイントまで下っていくには、4 ノードを 2 ノードに変更して、挿入によってリーフが飽和しないようにする必要があります。挿入から戻って、これらすべてのノードを分析して、4 ノードを正しく表していることを確認する必要があります。これは、ツリーを下って行うこともできます。グローバルコストは同じになります。フリーランチはありません！ツリーから要素を削除するのも同じ順序です。

これらのツリーはすべて、ノードが高さ、重さ、色などの情報を保持する必要があります。このような追加情報がないのは Splay ツリーだけです。しかし、ほとんどの人は Splay ツリーを恐れています。その構造が不規則であるためです。

最後に、ツリーはノードで重み情報を運ぶこともできるため、重みのバランスを取ることができます。さまざまなスキームを適用できます。サブツリーに他のサブツリーの 3 倍以上の要素が含まれている場合は、バランスを取り直す必要があります。リバランスは、1 回または 2 回のローテーションで再び行われます。これは、2.4logn の最悪のケースを意味します。3 倍の代わりに 2 倍の比率で回避できますが、これはサブツリーの 1% 未満をあちこちで不均衡のままにすることを意味する場合があります。トリッキー！

木の種類はどれがいい？確かにAVL。それらはコーディングが最も簡単で、logn に最も近い最悪の高さを持っています。1000000 要素のツリーの場合、AVL は最大で高さ 29、RB 40、重量バランスは比率に応じて 36 または 50 になります。

ランダム性、追加、削除、検索の比率など、他にも多くの変数があります。

Answer 4

それはあなたの実装の選択です - それらはバランスの取れたツリーとして実装できます。さまざまな選択肢はすべて比較可能ですが、わずかな違いがあります。したがって、どれもどれも同じくらい良いです。