Project Assignment: Red-Black Trees

You are to build binary search trees with nodes consisting of key & count fields. Keys are inserted in the given order into the tree - each new key with initial count 1 otherwise increment the count at the node containing the key by 1. For the following two input key sequences, you are to compare the heights of the four resulting binary trees, two without special balancing effort and two red-black trees.

1. A sequence of 500 random numbers each between 1 & 100.
2. 1, 3, 5,..., 99, 2, 4, 6,..., 100, followed by 400 random numbers between 1 & 100.

Also find the average number of key comparisons needed for a successful search in each of the four resulting trees, assuming that the counts represent the relative frequencies of the keys being sought. Compare the results.

Note. The height of the tree represents the worst case performance of a successful search. The average weighted path lengths represents average performance of a successful serach.