Scala 中的树集合

Tree collections in Scala

提问by Rich Oliver

I want to implement a tree in Scala. My particular tree uses Swing Split panes to give multiple views of a geographical map. Any pane within a split pane can itself be further divided to give an extra view. Am I right in saying that neither TreeMap nor TreeSet provide Tree functionality?Please excuse me if I've misunderstood this. It strikes me there should be standard Tree collections and it is bad practice to keep reinventing the wheel. Are there any Tree implementation out there that might be the future Scala standard?

我想在 Scala 中实现一棵树。我的特定树使用 Swing Split 窗格来提供地理地图的多个视图。拆分窗格中的任何窗格本身都可以进一步划分以提供额外的视图。我说 TreeMap 和 TreeSet 都没有提供树功能是否正确？如果我误解了这一点，请原谅。我觉得应该有标准的 Tree 集合，而不断重新发明轮子是不好的做法。是否有任何 Tree 实现可能成为未来的 Scala 标准？

All Trees have three types of elements: a Root, Nodes and Leaves. Leaves and Nodes must have a single reference to a parent. Root and Nodes can have multiple references to child nodes and leaves. Leaves have zero children. Nodes and Root can not be deleted without their children being deleted. there's probably other rules / constraints that I've missed.

所有的树都有三种类型的元素：根、节点和叶。叶子和节点必须有一个对父节点的引用。Root 和 Nodes 可以有多个对子节点和叶子的引用。叶子有零个孩子。节点和根节点不能在不删除其子节点的情况下被删除。我可能错过了其他规则/约束。

This seems like enough common specification to justify a standard collection. I would also suggest that there should be a standard subclass collection for the case where Root and Nodes can only have 2 children or a single leaf child. Which is what I want in my particular case.

这似乎足以证明标准集合的合理性。我还建议，对于 Root 和 Nodes 只能有 2 个孩子或单个叶子孩子的情况，应该有一个标准的子类集合。在我的特定情况下，这就是我想要的。

回答by Daniel C. Sobral

Actually, a tree by itself is both pretty useless and pretty difficult to specify.

实际上，树本身既无用又很难指定。

Starting with the latter, speaking strictly about the data structure, how many children can a tree have? Do nodes store values or not? Do nodes store metadata? Do children have pointers to their parents? Do you store the tree as nodes with pointers, or as positional elements on an array?

从后者开始，严格来说数据结构，一棵树可以有多少个孩子？节点是否存储值？节点是否存储元数据？孩子有指向父母的指针吗？您是将树存储为带有指针的节点，还是存储为数组上的位置元素？

These are all questions to which the answer is "it depends". In fact, you stated that children have pointers to their parents, but that is not truefor any immutable tree! You also seem to assume trees are always stored as node objects with references, when some trees are actually stored as nodes on a single array (such as a Heap).

这些问题的答案都是“视情况而定”。事实上，你说过孩子有指向他们父母的指针，但对于任何不可变的树来说都不是这样！您似乎还假设树始终存储为带有引用的节点对象，而当某些树实际上存储为单个数组（例如Heap）上的节点时。

Furthermore, not all these requirements can be accommodated -- some are mutually exclusive. Even if you ignore those, you are still left with a data structure which is not optimized for anything andclumsy to use because you have to deal with lots of details not relevant to you.

此外，并非所有这些要求都可以满足——有些是相互排斥的。即使你忽略了这些，你仍然会得到一个没有针对任何东西进行优化并且使用起来很笨拙的数据结构，因为你必须处理许多与你无关的细节。

And, then, there's the second problem, which is that a tree, by itself, is useless. TreeSetand TreeMaptake advantage of specific trees whose insertion/deletion/lookup algorithm makes them good data structures for sorted data. That, however, is not at all the only use for trees. Trees can be used to search for spatial algorithms, to represent tree-like real world information, to make up filesystems, etc. Sometimes the task is findinga tree inside a graph. Each of these uses require different representations and different algorithms -- the algorithms being what make them at all useful.

然后，还有第二个问题，那就是树本身是无用的。TreeSet并TreeMap利用特定树的插入/删除/查找算法使其成为排序数据的良好数据结构。然而，这根本不是树木的唯一用途。树可用于搜索空间算法、表示类似树的现实世界信息、组成文件系统等。有时任务是在图中找到一棵树。这些用途中的每一种都需要不同的表示和不同的算法——正是算法使它们变得有用。

And, to top it off, writing a tree class is trivial. The problem is writing the algorithms to manipulate it.

而且，最重要的是，编写一个树类是微不足道的。问题是编写算法来操作它。

回答by 0__

There is a bit of mismatch between the notion of "tree" as a GUI widget—which you seem to be referring to—and tree as an ordered data structure. In the former case it is just a nested sequence, in the latter the aim is to provide for instance fast search algorithms, and you don't arbitrary manipulate the internal structure, where often the branching factor is constant and the tree height is kept balanced, etc. An example of the latter is collection.immutable.TreeMapwhich uses a self-balancing binary tree structure called Red-Black-Tree.

“树”作为GUI 小部件的概念（您似乎指的是它）与作为有序数据结构的树的概念之间存在一些不匹配。在前一种情况下，它只是一个嵌套序列，在后一种情况下，其目的是提供例如快速搜索算法，并且您不会任意操纵内部结构，其中分支因子通常是恒定的并且树高度保持平衡等。后者的一个例子是collection.immutable.TreeMap使用称为红黑树的自平衡二叉树结构。

So these data structures are rather uselessfor bridging to javax.swing.TreeModel. There is little that can be done about this interface, so you'll probably stick with the default implementation DefaultTreeModel, a mutable non-generic structure (which is all that single threaded Swing needs).

因此，这些数据结构是相当无用的桥接javax.swing.TreeModel。关于这个接口几乎没有什么可以做的，所以你可能会坚持使用默认实现DefaultTreeModel，一个可变的非通用结构（这就是单线程 Swing 所需要的）。

For a discussion about having a scala-swing JTreewrapper, see this question. It also has a link to a Scala library for JTree.

有关使用 scala-swingJTree包装器的讨论，请参阅此问题。它还有一个指向 Scala 库的链接JTree。

回答by Polygnome

Since you can use java classes with Scala, take a look at the javax.swing.treepackage: http://docs.oracle.com/javase/6/docs/api/javax/swing/tree/package-summary.html, especially TreeModeland TreeNode, MutableTreeNodeand DefaultMutableTreeNode. They were designed to be used with Swing, but are pretty much a standard tree implementation.

既然你可以使用Java类使用Scala，看一看的javax.swing.tree包：http://docs.oracle.com/javase/6/docs/api/javax/swing/tree/package-summary.html，尤其是TreeModel和TreeNode，MutableTreeNode和DefaultMutableTreeNode. 它们被设计为与 Swing 一起使用，但几乎是标准的树实现。

Other than that, implementing a (generic) tree should be pretty straightforward.

除此之外，实现（通用）树应该非常简单。

回答by sourcedelica

TreeSetand TreeMapare both based on RedBlack:

TreeSet并且TreeMap都基于RedBlack：

Red-black trees are a form of balanced binary trees where some nodes are designated “red” and others designated “black.” Like any balanced binary tree, operations on them reliably complete in time logarithmic to the size of the tree.

红黑树是平衡二叉树的一种形式，其中一些节点被指定为“红色”，其他节点被指定为“黑色”。像任何平衡的二叉树一样，对它们的操作可靠地在时间上以树的大小对数完成。

(quote from Scala 2.8 Collections)

（引用自Scala 2.8 Collections）

RedBlackis not documented very well but if you look at the source of TreeSetand TreeMapit's pretty easy to figure out how to use it, though it doesn't fill all (most?) of your requirements (nodes don't have references to the parent, etc).

RedBlack没有很好地记录，但是如果您查看源代码TreeSet并且TreeMap很容易弄清楚如何使用它，尽管它没有满足您的所有（大多数？）要求（节点没有对父级的引用，等等）。

回答by ayvango

Since gui application imposes low performance demands on the tree collection you may use general graph library constrained to represent only tree structured-graph: http://scala-graph.org/

由于 gui 应用程序对树集合的性能要求较低，您可以使用限制为仅表示树结构图的通用图形库：http: //scala-graph.org/