(Appended to the previous post)
It would be useful to develop some sort of concept for the heights of these
trees. Using our approach, each node could be annotated with its height in
each dimension. We define the i-dimensional height of a node to be the maximum
depth under that node in an i-dimensional structure.
In order to calculate the height of a particular node for the i dimension, we
must take the maximum of the heights in that dimension of all the node's
i-dimensional children -- the nodes reachable by following zero or more
(j < i)-dimensional links from its i-dimensional successor -- and add one. For
the purpose of this calculation, the empty tree is taken to have a height of
-1.
The downside to this calculation is that it requires us to traverse an entire
(i-1)-dimensional forest in order to determine the i-dimensional height of a
single node. By annotating the nodes using a pair of heights per dimension
instead, we can propagate all the necessary information up the tree and thereby
skirt this problem. In each pair, the first i-dimensional height (the general
height) represents the height of this node from the perspective of a parent --
that is, the i-dimensional height obtained by following any links of dimension
≤ i. The second i-dimensional height (the specific height) represents the
actual height of this node -- that is, the i-dimensional height obtained by
following the node's i-dimensional link followed by any links of dimension ≤
i.
When a new node is constructed, its specific height in dimension i is
determined simply by taking the general height of dimension i for it's
i-dimensional successor, and adding 1 to that value. For the purposes of this
calculation (and for the calculation of the general heights as well), the
height of the empty tree is taken to be -1 in all dimensions.
In contrast, when propagating the general heights to a new node along an
i-dimensional link, two things happen. First, the general height of dimension
i is increased by 1, as in the calculation of the specific height for dimension
i. Second, since we are following an i-dimensional link, all general heights
for dimensions less than i are zeroed out.
Since a node may potentially be formed using links in more than one dimension,
this process must be carried out independently for each successor. The new
general height in each dimension is then obtained by taking the maximum value
in that dimension over all of the node's successors.