Unfortunately, using the `Join` algorithm given in Program
can result in particularly bad trees.
E.g., Figure 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*).

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 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 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.

**Program:** `PartitionAsForest` Class Collapsing `Find` Member Function Definition

Figure 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.

**Figure:** Example of Collapsing Find

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