2

効率的な挿入、削除、検索を備えたデータ構造を探しています。これには通常、バイナリ ツリーが適していますが、アイテムは値に基づいて並べ替えられるのではなく、実際の挿入位置に基づいて並べ替える必要があります (つまり、配列のように)。すべての操作は、配列の場合と同様に、この位置に基づいてアイテムにアクセス、挿入、または削除します。

  • getItem(整数位置)
  • addItem(int insertPosition, オブジェクト項目)
  • removeItem(整数位置)

したがって、基本的な問題は、アイテムを挿入/削除すると、その後のすべてのアイテムのインデックスが 1 シフトされることです。明らかにインデックスを格納しても、O(n) よりも優れた結果が得られることはないため、基本的なバイナリ ツリー/ハッシュ テーブルはアウトです。

これらすべての操作をサブリニア時間で実装できる構造はありますか? 私は二分木を何らかの方法で適応させることができると考え続けており、各ノードに左の枝にノードの数を格納させることで、インデックスによる検索をサポートしたいと考えています。

4

2 に答える 2

0

2-3 インデックスで注釈が付けられたフィンガー ツリーは、これを実行できるはずです。それらは（関数型プログラミングの意味で）永続的であり、それは良いことも悪いこともあります。変更可能なバリアントが必要な場合は、少なくともアイデアの源になります。2-3 フィンガー ツリーのサポート

  1. 対数時間アクセス、および
  2. 償却定数時間の最初と最後に追加と削除、および
  3. より小さい部分のサイズで対数時間で分割および連結します。

そのため、任意の位置に挿入するには、その位置で分割し、いずれかの部分の末尾に追加してから連結できます。同様に、アイテムを削除するには、そのインデックスで分割し、アイテムを削除して、再度連結することができます。どちらも O(log n) 時間未満で済み、これは過大評価です。

Data.SequenceHaskell のモジュールは、既存の実装 (インデックス アノテーション用に特別にケース化され、パフォーマンスが調整されている) です。それらを紹介する論文は、必要以上に読みにくいです。一般的な考え方をより明確に説明している記事がありますが、多くの詳細が省略されているため、それらを実装するには不十分です。

于 2013-05-30T16:54:17.530 に答える