1

幅が整数のアイテムのリストがあります。これは、間隔が左から右に積み上げられたものとして解釈できます。たとえば、項目が A、B、C、D、E、および F で、幅がそれぞれ 5、2、2、3、2、および 4 であるとします。

例

項目の下の数字は、リストの先頭からのオフセットを示します。

理想的には O(n) 未満で、これらの操作を効率的にサポートするデータ構造を探しています。

  • 指定された位置からアイテムを検索します。たとえば、位置 11 の項目は 9 から 12 に及ぶため D であり、位置 14 の項目はそこから始まるため F です。
  • 2 つの既存のアイテムの間にアイテムを挿入するか、既存のアイテムを削除します。これにより、後続のアイテムの位置がずれます。たとえば、アイテム E を削除すると、アイテム F が 2 つ左にシフトし、12 から 16 にまたがります。

各レベルが下のレベルに含まれる幅を格納する、スキップ リストに似たものを使用することを考えていましたが、どのようなパフォーマンス特性が得られるかはよくわかりません。

助言がありますか？

4

1 に答える 1

3

ロープの変形はいかがですか。

しかし、葉にひもがある代わりに、間隔があります。

特定の位置を含む間隔を見つけると、O(log n) になります (ロープのインデックス アルゴリズムを変更して、インデックスを作成する代わりにリーフを返すようにするだけです)。

任意の場所に項目を挿入すると、O(log n) になります (1 回分割して 2 回連結すると、すべて O(log n) かかります)。

本質的に確率論的であり、不運に遭遇した場合に O(n) の最悪のケースがあるスキップリストとは異なり、これらの操作は O(log n) 保証されます (O(log n) のbalancing-concatenate を使用すると仮定します)。 .

于 2013-08-27T12:11:55.173 に答える