一連の整数をツリーの範囲として格納するデータ構造を学習したことを覚えていますが、10 年が経ち、データ構造の名前を思い出せず、詳細が少し曖昧です。それが役立つ場合、それは CMU で教えられた関数型データ構造です。私は 2002 年の 15-212 (プログラミングの原則) を信じています。
基本的に、整数のセットを保存したいのですが、そのほとんどは連続しています。セットのメンバーシップを効率的にクエリし、整数の範囲を効率的に追加し、整数の範囲を効率的に削除できるようにしたいと考えています。特に、元の範囲が何であるかを維持することは気にしません。隣接する範囲が 1 つのより大きな範囲に結合された方がよいでしょう。
素朴な実装では、単純に HashSet や TreeSet などの一般的なセット データ構造を使用し、範囲を追加するときに範囲内のすべての整数を追加するか、範囲を削除するときに範囲内のすべての整数を削除します。しかしもちろん、それは add と remove を遅くするだけでなく、大量のメモリを浪費します。
私は純粋に機能的なデータ構造を考えていますが、現在の用途では必要ありません。IIRC、ルックアップ、挿入、および削除はすべて O(log N) でした。ここで、N はセット内の範囲の数です。
それで、私が覚えようとしているデータ構造の名前、または適切な代替案を教えてもらえますか?