• Dr. Taylor's Page
• Calendar
• Policy
• Resources

Maps

It's time for a new ADT: the Map. Every piece of data in a Map has two parts: a key and an element. We find the element, by searching for the key. For example, a dictionary is a map: we look up the word (the key), and get the definition (the element). So is a phone book: we look up the name, and get the phone number and address. In 210, you did a lab where you counted how many times words appeared in a document; the word was the key, and the count was the element. The important thing is that the keys be sortable (like numbers, or strings), so that we can be smart about storing them.

Suppose we were interested in creating a system to look up a mid's grades, which wasn't as terrible as MIDS. First, you might make a class that can contain all of a single student's grades (we'll call it Grades, because we're creative). Then, you want it to be searchable by alpha.

Operations of a Map

The operations are:

• insert(k,e): Insert element e with key k.
• get(k): Return the element associated with key k.

Oftentimes, a Map also has a remove(k) method, but in the interests in covering more ground, we're not going to talk much about that in this course. There are a couple reasons for this. The first is that remove is, by far, the least commonly used of the Map methods. The fact that it's done rarely means that oftentimes, the data isn't actually removed from the structure, it's just "marked" as removed, but keeps its place in the data structure. Because it happens rarely, there is little penalty for this. The second reason is that it can take a lot of time to learn, and there isn't a tremendous amount of educational benefit in going through the exercise.

We're going to spend a lot of time on Maps, implementing them with new data structures. For now, a map can be implemented with an array (either in sorted order by key, or unsorted), a linked list (again, either sorted by key, or unsorted), or Binary Search Tree (organized by key). Note that a Node in a LL or BST will now contain not a single data field, but both the key and the element. For an array, you would need to combine the key and element together into a single object, like the one below.

public class AlphaGradePair implements Comparable<AlphaGradePair> {
  private int alpha;
  private Grade grades;
  public AlphaGradePair(int alpha, Grade grades) {
    this.alpha=alpha;
    this.grades=grades;
  }
  public int getKey() {
    return alpha;
  }
  public Grade getGrades() {
    return grades;
  }
  public int compareTo(AlphaGradePair other) {
    if (alpha < other.getKey())
      return -1;
    else if (alpha > other.getKey())
      return 1;
    return 0;
  }
}

How would you implement these methods for each of these data structures?

For now, we know that the height of a tree is somewhere between log(n) and n. If only we had a way to guarantee the tree would be balanced! If only...