The Complexity of Splay Trees and Skip Lists.

Description

<p>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.</p>

Links & Downloads

1. http://etd.uwc.ac.za/index.php?module=etd&action=viewtitle&id=gen8Srv25Nme4_6858_1263424080

Tags

Binary Search Trees

Balanced Trees

AVL Trees

Self-adjusting Trees

Bottom-up Splay Trees.

Additional Fields

Identifer	oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uwc/oai:UWC_ETD:http%3A%2F%2Fetd.uwc.ac.za%2Findex.php%3Fmodule%3Detd%26action%3Dviewtitle%26id%3Dgen8Srv25Nme4_6858_1263424080
Date	January 2008
Creators	Sayed, Hassan Adelyar.
Source Sets	South African National ETD Portal
Language	English
Detected Language	English
Type	Thesis and dissertation
Format	Pdf
Coverage	ZA
Rights	Copyright: University of the Western Cape