HW 2: Splay trees

Submission

Send the source code, the output on the generated testing data, and two graphs of the statistics (details below).

English program: deadline is November 20. Submit by e-mail to and a copy to my address on matfyz.cz.

Czech program: your deadline is November 13 and instead of the copy to me you submit to CodEx. Beware that CodEx assignments only accept some languages.

The problem to solve

Implement Splay trees. The standard input contains testing instructions, one operation per line. Each block starts with insertions (I key), then searches follow (F key), and the block ends with an R line which means the tree should be emptied. The whole file ends by an X line.

Output a pair for each block: the size of the testing set and the average depth of the searched keys. At the end of the output, add a more detailed statistics: how many times each depth occured during searches.

Example

I 1
I 2
I 0
F 1
F 0
F 2
R
I 2
I 3
I 0
I 1
F 2
F 0
F 1
F 3
R
X

3 1.3
4 1.5

2 1
1 2
0 1

Generating the input

Example: the command

/afs/ms/u/k/koucky/ds1/pbl2-gen-data XX N

generates the input for measurements, where XX is the last two digits from your personal number (UKČO) found in SIS. N is one of {0,10,100,1000,10000}, and it signifies how big a subset of the input is randomly searched (N=0 denotes all).

The block sizes start at a thousand elements and grow up to a million. There are 300 blocks. Example run:

pbl2-gen-data 72 0     | my-splay > data-0.out
pbl2-gen-data 72 10    | my-splay > data-10.out
pbl2-gen-data 72 100   | my-splay > data-100.out
pbl2-gen-data 72 1000  | my-splay > data-1000.out
pbl2-gen-data 72 10000 | my-splay > data-10000.out

Plotting the output

Create two graphs from the output, each containing one curve per N value. The first graph will come from the first parts of the outputs and show dependence of average searched depth (y-axis) on the size of the tree (x-axis). The second graph will come from the second parts of the ouptups and show the number of searches (y-axis) ending in a given depth (y-axis).