View Record

TitleThe Complexity of Splay Trees and Skip Lists.
AuthorSayed, Hassan Adelyar.
SubjectBinary Search Trees
Subject Balanced Trees
Subject AVL Trees
Subject Self-adjusting Trees
Subject Bottom-up Splay Trees.
TypeThesis and dissertation
AbstractOur 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.