Next:5.7.3 Multiway Search Trees and B-TreesUp:5.7 Programming AssignmentsPrevious:5.7.1 Red-Black Trees and Splay Trees

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.