A Binary Search Tree Implementation - Data Structures and Abstractions with Java - page 628

25.3

Understanding the specifications. These specifications allow us to use a binary search tree in the
implementation of the ADT dictionary, as you will see later in this chapter. The methods use return
values instead of exceptions to indicate whether an operation has failed. The return value for a suc-
cessful retrieve, add, or remove operation, however, might seem strange at first. For example, it
appears that the retrieve operation, getEntry , returns the same entry it is given to find. In fact,
getEntry returns an object that is in the tree and that matches the given entry according to the
entry's compareTo method. Let's look at an example that adds entries and then retrieves them.
Imagine a class Person that has two strings as data fields representing the person's name and
identification number. The class implements the Comparable interface, and so has a compareTo
method. Suppose that compareTo bases its comparison only on the name field. Consider the follow-
ing statements that create and add to a binary search tree:
SearchTreeInterface<Person> myTree = new BinarySearchTree<Person>();
Person whitney = new Person("Whitney", "111223333");
Person returnValue = myTree.add(whitney);
Following the add operation, returnValue is null , since whitney was not in the tree already. Now
suppose we try to add another Whitney , who has a different identification number:

Person whitney2 = new Person("Whitney", "444556666");
returnValue = myTree.add(whitney2);
Since whitney and whitney2 have the same names, they are equal. That is, the expression
whitney.compareTo(whitney2) is zero. Therefore, the add method will not add whitney2 to the
tree. Instead it replaces whitney with whitney2 and returns whitney , the original object in the
tree, as Figure 25-2 illustrates. We can think of this as a way to change the identification num-
ber of a person named Whitney .

FIGURE 25-2

Adding an entry that matches an entry already in a binary search tree

(a)

Before myTree.add(whitney2) executes

Whitney 444556666

whitney2

Whitney 111223333

whitney

myTree

After myTree.add(whitney2) executes (b)

Returned from add

Whitney 111223333

whitney

Whitney 444556666

whitney2
myTree