data-structures - 高速マージを可能にするマップ データ構造はありますか?

Question

少なくともO(log n)挿入、削除、アクセス、およびマージを行うマップ データ構造はありますか?

AVL 木や赤黒木などのほとんどの自己均衡二分木は、これらの特性のほとんどを備えていますが、それらには融合があると私は信じています。マージが高速なデータ構造はありますか?O(n log n)

編集：私は周りを見回しましたが、このようなものは見つかりません。そのようなデータ構造がない場合、なぜこれが不可能なのかについての洞察が欲しいです。

Answer 1

スプレーツリーを見てみたいと思います。途中でマージ コストを支払うことになる可能性がありますが、別のツリーを挿入してコストを後回しにすることができるはずです。