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

Now the statement
returnValue = myTree.getEntry(whitney);
sets returnValue to whitney2 , since it is in the tree and matches whitney . Similarly,
returnValue = myTree.remove(whitney);
returns and removes whitney2 .
Now imagine that the method compareTo uses both the name and identification fields of a
Person object to make a comparison. Since whitney and whitney2 would not be equal accord-
ing to this compareTo , we could add both objects to the tree. Then getEntry(whitney) would
return whitney , and remove(whitney) would remove and return whitney .

Duplicate Entries
25.4

To make our discussion a bit simpler, we insist that a binary search tree contain distinct entries.
Notice that the add method, as specified in SearchTreeInterface , ensures that duplicates are
never added to the tree. In practice, this restriction can be desirable for many applications, but
sometimes it is not. By making a small change to our definition of a binary search tree, we can
allow duplicate entries, that is, multiple entries that are equal according to compareTo .
Figure 25-3 shows a binary search tree in which Jared occurs twice. If we are at the root of this
tree and want to know whether Jared occurs again, it would help to know in which subtree we
should look. Thus, if any entry e has a duplicate entry d , we arbitrarily require that d occur in the
right subtree of e 's node. Accordingly, we modify our definition as follows:
For each node in a binary search tree,

•

The data in a node is greater than the data in the node's left subtree

•

The data in a node is less than or equal to the data in the node's right subtree

Notice that an inorder traversal of the tree in Figure 25-3 visits the duplicate entry Jared immedi-
ately after visiting the original Jared .

FIGURE 25-3

A binary search tree with duplicate entries

Jared

Brittany Megan

Brett Doug Jim Whitney

Jared

With duplicate entries permitted, the add method has less to do. But which entry will getEntry
retrieve? Will the method remove delete the first occurrence of an entry or all occurrences? Exactly
what happens is up to the class designer, but these questions should indicate the complications that
duplicate entries cause. We will not consider duplicate entries any further, and will leave this issue
to you as a programming project. (See Project 1 at the end of this chapter.)