The classic representation of 2-dimensional trees, a parent with a set of children, does not fit well into a generalized form for a tree in higher dimensions. Since a 2-dimensional tree has arbitrarily many 2-dimensional children that have a 1-dimensional ordering, a node in a 3-dimensional tree would have arbitrarily many 3-dimensional children that have a 2-dimensional ordering. For an n-dimensional tree, a node would have arbitrarily many n-dimensional children with an (n-1)-dimensional ordering.
Using a "threaded form" for trees allows us to simply add one child per node for every dimension in the tree. Instead of maintaining arbitrarily many n-dimensional children, nodes in the threaded form contain a single child for every dimension. This creates a "left child, right sibling" relationship for 2-dimensional trees, where a root is the parent of a linearly ordered forest. The construction becomes generalized to two operations: adding another sibling to a forest and adjoining a forest under one root node.
This allows not only for arbitrarily many dimensions, but also for constructing arbitrary branching structures. So for a 2-dimensional tree, a node would have a 2nd and 1st dimensional child. The second dimensional child would be the first tree in a linearly ordered forest, while the first dimensional child would be a sibling in that node's own forest. The same structure holds for a 3-dimensional tree, but the children are now organized in a two dimensional tree rather than a linear structure.
Generalizing the two tree-building operations to n dimensions, however, requires that we create a new, generalized operation. Instead of first adding siblings to create a forest, and then assigning the forest a root node, we will do this in one step. Taking a label and two forests, we will create a new node that is the root of the first forest and the leftmost sibling of the second forest. We can then generalize this operation to one that takes d d-dimensional forests and a label and combines them under a new node of that label to form another d-dimensional forest. The formation of roots is still supported by using the empty tree as arguements in the operations. In two dimensions, a 2-dimensional root is formed if there is no 1-dimensional child. Otherwise, it is a sibling. For n-dimensions, an i-dimensional root is formed if there is no j-dimensional child, where j < i. Otherwise, a sibling is formed.
The linear form of threaded trees follows directly from their structure as well as how they are interpreted. Each node may only have one successor in each dimension and each of these successors is used to interpret the yield of the tree rooted at the node. The representation reflects this in the fact that each node is followed by a list of its successors within parentheses. This can be seen as the adjoining operation with the terms within the parentheses representing the forests which are being combined and the outside label representing either a new sibling or root forest.
The linear form is defined inductively as follows:
This is looking like a good start. A few thoughts.
----
Probably, you should remind the reader of the threaded form for ordinary trees. This introduces the issue of how to interpret the right sibling of the root of a tree, which introduces the idea that the structure really represents linearly ordered forests with the structures that represent a single tree being those in which the root happens to have no sibling. The generalization to arbitrary dimension is straightforward, but you should avoid refering to these as "first child", etc., to begin with. This confuses two distinct concepts: the threaded form, in which there is a successor relationship between a node and the root of each of the lower-dimensional structures that are its successors in the various dimensions, and the observation that we can interpret such a threaded structure as a d-branching 2-dimensional tree, in which the root of the successor in the ith dimension can be taken to be the (d-(i-1))th child.
----
This also seems to be bundling several things into a single paragraph (nearly a single sentence.) First introduce the structure building operation for the threaded structures as an operation that takes d d-dimensional forests (and a label) and combines them under a new node with that label to form another d-dimensional forest. We should note that this combines the usual "add new tree to forest" and "merge forest into singleton forest (i.e., tree)" operations of the 2-d structures, so that a node is simultaneously added to the left edge of a forest and to the root of its subtree. Since this is not the usual conceptualization of the structure building operation for threaded trees, we need to be careful in explaining it. Probably, you should introduce the 2(+label)-ary operation for ordinary threaded trees and then genearlize to the d-ary operation for d-dimensional trees. I think we probably will want to make the point about the i-dimensional roots, but we haven't really said what we mean by that yet and it seems likely that we may have to introduce the frusta to do so---the very complication that we were avioding (although at least here it is not necessary to the intuitive understanding of what is going on). Perhaps we want to save it for later.
----
It would be useful, now, to make the connection between the multidimensional trees and the free algebra of the d-ary combining operation. Fortunately, you don't need to fully understand the algebraic side of this. All you need to do is to note that the linearized trees are just the terms of that algebra, i.e., the fully expanded algebraic expression that was used to build the tree (rather forest). The inductive definition is then immediate and immediately seen to be correct without further justification.
Good stuff. Thanks.
Posted by: Jim at July 1, 2004 04:45 PM