C++の標準ライブラリに赤い黒のツリーやavlツリーの実装がありますか？

Question

マルチセットのように、STLのバイナリ検索ツリーの実装は、RBツリーまたはAVLツリーの実装が利用できますか？

Answer 1

通常、multisetはバイナリツリーとして実装しません。ツリーをO（logN）の挿入と削除を持たないリンクリストのように見せかける可能性があるため、1つを使用すると標準の性能保証が破られます。

典型的には、std::set/std::multiset/std::map/std::multimapは、これらの性能保証があるため、RBツリーとして実装されます。しかし、これは必須ではありません。この規格は、異なる操作におけるコンテナの性能を保証しており、その実現方法は実装次第です。

RBツリーを使用しているかどうかを確認するには、実装を確認したり、自分でロールしたり、RBツリーであることを保証するサードパーティライブラリを入手する必要があります。