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:

• 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 radix-3 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 red-black 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, Zig-zig, Zig-zag, Zag-zig, Zag-zag) 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 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.