O'Reilly logo

Think Data Structures by Allen B. Downey

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required