CIS 313 Winter 1997
Introduction to Information Structures
Programming Assignment #3
Implement the deletion function Remove for the Red Black Trees.
Perform experiments verifying (or at least substantiating) the claims:
- that the tree resulting from insertion of one less than a power of
2 consecutive keys in order (Problem 18.12) is complete,
- the logarithmic bound on the height of Red Black trees,
- the O(log n) time complexity of Red Black tree operations
Deliverables:
- A well documented and structured source code of the program.
- Listing of the depth of nodes during a systematic traversal of the
constructed tree, for n=15, 31, 63 nodes.
- Listing of node depths for each of the trees above after the deletion
of a random key.
- Height of a tree resulting from random insertion of nodes, for
n=200, 500, 1000 nodes.
- Timing of insertion and deletion operations in a tree resulting from
random insertion of nodes, for n=200, 500, 1000 nodes.
Notes:
- The text's description of Remove is incorrect!
- Most of the code is available on the web; use it judiciously!