Written portion

Do the following exercises:

1. Exercise R-9.6 from the book.
2. Exercise R-10.17 from the book and show your work. In addition, do
   • c. Insert the same keys into an initially empty splay tree.
3. Draw the trees that result from removing 12, 22, and 18, in that order, from the final (2,4)-tree, red-black tree, and splay tree of the above problem. Show the tree that results from each of the deletions.
4. Exercise R-10.20 from the book.
5. Exercise R-10.24 from the book.

Programming portion

You are to implement one of the balanced search trees: an AVL-tree, splay tree, (2,4)-tree, or red-black tree. The choice of which to implement is up to you.

You are to modify the PhoneDirectory class you created in Labs 1, 3, 4, 5, 6. Change the class to store the PhoneEntrys in the balanced search tree you created. You should make the key of the entry be the last name. You may assume that each last name in the directory is unique.

You should change the methods of the PhoneDirectory class as follows:

• The constructor should now create an empty tree.

• void add(String lastName, String firstName, String phoneNumber)
  Create a PhoneEntry for the above information, place it into an Entry object with the PhoneEntry as the value and the lastName as the key, and add it to the tree.

• PhoneEntry get(int index) Should be removed.

• PhoneEntry get(String firstName, String lastName)
  Should search the tree for the entry with key lastName and return the PhoneEntry stored in that node, or null if no entry is found.

• PhoneEntry get(String number)
  Should be removed unless you are doing the extra credit below.

• int getIndex(PhoneEntry entry) Should be removed.

• PhoneEntry remove(int index) Should be removed.

• void remove(PhoneEntry entry)
  Remove entry from the tree by removing the element that has as its key the last name of entry.

• main
  The main method should behave similarly to how it is described in Lab 5, but when a user types "print", you should print the entries using an in-order traversal of the tree. You do not need to deal with the "delete", but if a user types "remove" then the next string will be a last name, and remove the entry for that last name from the tree.

You may assume that each last name and phone number is unique in the directory.

Extra Credit:

1. (small) Change the key for the entry to use both the last name and first name as a key for the entry. You should organize it so that the entries are sorted by last name first and then first name. Make the appropriate changes to your code. You can now assume the pair of last name and first name is unique in the directory.

2. (large) Add a second tree that stores the entries using the phone number as a key. You should not create duplicate PhoneEntrys, but you should create two Entrys for each PhoneEntry, one using the name as a key and the other using the phone number as a key. You should now implement the appropriate get method of PhoneEntry and the lookup and delete commands in the main method. Make certain that whenever an entry is deleted from one tree, the corresponding entry is deleted from the other tree.