[解決済み】なぜstd::mapは赤黒い木として実装されているのですか？

質問

なぜ std::map として実装されています。 赤黒い木 ?

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

どのように解決するのか？

最も一般的な自己均衡木のアルゴリズムは、おそらく次の2つでしょう。 赤黒い木 と AVLツリー . 挿入/更新後の木のバランスをとるために、どちらのアルゴリズムも木のノードを回転させて再バランスをとるという回転の概念を用いています。

両アルゴリズムとも挿入/削除操作はO(log n)であるが、Red-Black木の再バランスをとるための回転は O(1) の操作であるのに対し、AVLでは O(log n) このため、Red-Black木がより効率的に再バランスを行うことができ、より一般的に使用されている理由の1つになっています。

Red-Blackツリーは、JavaやMicrosoft .NET Frameworkを含むほとんどのコレクションライブラリで使用されています。