The Complexity of Splay Trees and Skip Lists
Loading...
Date
2008
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of the Western Cape
Abstract
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.
Description
Magister Scientiae - MSc
Keywords
Binary Search Trees, Balanced Trees, AVL Trees, Self-adjusting Trees, Bottom-up Splay Trees