I've moved the official due date back since this assignment turned out to be quite tricky. If you're still having trouble with it, the pseudo-code which I handed out in class may help (it's available on pascal in the folder /users/faculty/mikes/126 in the file pseudo2-3.txt).

NOTE: I had a mistaken reference to vtop in the pseudocode for mergeUp which I just fixed in the file. Also, at the end of mergeUp, I had two lines for newTop.parent = and changeChild in which inNode.parent should really be parent.parent.

GOAL: Using any programming language with which you are comfortable, write a program to construct a 2-3 tree whose entries are strings (in alphabetical order). The trees are described in Section 6.3 of the textbook. Use your program to build trees for each of the data files words1.txt , words2.txt , and words3.txt found in the folder /users/faculty/mikes/126 on pascal (you can also save the files from the links on this page). Your program should not insert duplicate words. That is, either check if a word is already in the tree before inserting it, or have an insert call just leave the tree unchanged if the word is already there.

For each of the input files you should report:

1. Number of entries in the final tree.
2. Height of the tree.
3. The number of 2-nodes and 3-nodes in the tree.

METHOD: If you are writing in Java, you'll probably want to define a general class Node and then have two subclasses, TwoNode and ThreeNode. This will allow you to declare the children of a node as type Node without knowing if they're 2 or 3-nodes.

To collect the required statistics, it might be simplest to write a few recursive tree walk routines. For instance, to count the number of 2-nodes in the tree, you recursively count in the children of the root node and then add one or not depending on whether the root node is a 2-node. NOTE: In Java, the instanceof operator will let you check which type of node you have. For example:

   Node n;

   ... some code which assigns a value to n ...

   if (n instanceof TwoNode)
      System.out.println("Two node"):
   else
      System.out.println("Three node"):

HAND-IN: The reports on the three input files and the source code for your program.