Next:5.7.2
Skip Lists and Binary search TreesUp:5.7
Programming AssignmentsPrevious:5.7
Programming Assignments
5.7.1 RedBlack Trees and Splay
Trees
This assignment involves the implementation of searches, insertions, and
deletions in redblack 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 redblack 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:

n: The initial number of insertions of distinct strings to be made
for setting up an initial search tree (RBT or ST).

I: This is a decimal number from which a ternary string is to be
generated (namely the radix3 representation of I). In this representation,
assume that a 0 represents the search operation, a 1
represents the insert operation, and a 2 represents the delete
operation.

N: Number of operations to be performed on the data structure.

A C program, from which the tokens are to be picked up for setting up and
experimenting with the search trees.
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:

Number of probes (comparison of two strings of 10 characters each)

Number of pointer assignments (a single rotation involves three pointer
assignments)

Number of single rotations and number of double rotations (in the case
of RBTs and STs)

Examining or changing the colour (in a redblack tree)
Now, compute for the BST, RBT, and ST so created, the following:

Height of the search tree

Total number of probes for all the operations

Average number of probes (averaged over all the operations) for a typical
successful search, unsuccessful search, insert, and delete.

Total number of pointer assignments

Total number of single rotations (in the case of RBTs and STs)

Total number of double rotations (in the case of RBTs and STs)

Total number of each type of splaying steps (Zig, Zag, Zigzig, Zigzag,
Zagzig, Zagzag) in the case of STs

Total number of recolourings in the case of RBTs

3.

Scan the rest of the C program token by token, searching for it or inserting
it or deleting it, as dictated by the radix3 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.
Next:5.7.2
Skip Lists and Binary search TreesUp:5.7
Programming AssignmentsPrevious:5.7
Programming Assignments
eEL,CSA_Dept,IISc,Bangalore