Next: 4. Binary Trees
Up: 3.12 Programming Assignments
Previous: 3.12.1 Hashing: Experimental Analysis
Implement skip list data structure. Analyze the efficiency of search,
insert, and delete operations on randomly generated inputs. Carefully
take into account all the tradeoffs involved in designing and
implementing skip lists. Validate the experimental results with those
given in the article by William Pugh
(Skip Lists: A probabilistic alternative to balanced trees.
Communications of the ACM, Volume 33, Number 6, pp. 668-676, 1990).
Design and carry out experiments to compare the performance of skip lists
with that of hash tables.