5.7.2 Skip Lists and Binary search Trees

The paper by William Pugh ( Skip Lists: A probabilistic alternative to balanced trees. Communications of the ACM, Volume 33, Number 6, pp. 668-676, 1990) compares the performance of skip lists with AVL trees, splay trees, and 2-3 trees. Implement all these data structures, design experiments on these data structures, and verify the results presented in that article.