Spines and Spine Heads

In order to determine the string yield of higher dimensional trees, the trees need to be marked with local yield heads to disambiguate the construction of the yield. These heads create a spine that represents the central construction of the tree.

External Representation

To represent the head locations in the external tree form, we add a number to all the labels in the tree. This number is the distance of the head down the spine from the node. A zero indicates that the node itself is the head. A one would mean that to find the head (using a 3-d tree for an example), we must find the head of the 2-d successor. A two means we must find the head of the 2-d successor and then find the head of that's 2-d successor.

Internal Representation

We found it best to store both the number indicating where the head is and a pointer to the head. The pointer is useful for our algorithms, while the number is useful for input and output.

| CS Home | Earlham College | WebDB | Earlham Mail | Earlham Libraries | Word Online |

Copyright © 1996-2002 by Earlham College Computer Science Department.
If you're curious about why we copyright, see Peter Suber's Why Copyright Web Documents?.

Looking for something that's not here? Contact:
Last updated: Monday, 26-Jul-2004 14:22:53 EST
#837