1

次の保証を提供する Java で実装されたデータ構造はありますか。

  • 要素は常にソートされます
  • 要素を追加すると、少なくとも O(lg n) で実行されます
  • 特定のインデックスで要素を取得すると、少なくとも O(lg n) で実行されます

基本的には、次のことができるようにしたいと考えています。

SomeDataStructure elements = new SomeDataStructure();
elements.add(5);
elements.add(1);
elements.add(10);
assertEquals(1, elements.get(0));
assertEquals(5, elements.get(1));
assertEquals(10, elements.get(2));

ここで、addとgetメソッドの両方が少なくとも O(lg n) で実行されました。

これはツリー構造で実行できるように思えますが、インデックス付きの get メソッドを提供する実装が見つかりません。このために java.util.TreeMap を使用/拡張することも検討しましたが、すべての回転ロジックはプライベートであるため、ツリーがどのように変更されているかを追跡できません。

4

3 に答える 3

0

読み取りと書き込みをインターリーブする必要がない場合、つまり、データ構造を一度にすべて構築し、構築後に変更することなく、その中で物事を調べたい場合は、単純に構築しますリストを並べ替えてから、インデックスをリストに使用します。ツリーを構築している間、構造をソートしておく必要がないため、この状況ではツリーはやり過ぎです。

List<Integer> elements = new ArrayList<Integer>(3);
elements.add(5);
elements.add(1);
elements.add(10);

Collections.sort(elements);

assertEquals(1, elements.get(0));
assertEquals(5, elements.get(1));
assertEquals(10, elements.get(2));

追加はそれぞれ O(1) 回 (つまり、n 個のアイテムを追加する場合は O(n)) で行われ、並べ替えは O(n * log(n)) 時間で行われるため、全体的な複雑さは O(n + n * log) になります。 (n)) = O(n * log(n)) 構造を構築するため。これは、それぞれ O(log(n)) 回で n 個の要素を追加するのと同じです。ただし、検索は一定の (O(1)) 時間で行われるため、ツリーベースのソリューションよりも効率的です。

構造が変更されない (つまり、ソートが失われない) ことを保証したい場合は、上記の 5 行目を次のように置き換えることができます。

elements = Collections.unmodifiableList(Collections.sort(elements));

これは、誰かがリストを変更しようとすると例外をスローします。これは、何か問題が発生しているという手がかりになります。

于 2012-08-01T17:19:12.150 に答える
0

を使用して、ツリーを走査してそのインデックスを取得するメソッドをTreeMap追加できるように見えますか?get

keySetイテレータを使用して順番に実行できる場合がありますが、そのパフォーマンスに関するドキュメントはありません。

于 2012-08-01T16:59:54.490 に答える
-1

TreeMapのJavaSE ドキュメントから:

この実装では、containsKey、get、put、remove 操作の保証された log(n) 時間コストが提供されます。

使用している実装に関する情報を調べることで、同じことを見つけることができます。

于 2012-08-01T16:17:32.213 に答える