Data Structures Library Phase 2 Solution

Function

Description

Runtime

RBTree();

Default Constructor. The tree should be empty

O(1)

RBTree(keytype k[], valuetype V[],

For this constructor the tree should be built using

O(s lg s)

int s);

the arrays K and V containing s items of keytype

and valuetype.

~RBTree();

Destructor for the class.

O(n)

valuetype * search(keytype k);

Traditional search. Should return a pointer to the

O(lg n)

valuetype stored with the key. If the key is not

stored in the tree then the function should return

NULL.

void insert(keytype k, valuetype

Inserts the node with key k and value v into the

O(lg n)

v);

tree.

int remove(keytype k);

Removes the node with key k and returns 1. If key

O(lg n)

k is not found then delete should return 0.

int rank(keytype k);

Returns the rank of the key k in the tree. Returns

O(lg n)

0 if the key k is not found.

keytype select(int pos);

Order Statisics. Returns the key of the node at

O(lg n)

position pos in the tree. Calling with pos = 1

should return the smallest key in the tree, pos = n

should return the largest.

void split(keytype k,

Splits the tree into T1 and T2 based on key k

O(lg n)

RBTree<keytype,valuetype>& T1,

This function will be worth 10 bonus points if

RBTree<keytype,vlauetype>& T2);

implemented on O(lg n) time.

int size();

returns the number of nodes in the tree.

O(1)

void preorder();

Prints the keys of the tree in a preorder traversal.

O(n)

void inorder();

Prints the keys of the tree in an inorder traversal.

O(n)

void postorder();

Prints the keys of the tree in a postorder traversal.

O(n)