Trees - Data Structures and Problem Solving Using Java - page 663

figure 18.14
Result of a naive
merge operation:
Subtrees are shared.

root

x

t1.root t2.root

the root , after verifying that the tree is not empty. An alternative traversal
strategy that can be implemented is level-order traversal. We discuss these tra-
versal routines in Section 18.4. Routines to make an empty tree and test for
emptiness are given, with their inline implementations, at lines 35 to 38, as
are routines to compute the tree's size and height. Note that, as size and
height are static methods in BinaryNode , we can call them by simply using
BinaryNode.size and BinaryNode.height .
The last method in the class is the merge routine, which uses two trees— t1
and t2 —and an element to create a new tree, with the element at the root and
the two existing trees as left and right subtrees. In principle, it is a one-liner:

The merge routine is
a one-liner in prin-
ciple. However, we
must also handle
aliasing, ensure
that a node is not in
two trees, and
check for errors.

We set the original
trees' root to null
so that each node
is in one tree.

root = new BinaryNode<AnyType>( rootItem, t1.root, t2.root );

If things were always this simple, programmers would be unemployed. Fortu-
nately for our careers, there are a host of complications. Figure 18.14 shows
the result of the simple one-line merge . A problem becomes apparent: Nodes in
t1 and t2 's trees are now in two trees (their original trees and the merged
result). This sharing is a problem if we want to remove or otherwise alter sub-
trees (because multiple subtrees may be removed or altered unintentionally).

The solution is simple in principle. We can ensure that nodes do not
appear in two trees by setting t1.root and t2.root to null after the merge .
Complications ensue when we consider some possible calls that contain
aliasing:

If the two input
trees are aliases,
we should disallow
the operation
unless the trees
are empty.

t1.merge( x, t1, t2 );
t2.merge( x, t1, t2 );
t1.merge( x, t3, t3 );

The first two cases are similar, so we consider only the first one. A diagram of
the situation is shown in Figure 18.15. Because t1 is an alias for the current
object, t1.root and root are aliases. Thus, after the call to new , if we execute
t1.root=null , we change root to the null reference, too. Consequently, we
need to be very careful with the aliases for these cases.