Implement representations of a set by (2,3)-trees and (2,4)-trees. The set will consist of positive 31-bit numbers, stored in all nodes of the tree (not only in the leaves).
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 following values:
For each kind of test (uniform/biased), draw a plot showing the number of accesses and modifications vs. the size of the set (two lines for (2,3)-trees, two more for (2,4)-trees). Try to explain the differences in behavior of the two structures.
Download the generator or use a compiled version
/afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw2/abgen in the unix lab Rotunda.
Run it with the following parameters:
-s XX, where XX are the last two digits of your student ID;
-b, if you want to generate the biased test; otherwise, the uniform test is generated.
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);
D X: remove a key X from tree (if the key is not present, ignore this operation).
A single invocation of the generator creates a sequence of tests ranging roughly from 1000 to 1000000
elements. If you want to use a different size for debugging, use the
-n N parameter.
# 5 I 67 I 45 D 67 I 81
Send an e-mail with subject of the form 'HW2-55973318' (i.e., HW2-student ID) with the following attachments:
The body of your e-mail shall have the following form:
Name: Martin Mareš Pseudonym for web results: Guybrush Threepwood Tutorial section: Monday-12:20-odd