Think Data Structures

Chapter 13. Binary Search Tree

This chapter presents solutions to the previous exercise, then tests the performance of the tree-backed map. I present a problem with the implementation and explain how Java’s TreeMap solves it.

A Simple MyTreeMap

In the previous exercise I gave you the outline of MyTreeMap and asked you to fill in the missing methods. Now I’ll present a solution, starting with findNode:

private Node findNode(Object target) {
    // some implementations can handle null as a key, but not this one
    if (target == null) {
            throw new IllegalArgumentException();
    }

    // something to make the compiler happy
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) target;

    // the actual search
    Node node = root;
    while (node != null) {
        int cmp = k.compareTo(node.key);
        if (cmp < 0)
            node = node.left;
        else if (cmp > 0)
            node = node.right;
        else
            return node;
    }
    return null;
}

findNode is a private method used by containsKey and get; it is not part of the Map interface. The parameter target is the key we’re looking for. I explained the first part of this method in the previous exercise:

• In this implementation, null is not a legal value for a key.

• Before we can invoke compareTo on target, we have to typecast it to some kind of Comparable. The type wildcard used here is as permissive as possible; that is, it works with any type that implements Comparable and whose compareTo method accepts K or any supertype of K.

After all that, the actual search is relatively simple. We initialize ...