Data Structures and Algorithms with Object-Oriented Design Patterns in C#
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_inline63241 and tex2html_wrap_inline63243. Equivalence of trees is given by

displaymath63239

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

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

int result = obj1.CompareTo(obj2);
The CompareTo method returns a negative number if tex2html_wrap_inline63245; a positive number if tex2html_wrap_inline63247; and zero if tex2html_wrap_inline63249.

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_inline63251 and tex2html_wrap_inline63253 and the relation < given by

equation16593

where tex2html_wrap_inline63251 is either tex2html_wrap_inline62795 or tex2html_wrap_inline63261 and tex2html_wrap_inline63253 is tex2html_wrap_inline63265. 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.

   program16622
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 IComparable interface and, therefore, we use the CompareTo 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_inline63299, where tex2html_wrap_inline63301 is the time needed to compare the objects contained in the nodes of the trees.


next up previous contents index

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