java - 並べ替えと順序付け以外のJavaのツリーマップデータ構造の利点

Question

並べ替えと順序付け以外に、Javaのツリーマップ データ構造の利点は何ですか? ツリーマップのデータ構造は内部でどのように機能しますか?

Answer 1

ツリーマップの主な利点は、キーと値のマッピングをソートされた順序で保存できることです。Treemap は、内部的に赤黒の木を使用します。

javadoc から:

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

この実装では、containsKey、get、put、remove 操作の保証された log(n) 時間コストが提供されます。アルゴリズムは、Cormen、Leiserson、および Rivest のアルゴリズム入門にあるものの適応です。

Wikiの赤黒木:

赤黒木は、一種の自動平衡二分探索木であり、コンピューター サイエンスで使用されるデータ構造です。自己バランスは、各ノードを 2 つの色のいずれかでペイントすることによって提供されます (これらは通常、「赤」と「黒」と呼ばれるため、ツリーの名前です)。著しくアンバランスにならないようにしてください。ツリーが変更されると、その後、新しいツリーが再配置されて再描画され、カラー プロパティが復元されます。プロパティは、この再配置と再配色を効率的に実行できるように設計されています。ツリーのバランスは完全ではありませんが、O(log n) 時間での検索を保証するには十分です。ここで、n はツリー内の要素の総数です。挿入、

レブ ブラック ツリーの詳細については、こちらをご覧ください: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree

ツリーマップ チェックの詳細については、 http ://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html を参照してください。