Multiway Search Trees and B-TreesUp:5.7
Red-Black Trees and Splay Trees
5.7.2 Skip Lists and Binary search
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.