CPSC 220 Fall 2007
Program 3: A Balanced Binary Search Tree
The goal of this program is to create a balanced binary search tree
class with search and insertion capabilities. We will eventually
(but not in this assignment) compare the
performance of this class to our regular
binary search tree class for the lookup-intensive problems we are
addressing for the Regional Commission.
Your program should:
- Include a class BalancedBinarySearchTree that is just like
LinkedBinarySearchTree (extends LinkedBinaryTree, implements
BinarySearchTreeADT, and has the same public methods) but is
guaranteed to maintain a balanced tree. You do not need
to rebalance when removing a node. (In fact, you do not have to
implement the remove method at all.)
- Use either the AVL or the red-black algorithm to keep the tree balanced.
Whichever you choose should be noted in your documentation and
implemented precisely.
- Include a test program that allows the user to do two things:
- Enter integers to be
inserted into the tree in order. The program should
then print preorder and inorder
traversals of the tree along with its height.
- Search for one or more elements in the tree.
This program is due by 4:00 pm on Tuesday, November 20. E-mail me a
tar file of your directory by that date and bring hardcopy with you to
class on Monday, Nov 26. Because of the Thanksgiving holiday, late penalties
will accrue at an adjusted rate: programs received
by 4:00 pm on Sunday, Nov 25 will be counted one day late,
and by Mon, Nov 26 as two days late.