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

25.43

In what order should we add the entries? Jared is the root of the tree in Figure 25-13a, so let's add
Jared first. Next add Brittany and then Brett and Doug . Finally, add Megan , Jim , and Whitney .
While it should be clear that by using this order we get the tree in Figure 25-13a, how do we deter-
mine the order ahead of time? Looking at our alphabetical set of names, notice that Jared is exactly
in the middle. We add Jared first. Brittany is in the middle of the left half of the data set, so we add
Brittany next. The halves that Brittany defines each contain only one name, so we add them next.
We repeat this process with the names that occur after Jared —that is, the right half of the data set.
We shouldn't have to do this much work! In fact, if we add data to a binary search tree in ran-
dom order, we can expect a tree whose operations are O(log n ). It probably will not be the shortest
tree we could create, but it will be close.
The operations of a binary search tree ensure that the tree remains a binary search tree. Unfor-
tunately, they do not ensure that the tree remains balanced. Chapter 27 looks at search trees that are
responsible for maintaining their balance, and hence their efficiency.

An Implementation of the ADT Dictionary

25.44

We can use the ideas developed thus far in this chapter to implement the ADT dictionary. Recall
from Chapter 19 that a dictionary stores search keys and their associated values. For example, sup-
pose that you want a dictionary of names and telephone numbers. In terms of the ADT dictionary,
the name could be the search key and the telephone number could be the corresponding value. To
retrieve a telephone number, we would provide a name, and the dictionary would return its value.
Here is the interface for a dictionary as given in Segment 19.4, but without the comments:

import java.util.Iterator;
public interface DictionaryInterface<K, V>
{

public V add(K key, V value);
public V remove(K key);
public V getValue(K key);
public boolean contains(K key);
public Iterator<K> getKeyIterator();
public Iterator<V> getValueIterator();
public boolean isEmpty();
public int getSize();
public void clear();
} // end DictionaryInterface

Earlier in this topic we saw several implementations of the ADT dictionary. A dictionary
implementation that uses a balanced search tree to store its entries can be an attractive alternative to
these implementations. As an example of such an implementation, we will use a binary search tree
here, even though it might not remain balanced after additions or removals. Chapter 27 presents
search trees that are always balanced and could be used instead to implement the dictionary.

25.45

The data entries. We need a class of data objects that will contain both a search key and an associ-
ated value. A class Entry —similar to the class we used in the array-based implementation of the
ADT dictionary in Chapter 20—is suitable for our purpose. Here, we make the class Comparable
by defining the method compareTo . This method compares two instances of Entry by comparing
their search keys. Thus, the search keys of this dictionary must belong to a Comparable class.