Hyperbolic Tree of Similar Pages

4.2 Search/Rotation Algorithm
The application supports the navigation of the hyperbolic tree via a MakeRoot method. MakeRoot makes one of the non-root nodes the root of the tree through a series of rotation/growth iterations. When the user invokes MakeRoot on a node, nodeA, MakeRoot is recursively called on the parent of nodeA, all the way up to the root node. This eventually makes the nodeA the root of the tree.
Consider the example illustrated in Figure 1. In Figure 1.1, we start off with a tree of depth 3 and fanout 3. Now suppose MakeRoot is called on node 1. The tree is rotated to make node 1 the parent of node 0, and node 0 the child of node 1, as shown in Figure 1.2. At this point, the rotation is complete. However, the depth of the tree is no longer uniform, so we need to grow the nodes 4, 5, and 6. Nodes 7, 9, 9, 10, 11 and 12 are then pruned from the tree because they exceed the required depth. Note that these nodes are only hidden, but not actually removed from the data structures, so they do not need to be rebuilt if the tree is rotated back to its original form. Note that the number of children of a node may be more than the specified fanout due to a rotation operation.

During a rotation, one or more child-parent relationship in the tree is reversed. This is only strictly correct when the reflexivity assumption of the similarity relationship mentioned earlier is true. We make this assumption because without it, the tree would become disjoint after a rotation. We feel it is important to keep the tree intact to allow the user to rotate the tree back into its original form later on.