CPSC 220 Fall 2004
Program 2: A Simple Dictionary

• The dictionary should be implemented using a binary search tree (BST). A BST is a special case of a binary tree, so first write a BinaryTree class with the following interface:
  • BinaryTree() -- creates an empty binary tree
  • BinaryTree(Object item) -- creates a binary tree with item in the root node and empty left and right subtrees.
  • BinaryTree(Object item, BinaryTree left, BinaryTree right) -- creates a binary tree with item in the root node and with left and right as the left and right subtrees, respectively.
  • Iterator iteratorPreOrder() -- returns an Iterator that performs a preorder traversal of the tree's nodes.
  • Iterator iteratorInOrder() -- returns an Iterator that performs an inorder traversal of the tree's nodes.
  • Iterator iteratorPostOrder() -- returns an Iterator that performs a postorder traversal of the tree's nodes.
  Note that this is just three constructors and three iterators -- so far all you can do is make a tree and get all of its elements. As we discussed in class, it's hard to do much more without knowing something about the structure of the tree. Write a little test program to test these methods.

• Write a BST class that extends BinaryTree. BST should have the following interface:
  • boolean contains(Comparable item) -- returns true if the given item is in the tree, false otherwise.
  • void insert(Comparable item) -- inserts the given item into the tree.
  Write a little program to test these methods. Note that you can use the traversals to see if the tree is getting built correctly.

• Write a driver that takes a filename and uses a BST to create a dictionary from the words (alphanumeric tokens) in the file. Skip over any non-alphanumeric tokens.After creating the dictionary, your driver should enter an interactive loop in which it asks the user for a word and then says "Found" or "Not Found".

• Run your program on some small files, then try it on /usr/share/dict/linux.words, which is an online dictionary file of about 45,000 words. You will probably find that its performance is unsatisfactory. You can explore this a little more using the Java method long System.currentTimeMillis(), which returns the current system time in milliseconds. Insert appropriate calls to this method and run your program on smaller versions of linux.words to find the time required to build the BST for the first 1000 words, then for the first 2000 words, then for the first 4000 words, then for the first 8000 words. In each case also find the time to do a worst-case search (think about how to produce this time.) Record both the build and search times and interpret the results.

  Since you have the entire file before you start building the BST, you can modify the order in which you enter the words. Think about how to do this, then write a second driver that is just like the first except that it changes the order in which the words are inserted to significantly improve performance. Keep your same timing tests in place, and again record and discuss the results.

  What to turn in

  Turn in hardcopy of your BTNode, BinaryTree and BST classes and corresponding interfaces, both of your drivers, and your recorded times and discussions of these times (these must be typed). E-mail your programs and writeups to me with cpsc220 prog2 in the subject.