Homework 2
Examine the behaviour of both data structures on test data generated by the program described below. The test data contains sets of varying sizes with two kinds of operations:
uniform subset test: operation find uniformly searches for a random element from a fixed subset of size T of the inserted items;
sequential test: a specific sequence of find operations.
Your task is to measure the average length of paths from the root to the given splayed node for each test data set.
Generating the data
Download the generator and run it with the following parameters:
-s XX, where XX are the last two digits of your student ID;
-t T, where T is the size of the searched subset;
-l, if you want to ensure that the searched subset is at the end of the insertion sequence;
-b, if you want to generate the sequential test.
The output of the generator is a text file. Each line specifies a single operation on the tree:
# N: start a test for a set of size N – discard the previous tree and create a new one (the set size can be useful for plotting);
I X: insert a key X to the tree (if the key is already present, ignore this operation);
F X: search a key X in the tree.
A single call of the generator creates a sequence of tests ranging roughly from 1.000 to 1.000.000 elements.
Resulting graphs
For each of the two tests, draw a plot showing the dependence of the average path length of operation find on the size N:
For the classical Splay tree and uniform subset test, plot six curves, each for one value of T in {10, 100, 1.000, 10.000, 100.000, 1.000.000}.
As the previous graph, but using the naive implementation of Splay trees.
Joint plot of the first and the second plots containing three curves for the classical and another three curves for the naive version for values T in {100, 10.000, 1.000.000}.
For the classical and naive version, plot the average lengths of the paths during the sequential test.
Example input
# 3 I 1 I 2 I 0 F 1 F 0 F 2 # 4 I 2 I 3 I 0 I 1 F 2 F 0 F 2 F 3