Class 41: Dictionaries and Binary Search Trees

Held Monday, April 17, 2000

Overview

Today we move on to a new kind of ADT, the Dictionary. You may note some similarities between dictionaries and other ADTs we've discussed, such as the array.

Notes

• The MathLAN was down while I was prepping class, so I may not have things as organized as I'd like.
  • Because of the downtime, I did not have a chance to look over your project components.
• Upcoming events:
  • Monica Neagoy's talk tonight at 7:30 in Harris.
  • Thursday night's Africana studies conference
  • May 1 at lunch: Demos!
• Are there questions on assignment 5?
• I realize last week had an unpleasant workload. This week should be better.
  • HW5 is shorter than HW4
  • Project work is not due until next Tuesday.
• Since preregistration is fast approaching, I've been asked to discuss Math and CS courses that you might consider. We'll spend a few minutes on these subjects.
• More prospies on Friday!

Contents

• Linear Structures and Puzzle Solving
• Dictionaries
  • Applications of Dictionaries
• Dictionaries vs. Databases

Summary

• Dictionaries, Defined
• Simple Implementation: Association Lists
• Due:
  • Java Plus Data Structures, Chapter 9, Dictionaries
  • Project, Phase 4: Draft implementations of classes

Linear Structures and Puzzle Solving

• We ended Fridays class with an algorithm for solving puzzles.
• Your question for today was How do the linear structures we've developed help us with this algorithm?
• Here's a hint; it's a reformation of the algorithm

  public boolean solvable(Puzzle p)
  {
    // Prepare the "tree" of puzzles to test.
    PuzzleSet leftToTest = new PuzzleSet();
    // Keep track of which ones we've looked at.
    PuzzleSet checked = new PuzzleSet();
  
    // Start with the one puzzle we have.
    leftToTest.add(p);
    checked.add(p)_;
  
    // Keep going until we run out of puzzles
    while (!leftToTest.isEmpty()) {
      // Grab a puzzle
      Puzzle nextAttempt = leftToTest.get();
      // Is it solved?  If so, the initial puzzle is solvable.
      if (nextAttempt.solved())
        return true;
      // Otherwise, consider all neighboring puzzles 
      PuzzleList nextPuzzles = nextAttempt.nextPuzzles();
      for each possibility in nextPuzzles
        if (!checked.contains(possibility)) {
          leftToTest.add(possibilty);
          checked.add(possibility);
        }
      } // for
    } // while
  
    // Never found a solution.  There is none.
    return false;
  } // solvable(Puzzle)
  

• I look forward to your answers. Once I have yours, I'll give you some of my own.

Dictionaries

• In our investigation of vectors and arrays, we've seen structures that collect objects in which the objects can be indexed by numbers.
• Are there other ways to index collections? Yes, we could index collections by objects (Strings, Integers, whatever).
• Collections of objects indexed by objects are called dictionaries. Some people also refer to them as keyed tables.
• Some more terminology:
  • The objects we're using as indices are called keys.
  • The objects we're looking up are called values.

Applications of Dictionaries

• Why do we do we want dictionaries? They make many tasks more convenient.
• Keeping track of objects we've seen. If an object is an index in the dictionary, we've seen it; if it's not an index in the dictionary, we haven't seen it. This would be helpful for our puzzle solver from an earlier class.
• Counting things We can use the dictionary to associate a counter with each object; when you see another copy, increment the counter.
• Databases. There are a number of techniques for implementing and thinking about databases. Dictionaries provide a simple mechanism for single-keyed databases.

• How do we do build dictionaries? There are a number of techniques, including linked lists of key/value pairs. and won't worry about how they work. Later, we'll look at how to build them.
• What features do we need in a dictionary? Some are similar to those we need for vectors.
  • Add something to the dictionary (requires a key and value).
  • Look up something in the dictionary (requires a key, returns a value).
  • Remove something from the dictionary.
• Others correspond more to the different structure of dictionaries.
  • List/iterate all the keys in the dictionary.
  • List/iterate all the values in the dictionary.

Dictionaries vs. Databases

• Note that dictionaries are not the same as databases.
• Why not? There are a number of reasons.
• Dictionaries have a single key, and that key provides the only way to access information.
  • Databases may have multiple keys. You may also access information using other fields. For example, while a database may be keyed by ID#, you might still be able to search by name.
• A dictionary returns a single object given a request.
  • A database may return multiple objects (e.g., all the students with a B).