Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Collapsing Find

 

Unfortunately, using the Join algorithm given in Program gif can result in particularly bad trees. E.g., Figure gif shows the worst possible tree that can be obtained. Such a tree is bad because its height is O(N). In such a tree both the worst case and the average case running time for the Find operation is O(N).

   figure29630
Figure: A Degenerate Tree

There is an interesting trick we can play that can improve matters significantly. Recall that the find operation starts from a given node and locates the root of the tree containing that node. If, having found the root, we replace the parent pointer of the given node with a pointer to the root, the next time we do a Find it will be more efficient.

In fact, we can go one step further and replace the parent pointer of every node along the search path to the root. This is called a collapsing find   operation. Doing so does not change the asymptotic complexity of the Find operation. However, a subsequent Find operation which begins at any point along the search path to the root will run in constant time!

Program gif gives the code for a collapsing version of the Find operation. The Find function first determines the root node as before. Then, a second pass is made up the chain from the initial node to the root, during which the parent pointer of each node is made to point at the root. Clearly, this version of Find is slower than the one given in Program gif because it makes two passes up the chain rather than one. However, the running of this version of Find is still O(d), where d is the depth of the node from which the search begins.

   program29839
Program: PartitionAsForest Class Collapsing Find Member Function Definition

Figure gif illustrates the effect of a collapsing find operation. After the find, all the nodes along the search path are attached directly to the root. I.e., they have had their depths decreased to one. As a side-effect, any node which is in the subtree of a node along the search path may have its depth decreased by the collapsing find operation. The depth of a node is never increased by the find operation. Eventually, if we do enough collapsing find operations, it is possible to obtain a tree of height one in which all the non-root nodes point directly at the root.

   figure29849
Figure: Example of Collapsing Find


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.