scala - Scalaのツリーコレクション

Question

Scalaにツリーを実装したい。私の特定のツリーは、Swing Splitペインを使用して、地理マップの複数のビューを提供します。分割ペイン内の任意のペイン自体をさらに分割して、追加のビューを提供できます。TreeMapもTreeSetもTree機能を提供しないと言っているのは正しいですか？これを誤解してしまったら失礼します。標準のツリーコレクションがあるはずだと思います。車輪の再発明を続けるのは悪い習慣です。将来のScala標準になる可能性のあるTreeの実装はありますか？

すべてのツリーには、ルート、ノード、リーフの3種類の要素があります。リーフとノードには、親への単一の参照が必要です。ルートとノードは、子ノードとリーフへの複数の参照を持つことができます。葉には子がありません。ノードとルートは、子を削除せずに削除することはできません。おそらく私が見逃した他のルール/制約があります。

これは、標準のコレクションを正当化するのに十分な一般的な仕様のようです。また、ルートとノードが2つの子または1つのリーフの子しか持てない場合は、標準のサブクラスコレクションが必要であることをお勧めします。これが私の特定のケースで欲しいものです。

Answer 1

実際、ツリー自体は非常に役に立たず、指定するのも非常に困難です。

後者から始めて、データ構造について厳密に言えば、ツリーは何人の子供を持つことができますか？ノードは値を保存しますか？ノードはメタデータを保存しますか？子供たちは両親へのポインターを持っていますか？ツリーをポインタ付きのノードとして保存しますか、それとも配列上の位置要素として保存しますか？

これらはすべて、答えが「状況によって異なります」である質問です。実際、あなたは子供たちが彼らの両親へのポインターを持っていると言いました、しかしそれはどんな不変の木にも当てはまりません！また、一部のツリーが実際には単一の配列（ヒープなど）にノードとして格納されている場合、ツリーは常に参照付きのノードオブジェクトとして格納されると想定しているようです。

さらに、これらすべての要件に対応できるわけではありません。相互に排他的なものもあります。それらを無視しても、自分に関係のない多くの詳細を処理する必要があるため、何にも最適化されておらず、使用するのが不器用なデータ構造が残っています。

そして、2番目の問題があります。それは、木自体が役に立たないということです。挿入/削除/ルックアップアルゴリズムによってソートされたデータに適したデータ構造になる特定のツリーを利用しますTreeSet。TreeMapしかし、それだけが木の用途ではありません。ツリーは、空間アルゴリズムの検索、ツリーのような実世界の情報の表現、ファイルシステムの構成などに使用できます。タスクがグラフ内のツリーを見つけることである場合もあります。これらの使用法のそれぞれは、異なる表現と異なるアルゴリズムを必要とします-アルゴリズムはそれらをまったく有用にするものです。

そして、それを締めくくりに、ツリークラスを書くことは簡単です。問題は、それを操作するためのアルゴリズムを書くことです。

Answer 2

GUIウィジェットとしての「ツリー」の概念（参照しているように見えます）と、順序付けられたデータ構造としてのツリーの間には、少し不一致があります。前者の場合、それは単なるネストされたシーケンスであり、後者の目的は、たとえば高速検索アルゴリズムを提供することであり、内部構造を任意に操作することはありません。多くの場合、分岐係数は一定で、木の高さはバランスが保たれています。後者の例は、collection.immutable.TreeMap赤黒木と呼ばれる自己平衡二分木構造を使用するものです。

したがって、これらのデータ構造は、へのブリッジングにはかなり役に立ちjavax.swing.TreeModelません。このインターフェースについてできることはほとんどないので、おそらくデフォルトの実装DefaultTreeModelである可変の非ジェネリック構造（シングルスレッドのSwingに必要なものすべて）を使い続けるでしょう。

JTreeScala-Swingラッパーの使用に関する議論については、この質問を参照してください。のScalaライブラリへのリンクもありますJTree。

Answer 3

ScalaでJavaクラスを使用できるので、javax.swing.treeパッケージを見てください：http: //docs.oracle.com/javase/6/docs/api/javax/swing/tree/package-summary.html、特にTreeModeland TreeNode、MutableTreeNodeおよびDefaultMutableTreeNode。これらはSwingで使用するように設計されていますが、ほとんど標準的なツリー実装です。

それ以外は、（ジェネリック）ツリーの実装は非常に簡単です。

Answer 4

GUIアプリケーションはツリーコレクションに低いパフォーマンス要求を課すため、ツリー構造化グラフのみを表すように制約された一般的なグラフライブラリを使用できます：http ：//scala-graph.org/

Answer 5

TreeSetとTreeMap両方に基づいていRedBlackます：

赤黒木はバランスの取れた二分木の一種で、一部のノードは「赤」と指定され、他のノードは「黒」と指定されます。他の平衡二分木と同様に、それらに対する操作は、ツリーのサイズに対数で時間内に確実に完了します。

（ Scala 2.8コレクションからの引用）

RedBlackは十分に文書化されていませんが、のソースを見て、TreeSetそれTreeMapを使用する方法を理解するのは非常に簡単ですが、要件のすべて（ほとんど？）を満たしていません（ノードには親への参照がありません、等）。