Programming Assignment 1, ENEE759F, Fall 2001

Write a C program which implements a red-back tree data-structure.
The program should support search, insert and delete queries.
An insert query should be able to cope with the case that the key is already
in the tree and a delete query should be able to cope with the case that the 
key is not there.

This assignment has two deadlines.

First deadline: November 19.
---------------------------
By this date, please submit your code.
Your code should first build directly an all black balanced binary tree
with 127 nodes: all the numbers divided by 4 between 4 and 508.
Do this in the most efficient way you can find. Do not use the red-black tree 
one. (Explain what you did and discuss the efficiency.)
Print this 127-node tree out laid out as a tree.
That is, the printout will look like a graphic presentation of a binary tree.
It should be similar to Figure 14.1 (1st Edition, or Figure 13.1(a), 2nd 
Edition), but without the NIL leaves.
It is expected that you will make some effort to figure out a way for obtaining
a satisfactory printout format.

The code itself should count for each query it executes the number of 
instructions (i.e., lines of C) it takes (do not count the counting 
instructions, or instructions related to the printout or its preparation).

Provide the following printouts:
For each query: the number of instructions executed.
For a search query: the yes/no outcome.
For an insert query: the new tree.
For a delete query: the new tree.

Your code should be well documented and the counting instructions
clearly marked to differentiate them from the regular instructions.

Attach to the code a careful written analysis of the complexity 
(including constant factors) for executing each query.
The analysis should include the count of the same operations 
counted above, that a query can execute.

Second deadline: November 21. 
---------------------------
On November 19 you will get a sequence of up to 100 queries.
Your initial tree will be the one with 127 nodes constructed earlier.
You will have to produce an output and submit it by November 21.