Tree collections in Scala

Question

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?

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.

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.

Answer 1

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 true for 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).

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 and clumsy 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. TreeSet and TreeMap take 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 finding a tree inside a graph. Each of these uses require different representations and different algorithms -- the algorithms being what make them at all useful.

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

Answer 2

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/

Answer 3

TreeSet and TreeMap are both based on 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)

RedBlack is not documented very well but if you look at the source of TreeSet and TreeMap it'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).

Answer 4

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.TreeMap which uses a self-balancing binary tree structure called Red-Black-Tree.

So these data structures are rather useless for 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).

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

Answer 5

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

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