4.9.3 Comparison of Skip Lists and Splay Trees

The objective of this assignment is to compare the performance of splay trees and skip lists in implementing search, insert, and delete operations in dictionaries. The context is provided by symbol table operations in a C compiler.
What is Required?
Assume that your keys are identifiers in a C program (strings that are different from special symbols). Use LEX to design a scanner (lexical analyzer) that will scan the C program and split it into a set of identifiers. Each identifier is a regular expression. Call these identifiers as tokens from henceforth. The tokens are to be put it into a symbol table. The following two data structures are to be evaluated.

1.

Splay trees with bottom-up splaying

2.

Skip lists

Inputs to the Program
The inputs to the program are:

• A C program of sufficient size
• n: The initial number of insertions of distinct tokens to be carried out to set up a base data structure.

What should the Program Do?
Do the following steps for splay tree (skip list):

1.

Scan the given C program and as you scan, insert the first n distinct tokens into an initially empty data structure.

2.

Now scan the rest of the C program token by token, inserting or deleting the token, by tossing a fair coin. For each individual operation, keep track of the number of probes and number of rotations (if applicable). Count the number of elementary operations for each insert or delete (comparisons, assignments of pointers, etc.)

3.

Compute the average number of elementary operations for insert and delete.

Programming Language
C++ or Java is recommended. A serious attempt should be made to use ideas of data abstraction, encapsulation, modularity, inheritance, and polymorphism.