CSC152 2005F, Class 46: Implementing Dictionaries with Binary Search Trees

Admin:
* We'll try a lab today.
* Any announcements?
  * Basketball game Tuesday at 5 pm
  * Women at 7 pm

Overview:
* About binary search trees
* Lab
* Reflection

Review: Dictionary
* Philosophy: Like arrays, but can be indexed by things other than numbers (usually strings) ; the indices are called "keys"
* Applications: Many
* Methods:
  ValueType get(KeyType key) ; usually "String" as parameter, and whatever type of thing we're storing as ValueType
    get throws exception if the key isn't there
  ValueType put(KeyType key, ValueType element) - returns the old value stored there; returns null if no value previously stored
  size()
  [remove]?
* Design decision: For put, what happens if the key is already in the dictionary?
  * Replace the entry - Keeps it like arrays
  * Throw an exception - and support a separate replace method
  * Specify the decision when you create the dictionary

Implementing dictionaries: Binary Search Trees
* Use divide-and-conquer strategy: Get a tree
* Binary search tree
  * Each node in the tree has four parts
    key
    value
    left subtree - entries with smaller keys
    right subtree - entries with larger keys
  * Smaller and larger are determined by a separate comparator
  * How do you search for existing elements?
    * Look at the top.  If the keys match, you're done, return the value
    * If the keys don't match, look in the appropriate half (as in binary search)
    * When you fall off of the tree, throw an exception
  * How do you add new elements?
    * Keep moving left or right (depending on comparison) until you run off the tree; then create a new node and make it the appropriate child of the node you last visited.

    The lab emphasizes how we turn all of this into code.