Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Comparing Trees

A problem which is relatively easy to solve is determining if two trees are equivalent. Two trees are equivalent   if they both have the same topology and if the objects contained in corresponding nodes are equal. Clearly, two empty trees are equivalent. Consider two non-empty binary trees tex2html_wrap_inline62974 and tex2html_wrap_inline62976. Equivalence of trees is given by

displaymath62972

A simple, recursive algorithm suffices to test the equivalence of trees.

Since the BinaryTree class is ultimately derived from the AbstractObject class introduced in Program gif, it must provide a compareTo method to compare binary trees. Recall that the compareTo method is invoked by the compare method when the latter is used to compare two objects, say obj1 and obj2 like this:

int result = obj1.compare (obj2);
The compareTo method returns a negative number if tex2html_wrap_inline60166; a positive number if tex2html_wrap_inline60168; and zero if tex2html_wrap_inline62982.

So what we need is to define a total order  relation on binary trees. Fortunately, it is possible to define such a relation for binary trees provided that the objects contained in the nodes of the trees are drawn from a totally ordered set.

Theorem  Consider two binary trees tex2html_wrap_inline62984 and tex2html_wrap_inline62986 and the relation < given by

equation16479

where tex2html_wrap_inline62984 is either tex2html_wrap_inline62528 or tex2html_wrap_inline62994 and tex2html_wrap_inline62986 is tex2html_wrap_inline62998. The relation < is a total order.

The proof of Theorem gif is straightforward albeit tedious. Essentially we need to show the following:

The details of the proof are left as an exercise for the reader (Exercise gif).

Program gif gives an implementation of the compareTo method for the BinaryTree class. This implementation is based on the total order relation < defined in Theorem gif. The argument of the compareTo method can be any Object instance. However, normally that object will be another BinaryTree instance. Therefore, the cast on line 10 is normally successful.

   program16508
Program: BinaryTree class compareTo method.

The compareTo method compares the two binary trees this and arg. If they are both empty trees, compareTo returns zero. If this is empty and arg is not, compareTo returns -1; and if arg is empty and this is not, it returns 1.

Otherwise, both trees are non-empty. In this case, compareTo first compares their respective roots. We assume that the roots implement the Comparable interface defined in Program gif and, therefore, we use the compare method to compare them. If the roots are equal, then the left subtrees are compared. Then, if the roots and the left subtrees are equal, the right subtrees are compared.

Clearly the worst-case running occurs when comparing identical trees. Suppose there are exactly n nodes in each tree. Then, the running time of the compareTo method is tex2html_wrap_inline63032, where tex2html_wrap_inline60522 is the time needed to compare the objects contained in the nodes of the trees.


next up previous contents index

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