Self-Adjusting Binary Search Trees

Daniel Dominic Sleator, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

850 Scopus citations

Abstract

The splay tree, a self-adjusting form of binary search tree, is developed and analyzed. The binary search tree is a data structure for representing tables and lists so that accessing, inserting, and deleting items is easy. On an n-node splay tree, all the standard search tree operations have an amortized time bound of O(log n) per operation, where by “amortized time” is meant the time per operation averaged over a worst-case sequence of operations. Thus splay trees are as efficient as balanced trees when total running time is the measure of interest. In addition, for sufficiently long access sequences, splay trees are as efficient, to within a constant factor, as static optimum search trees. The efficiency of splay trees comes not from an explicit structural constraint, as with balanced trees, but from applying a simple restructuring heuristic, called splaying, whenever the tree is accessed. Extensions of splaying give simplified forms of two other data structures: lexicographic or multidimensional search trees and link/cut trees.

Original languageEnglish (US)
Pages (from-to)652-686
Number of pages35
JournalJournal of the ACM (JACM)
Volume32
Issue number3
DOIs
StatePublished - Jul 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Self-Adjusting Binary Search Trees'. Together they form a unique fingerprint.

Cite this