少なくともO(log n)の挿入、削除、アクセス、およびマージを持つ地図データ構造はありますか？高速マージを可能にするマップデータ構造はありますか？
self-balancing binary treesAVL treesおよびred-black treesは、これらのプロパティの大部分を持っていますが、私はO(n log n)をマージしていると思います。高速なマージを持つデータ構造はありますか？
編集：私は周りを見回しており、このようなものは見つけられません。そのようなデータ構造がない場合、なぜこれが不可能であるかについてのいくつかの洞察が大好きです。
私はスプレーツリーを見ています。あなたはおそらく合併コストを途中で支払うことになりますが、別のツリーを挿入して後でコストを取り除くことができるはずです。
比較が定義されている任意のキータイプに対してはツリーが必要ですか、固定サイズのバイナリ表現（int、long、float、double、..）を持つ型でのみ機能する場合はOKです。 ）？後者が当てはまる場合、バイナリ基数木は非常に効率的なマージング（あなたがラッキーならばO（1）、最悪の場合はO（N））を持つデータ構造です。
データ構造の詳細については、Chris OkasakiとAndrew GillによるFast Mergeable Integer Mapsを参照してください。
Scala Collections Libraryにはintsとlongsの実装が含まれています。他のすべてのjavaプリミティブ型は、intsまたはlongsのいずれかに変換できます。 Doubleにjava.lang.Double.doubleToLongBitsを使用します。
それは涼しく、私はそれを使用するかもしれない...私はちょうど破壊的な読書の考えが好きではない。 – Zifre
@ Zifre：読み取りは実際には破壊的ではありません。何かがあれば、一般的に木の構造が改善され、外部の表現は変わらない。 –
スプレイツリーの定数はかなり悪いです。あまり頻繁にマージしないと、最悪の場合、マージの実行時間が「劣る」ことがあります。 – Dave