6.11. Dictionary Implementation Using a BST¶

A simple implementation for the Dictionary ADT can be based on sorted or unsorted lists. When implementing the dictionary with an unsorted list, inserting a new record into the dictionary can be performed quickly by putting it at the end of the list. However, searching an unsorted list for a particular record requires \(\Theta(n)\) time in the average case. For a large database, this is probably much too slow. Alternatively, the records can be stored in a sorted list. If the list is implemented using a linked list, then no speedup to the search operation will result from storing the records in sorted order. On the other hand, if we use a sorted array-based list to implement the dictionary, then binary search can be used to find a record in only \(\Theta(\log n)\) time. However, insertion will now require \(\Theta(n)\) time on average because, once the proper location for the new record in the sorted list has been found, many records might be shifted to make room for the new record.

Is there some way to organize a collection of records so that inserting records and searching for records can both be done quickly? We can do this with a binary search tree (BST). The advantage of using the BST is that all major operations (insert, search, and remove) are \(\Theta(\log n)\) in the average case. Of course, if the tree is badly balanced, then the cost can be as bad as \(\Theta(n)\).

Here is an implementation for the Dictionary interface, using a BST to store the records.

// Dictionary implementation using BST
// This uses KVPair to manage the key/value pairs
class BSTDict implements Dictionary {
  private BST theBST; // The BST that stores the records

  // constructor
  BSTDict() { theBST = new BST(); }

  // Reinitialize dictionary
  public void clear() { theBST = new BST(); }

  // Insert a record
  // k: the key for the record being inserted.
  // e: the record being inserted.
  void insert(Comparable k, Object e) {
    theBST.insert(new KVPair(k, e));
  }

  // Remove and return a record.
  // k: the key of the record to be removed.
  // Return a maching record. If multiple records match "k", remove
  // an arbitrary one. Return null if no record with key "k" exists.
  Object remove(Comparable k) {
    Object temp = theBST.remove(k);
    if (temp == null) return temp;
    else return ((KVPair)temp).value();
  }

  // Remove and return an arbitrary record from dictionary.
  // Return the record removed, or null if none exists.
  Object removeAny() {
    if (theBST.size() == 0) return null;
    Object temp = theBST.remove(((KVPair)(theBST.root.element)).key());
    return ((KVPair)temp).value();
  }

  // Return a record matching "k" (null if none exists).
  // If multiple records match, return an arbitrary one.
  // k: the key of the record to find
  Object find(Comparable k) {
    Object temp = theBST.find(k);
    if (temp == null) return temp;
    else return ((KVPair)temp).value();
  }

  // Return the number of records in the dictionary.
  int size() {
    return theBST.size();
  }
}

TDDD86 Fall 2020

Chapter 6 Binary Trees

6.11. Dictionary Implementation Using a BST¶