Data Structures I - NTIN066 - Winter Semester 2015/2016 - 3rd homework

Deadline: 1st December 2015.
How to submit: As an attachment of email to

The rules

The description of the problem

Implement two versions of Splay trees, the classical one which uses double rotations and a naive version which uses only the simple rotation on the whole path from a splayed node to the root.
Simple rotation
Simple rotation

Examine behavior of both data structures on test data generated by the program described below. The test data contain sets of varying sizes with two kinds of operations:

For each set, measure the average length of paths from the root to the given splayed node.

Generating the data

Use the program /afs/ in the unix lab Rotunda. Run it with the following parameters:

The output of the generator is a text file. Each line specifies a single operation on the tree:

A single invocation of the generator creates a sequence of tests ranging roughly from 1000 to 1000000 elements.

Resulting graphs

For each kind of test draw a plot showing the dependency of the average length of the path Find on the size N:

  1. For the classical Splay tree and uniform subset test, plot six curves, each for one value of T from {10,100,1000,10000,100000,1000000}.
  2. As the previous graph, but using the naive implementation of Splay trees.
  3. 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 from {100,10000,1000000}.
  4. For the classical and naive version, plot the average length of the path during the sequential test.

Try to explain the differences in behavior of two versions of the tree.

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

Submitting your solution

Send an e-mail with subject of the form 'HW3-55973318' (i.e., HW3-student ID) with the following attachments:

The body of your e-mail shall have the following form:

Name: Jirka Fink
Pseudonym for web results: Guybrush Threepwood
Tutorial section: Monday-12:20-odd