CSE326 Assignment #3
Spring 2002

Due: Friday, April 26, 2002, at the beginning of class.

Reading in Lewis & Denenberg:

• 6.4, 7.1, 7.2 (2-3 Trees and B-Trees only), 7.3

  Most of the reading in chapter 6 should be review.

Problems

1. You've seen code for several different types of tree objects: regular trees, BST's, and (once you've read the AVL assignment) AVL trees. The different trees have been given to you as distinct, unrelated objects. A good object-oriented programmer would have arranged the tree classes into a hierarchy in order to maximize code reuse.

   I want you to come up with a hierarchy for the three classes BinaryTree, BinarySearchTree and AVLTree. Think about issues such as maximizing code reuse and maintaining a consistent interface. Use polymorphism (virtual functions) where appropriate. Ignore everything to do with the Visualizer: concentrate on the core search tree functionality.

   1. Produce a valid C++ .h file for your class hierarchy. You don't need to actually compile it, but you should include all appropriate members and methods of all classes, public, private and protected. Print it out and staple it with the rest of your assignment.

   2. Write a paragraph or two discussing your hierarchy. What is easy to do in your hierarchy? What's hard to do? How does the interface differ from that of the trees for your programming assignments? Don't write more than a page.

From Chapter 4:

• 3, 7, 14

• Extra-Credit: 18 (See 4.4; pseudo-code for the functions is okay).

From Chapter 6:

• 36, 38 (for binary trees only)

From Chapter 7:

• 2

• 7, 8 (use the presentation of the theorem from the book, not from class)

• Extra-Credit: 6