do the following problem:
Implement a balanced binary search tree for storing integers - either
a red-black tree or a 2-3 tree. The program should interactively take
input from the user, accepting the following commands, which trigger
the given actions:
i 5 - inserts the value 5 (or whatever number the user gives) into the tree.
s 5 - searches for the value 5 (or whatever), and reports yes if the
value is in the tree, or no if it is not.
d 5 - search for the value, and if it is in the tree deletes the value
and reports done, or reports not there otherwise.
p - do inorder traversal, printing out all stored values.
h - report the height of the root (i.e., the length of the longest
path from the root to a leaf).
c - report the number of nodes in the tree (c is for count).
q - quit the program.
Don't quit until the q command is received.
When printing the inorder traversal, print the values in a way that
shows the structure of the tree. One easy way to do this is to wrap
parentheses around all values in each subtree (including the entire
tree). For example, the 2-3 tree in the middle right of Figure 6.8 on
page 216 (after inserting all numbers except 7) would look like this:
((2) 3 (4 5) 8 (9))
If you implement a red-black tree, be sure to distinguish between red
and black nodes somehow, perhaps by putting asterisks around the black
values. |
