TreeMaps + SearchTreeMap

TreeMaps + SearchTreeMap
— print (last updated: Oct 16, 2009) — print

Maps

A map is something which associates one set of things called keys, to a set of things called values. The general name for any such association is a relation. The important point about a map is that the relation is functional in that a key never appears twice in the relation (with different values).

Other names for a map are partial function (mathematics) association list (computer science). Sometimes the term hash refers to a map, but hash connotes a specific implementation of a map which we'll see later.

Java uses the generic interface Map<K,V> as the basis of map implementations. The generic type K refers to the key type and V refers to the value type. The important member functions are these:

put(key,value);      add a key/value pair or replace value for existing key
get(key);            retrieve value for a given key (null if no such key)

Like the Set interface, the Map interface has stronger extensions: SortedMap<K,V> and NavigableMap<K,V>. The Map implementation of interest to us in this document is TreeMap<K,V>, which is an implementation of NavigableMap<K,V>.

TreeMap

The implementation of a TreeMap is like that of a TreeSet. The only difference is that the nodes hold a (key,value) pair instead of single data value. A key, which can occur only once in the tree takes on the role of the element in TreeSet. In a binary tree implementation, we maintain the following ordering property at each node:

keys of all
nodes in the
left subtree
of node n < key at
node n < keys of all
nodes in the
right subtree
of node n

Basic Demo Program

The NetBeans project used here is TMapDemo. The Main class below provides one simple test program uses a TreeMap object as a SortedSet element:

package tmapdemo;

import java.util.*;
//import tmap.SearchTreeMap;

public class Main {
  public static void main(String[] args) {
    main1(args);
  }

  public static void main1(String[] args) {
    Map<String, Integer> age = new TreeMap<String, Integer>();

    // size
    System.out.println("size=" + age.size());

    // toString
    System.out.println(age);

    // put
    System.out.println(age.put("john", 34));
    System.out.println(age.put("john", 35));
    System.out.println(age.put("paul", 22));
    System.out.println(age.put("erin", 41));
    System.out.println(age.put("bob", 17));
    System.out.println(age.put("bill", 25));
    age.put("me", null);

    // size
    System.out.println("size=" + age.size());

    // toString
    System.out.println(age);

    // entrySet.iterator
    System.out.println("\niterate using entrySet");
    for (Map.Entry<String, Integer> entry : age.entrySet()) {
      System.out.println("entry: " + entry);
      System.out.println(
        "\tkey: " + entry.getKey() + ", value: " + entry.getValue());
    }

    // get
    System.out.println("\njohn: " + age.get("john"));
    System.out.println("jill: " + age.get("jill"));

    // remove
    System.out.println("\nremove bob: " + age.remove("bob"));
    System.out.println("remove bob: " + age.remove("bob"));
    System.out.println(age);

    // keySet
    //
    // here we traverse the entire tree inorder to get the keys, and then
    // for each key we must traverse from the root to get the value,
    // so this is less efficient compared to the former method

    System.out.println("\niterate using keySet: less efficient!");
    for (String key : age.keySet()) {
      System.out.println("\tkey: " + key + ", value: " + age.get(key));
    }
  }
}

Test-drive

To "test-drive", replace TreeMap by SearchTreeMap. Only you won't get very far because the most basic operation, put, is not yet implemented.

Adapters

Create the Java Class:

Class Name: MapAdapter
package:    map

Then insert the following content ( click to show )

Create the Java Class:

Class Name: NavMapAdapter
package:    map

Then insert the following content ( click to show ).

The implementation of the search tree map below also requires the set.SetAdapter class used in the TreeSet + SearchTreeSet document. You can either install it directly from the code here ( click to show )

or perhaps simply copy the entire set package from the TSetDemo project.

SearchTreeMap

Create the class:

Class Name: SearchTreeMap
package:    tmap

Then insert the following content ( click to show )

This "implementation" is just a sketch since most of the basic functions are not actually implemented.

SearchTreeMap Discussion

It's useful to compare what we're doing here with the SearchTreeSet class discussion in the TreeSets + SearchTreeSet document. The nodes are defined by this inner class:

  private class Node {
    K key;
    V value;
    Node left, right;

    Node(K key, V value, Node left, Node right) {
      this.key = key;
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }

The data members of our class are the same as in SearchTreeSet:

  private Node root = null;
  private int size = 0;
  private Comparator<? super E> cmp = null;

The put function

The Map-based put function replaces the Set-based add function. The suggestion in the code is to make the public put(K key, V value) function call the private helper function of the same name:

  private Node put(K key, V value, Node n,
                   AtomicBoolean found, AtomicReference<V> oldvalue) {
    throw 
      new UnsupportedOperationException("you have to implement");
  }

  public V put(K key, V value) {
    AtomicBoolean found = new AtomicBoolean();
    AtomicReference<V> oldvalue = new AtomicReference<V>();

    root = put(key, value, root, found, oldvalue);

    if (found.get()) {
      return oldvalue.get();
    } else {
      ++size;
      return null;
    }
  }

The public one is implemented fully subject to the completion of the private function's implementation. The code which needs to be written follows along the exact same lines as in the TreeSet's

  private Node add(E elt, Node n, AtomicBoolean found);

The primary difference is what happens if the key is found. For add, we did nothing other than report that it was found through the AtomicBoolean object. For put, when you find a matching key, you have to replace the old node's value with the new value and send the old value back. This is the reason we need the extra AtomicReference<V> parameter: it gives us the ability to pass back the old value.