Assignment: Data Structures and Algorithms

In this project, you are going to reuse your BST from program 1 and create an implementation of a red-black tree using a subclass of BinaryNode. In addition to the normal functions of a red-black tree, as discussed in class, you will add the following methods:

a) Count the number of leaves in a tree with data.
b) Return the height of the tree.
c) Return a listing of all the nodes in our tree with values between a and b

(a and b being values given to us by the user)

Your program should:

- Randomly generate 100 values
- Load the values which were generated into both an instance of your BST and red-black tree programs
- Offer the user a menu with the following options:

o Insert a new value (ignore repetitions, values should be added to both trees)
o Delete a value (values should be deleted from both trees)
o Return a count of the leaves of both trees
o Return a listing of all values in the tree between a and b, where a and b are input by the user.
o An option for the user to delete the first 20 entries in the trees encountered by a preorder traversal if possible. Once completed, this option will automatically display the new height of the tree, and the count of the remaining leaves in both trees.

- Provide an option to exit the program

(Your program should continue displaying the menu after each action is completed until the user chooses to quit)

In your project report, you need to analyze the differences in our BST and red-black trees. Which seems to be more efficient? Why is that?

You are free to choose how you present the menu to the user.