Java Reference
In-Depth Information
6.2
The Parent Pointer Implementation
Perhaps the simplest general tree implementation is to store for each node only a
pointer to that node's parent. We will call this the parent pointer implementation.
Clearly this implementation is not general purpose, because it is inadequate for
such important operations as finding the leftmost child or the right sibling for a
node. Thus, it may seem to be a poor idea to implement a general tree in this
way. However, the parent pointer implementation stores precisely the information
required to answer the following, useful question: “Given two nodes, are they in
the same tree?” To answer the question, we need only follow the series of parent
pointers from each node to its respective root. If both nodes reach the same root,
then they must be in the same tree. If the roots are different, then the two nodes are
not in the same tree. The process of finding the ultimate root for a given node we
will call FIND.
The parent pointer representation is most often used to maintain a collection of
disjoint sets. Two disjoint sets share no members in common (their intersection is
empty). A collection of disjoint sets partitions some objects such that every object
is in exactly one of the disjoint sets. There are two basic operations that we wish to
support:
(1) determine if two objects are in the same set, and
(2) merge two sets together.
Because two merged sets are united, the merging operation is called UNION and
the whole process of determining if two objects are in the same set and then merging
the sets goes by the name “UNION/FIND.”
To implement UNION/FIND, we represent each disjoint set with a separate
general tree. Two objects are in the same disjoint set if they are in the same tree.
Every node of the tree (except for the root) has precisely one parent. Thus, each
node requires the same space to represent it. The collection of objects is typically
stored in an array, where each element of the array corresponds to one object, and
each element stores the object's value. The objects also correspond to nodes in
the various disjoint trees (one tree for each disjoint set), so we also store the parent
value with each object in the array. Those nodes that are the roots of their respective
trees store an appropriate indicator. Note that this representation means that a single
array is being used to implement a collection of trees. This makes it easy to merge
trees together with UNION operations.
Figure 6.4 shows the parent pointer implementation for the general tree, called
ParPtrTree
. This class is greatly simplified from the declarations of Figure 6.2
because we need only a subset of the general tree operations. Instead of implement-
ing a separate node class,
ParPtrTree
simply stores an array where each array
element corresponds to a node of the tree. Each position i of the array stores the
value for node i and the array position for the parent of node i. Class
ParPtrTree
