| dc.description.abstract | Binary search trees (BSTs) are important data structures which are widely used
in various guises. Splay trees are a specific kind of binary search tree, one without
explicit balancing. Skip lists use more space than BSTs and are related to them
in terms of much of their run-time behavior.
Even though binary search trees have been used for about half a century, there
are still many open questions regarding their run-time performance and algorith mic complexity. In many instances, their worst-case, average-case, and best-case
behaviors are unknown and need further research. Our analysis provides a basis
for selecting more suitable data structures and algorithms for specific processes
and applications.
We contrast the empirical behavior of splay trees and skip lists with their
theoretical behavior. In particular we explore when splay trees outperform skip
lists and vice versa.
The performance of a splay tree depends on the history of accesses to its el ements. On the other hand, the performance of a skip list depends on an indepen dent randomization of the height of links that lead to specific elements. Therefore,
probabilistic methods are used to analyze the operation of splay trees and skip
lists.
Our main results are that splay trees are faster for sorted insertion, where
AVL trees are faster for random insertion. For searching, skip lists are faster than
single class top-down splay trees, but two-class and multi-class top-down splay
trees can behave better than skip lists. | en_US |
