CS 201 Data Structures Library Phase 2 Due 11/1
Phase 2 of the CS201 programming project, we will be built around a balanced binary search tree. In
particular, you should implement a left-leaning red-black tree for the class RBTree.
The public methods of your class should include the following (elmtype indicates the type from the
template):
Function Description Runtime
RBTree(); Default Constructor. The tree should be empty O(1)
RBTree(keytype k[], valuetype V[],int s);
For this constructor the tree should be built using
the arrays K and V containing s items of keytype
and valuetype.O(s lg s)
~RBTree(); Destructor for the class. O(n)
valuetype * search(keytype k); Traditional search. Should return a pointer to the
valuetype stored with the key. If the key is not
stored in the tree then the function should return
NULL.O(lg n)
void insert(keytype k, valuetypev);
Inserts the node with key k and value v into the
tree.O(lg n)
int delete(keytype k); Removes the node with key k and returns 1. If key
k is not found then delete should return 0.O(lg n)
int rank(keytype k); Returns the rank of the key k in the tree. Returns
0 if the key k is not found.O(lg n)
keytype select(int pos); Order Statisics. Returns the key of the node at
position pos in the tree. Calling with pos = 1
should return the smallest key in the tree, pos = n
should return the largest.O(lg n)
void split(keytype k,
RBTree