nextupprevious
Next:5.7.2 Skip Lists and Binary search TreesUp:5.7 Programming AssignmentsPrevious:5.7 Programming Assignments

5.7.1 Red-Black Trees and Splay Trees

This assignment involves the implementation of searches, insertions, and deletions in red-black trees and splay trees, and evaluating the performance of each data structure in several scenarios. The intent is to show that these trees are better than ordinary (unbalanced) binary search trees and also to compare red-black trees with splay trees.

Generation of Keys

Assume that your keys are character strings of length 10 obtained by scanning a C program (identical to Programming assignment 1). If a string has less than 10 characters, make it up to 10 characters by including an appropriate number of trailing *'s. On the other hand, if the current string has more than 10 characters, truncate it to have the first ten characters only.

Inputs to the Program

The possible inputs to the program are:

What should the Program Do?
1.
Scan the given C program and as you scan, insert the first n distinct strings scanned into an initial search tree (BST or RBT or ST).
2.
For each individual operation, keep track of:
Now, compute for the BST, RBT, and ST so created, the following:
3.
Scan the rest of the C program token by token, searching for it or inserting it or deleting it, as dictated by the radix-3 representation of I and its permutations. You are to carry out a total of N operations.
4.
Repeat Step 2 to evaluate the trees over the N operations.

nextupprevious
Next:5.7.2 Skip Lists and Binary search TreesUp:5.7 Programming AssignmentsPrevious:5.7 Programming Assignments
eEL,CSA_Dept,IISc,Bangalore