なぜJava Collections APIにTreeが実装されていないのですか

Question

私は最近自分のプログラムの1つにツリーを使用する必要がありました。私はバイナリツリーを自分で構築しなければならなかったのですが、なぜCollections APIにデフォルトツリー（またはバイナリツリー）の実装？

コレクションAPIに含めないと決めた理由があると思います。

Answer 1

java.util.TreeMapは、赤と黒のツリーの実装です。

Answer 2

IMHO、理論的には、Treeはコレクションの一種ではなく、単なる実装の種類です。私は抽象的なコレクション（配列の順序付けられていないセット）、リスト（順序付けされたエントリセット）、マップ（それらの間の関係を持つエントリの2つのセット）などがあり、それらの実装があることを意味します：array、list ）、HashSetなど、それらのすべてには長所と短所があります。したがって、ツリーは、配列よりも（おおよそ）高速な検索を提供するインデックスからのアクセスはありませんが、リストの実装の1つに過ぎません。

ところで、JavaのTreeMap（「Red-BlackツリーベースのNavigableMap実装」）とTreeSet（「TreeMapに基づくNavigableSet実装」）クラスがあります。

Answer 3

コレクションAPIに含めないと決めた理由があると思います。私は便利な理由は誰もが、ユースケースの広い範囲をカバーするのに十分な汎用の両方

• ある木のために良いAPIを打ち出していないことだと思い、そして

一般的なパフォーマンスのオーバーヘッドを補うのに十分です。

（そして、どこで？ツリーを停止していますか？バイナリツリー？N分木？DAG？グラフ？）

Apache CommonsのコレクションやGoogleコレクション（通称グアバ）のいずれもが持っていることは注目に値しますツリーAPI。しかし、このトピックにはアクティブなGuavaの問題があります - http://code.google.com/p/guava-libraries/issues/detail?id=174 - 少なくとも明らかに少なくとも人はあなたの視点に同意します。バージョン15.0のよう

UPDATE

、グアバは今TreeTraverserとBinaryTreeTraverserクラスの形式でツリーをサポートしています。しかし、これはあなたが期待するものではないかもしれません。実際には、これらのクラスはツリーデータ構造を実際に実装していません。代わりに、ジェネリック型のパラメータでこれを行う必要があります。さらに、Traverserクラスでは、ノード型のAPIについての前提を避けることさえできます。彼らは、抽象クラスであり、具体的なtraverserサブタイプにツリーを問い合わせる操作を実装することを要求することによってこれを行います。例えばノードの子を取得します。

---

FWIW、TreeMapとTreeSetは "木のAPI" ではありません。それらは、MapおよびSet APIのツリーベースの実装です。このツリーツーはパブリックAPIによって完全に隠されているため、これらの2つのクラスは汎用ツリーとして完全には使用できません。