9

Javaコレクション/Guava/ Apache CommonsライブラリにRed Black Tree/構造の実装はありますか？AVL Tree dataはいの場合、それらを私に向けていただけますか。基本的に、クエリがO（lg n）時間で発生するデータ構造を探しています。データ構造にもいくつかの更新がありますが、クエリほど頻繁ではありません。

4

1 に答える 1

13

基本的に、クエリがO（lg n）時間で発生するデータ構造を探しています

TreeMapを使用します。赤黒木に裏打ちされているので、アクセス時間は次のとおりですO(logN)（以下の引用に重点を置いています）

パブリッククラスTreeMap
はAbstractMapを拡張し
、NavigableMap、Cloneable、Serializableを 実装します

赤黒木ベースのNavigableMap実装。マップは、使用されるコンストラクターに応じて、キーの自然な順序に従って、またはマップ作成時に提供されるコンパレーターによってソートされます。

この実装は、containsKey、get、put、およびremove操作のlog（n）時間コストを保証します。

于 2012-08-25T13:03:25.763 に答える