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

25.46

The Dictionary methods. The method add encapsulates the given search key and value into an
instance of Entry that it passes to BinarySearchTree 's add method. It then uses the entry that this
method returns to form its own return value. Dictionary 's add method has the following implementation:

public V add (K key, V value)
{

Entry<K, V> newEntry = new Entry<K, V>(key, value);
Entry<K, V> returnedEntry = bst.add(newEntry);
V result = null ;
if (returnedEntry != null )
result = returnedEntry.getValue();
return result;
} // end add
Both remove and getValue have implementations that are similar to add 's. Since these meth-
ods have only a search key as a parameter, the instances of Entry that they form encapsulate the
key and a null value. For example, remove begins as

public V remove(K key)
{

Entry<K, V> findEntry = new Entry<K, V>(key, null );
Entry<K, V> returnedEntry = bst.remove(findEntry);
and ends just like the method add . The implementation of the method getValue is identical to that
of remove , except that it calls getEntry from BinarySearchTree instead of remove .
We can implement the methods getSize , isEmpty , contains , and clear by calling appropriate
methods of BinarySearchTree . We leave these to you as exercises.

Question 13 Implement each of the Dictionary methods getSize , isEmpty , contains , and
clear by calling methods of BinarySearchTree .

Question 14 Write another implementation of the method contains by invoking Dictionary 's
method getValue .

25.47

The iterators. DictionaryInterface specifies two methods that return iterators. The method
getKeyIterator returns an iterator that accesses the search keys in sorted order; getValueIterator
returns an iterator that provides the values belonging to these search keys.
For example, getKeyIterator has the following implementation:

public Iterator<K> getKeyIterator()
{

return new KeyIterator();
} // end getKeyIterator
The class KeyIterator is internal to Dictionary and uses the method getInorderIterator from
BinarySearchTree . It has the following implementation:

private class KeyIterator implements Iterator<K>
{

Iterator<Entry<K, V>> localIterator;
public KeyIterator()
{

localIterator = bst.getInorderIterator();
} // end default constructor