Self-adjusting binary search trees
1985/07/01 by Daniel D. Sleator, Daniel Dominic Sleator, Robert E. Tarjan +1 · 1,244 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Amortized analysis #Binary search tree #Binary tree #Combinatorics #Computer science #Data structure #Heuristic #Interval tree #K-ary tree #Lexicographical order #Mathematical optimization #Mathematics #Optimal binary search tree #Optimization and Search Problems #Random binary tree #Search algorithm #Search tree #Self-balancing binary search tree #Ternary search tree #Tree (set theory) #Tree structure #Web Data Mining and Analysis #Weight-balanced tree
paper · pdf · doi:10.1145/3828.3835
published in Journal of the ACM 32(3), 652-686 (Association for Computing Machinery)
openalex publication_date 1985/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25
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.
Citations
Cited by
- Heaps and Their Working Sets
- Retrofitting parallelism onto OCaml
- Self-Adjusting Heaps
- LZ78 Substring Compression in Compressed Space
- Data Structures for Mergeable Trees
- Pandora's Box with Correlations: Learning and Approximation
- The TAG array of a multiple sequence alignment
- Empirical entropy in context
- Dynamic subtrees queries revisited: the Depth First Tour Tree
- Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
- Beyond Word N-Grams
- Randomized Ternary Search Tries
- ikd-Tree: An Incremental K-D Tree for Robotic Applications
- Edge colouring Game on Trees with maximum degree Δ=4
- Reclassification formula that provides to surpass K-means method
- Common-Face Embeddings of Planar Graphs
- Privacy-Preserving Learning-Augmented Data Structures
- Self-Adjusting Networks to Minimize Expected Path Length
- Greedy Is an Almost Optimal Deque
- Analysis of Smooth Heaps and Slim Heaps
- DJXPerf: Identifying Memory Inefficiencies via Object-centric Profiling for Java
- OBST: A Self-Adjusting Peer-to-Peer Overlay Based on Multiple BSTs
- ReNets: Toward Statically Optimal Self-Adjusting Networks
- The generalized work function algorithm is competitive for the generalized 2-server problem
- Adaptive Planar Point Location
- Stratified B-trees and versioning dictionaries
- An interesting spectral gap problem, from Jim Fill
- Sorting a Low-Entropy Sequence
- The Violation Heap: A Relaxed Fibonacci-Like Heap
- Faster Dynamic Matrix Inverse for Faster LPs
- Upper Bounds for Maximally Greedy Binary Search Trees
- Adaptive BSTs for Single-Source and All-to-All Requests: Algorithms and Lower Bounds
- Fast-update in self-learning algorithm for continuous-time quantum Monte Carlo
- A coefficient related to splay-to-root traversal, correct to thousands of decimal places
- SSA without Dominance for Higher-Order Programs
- Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings
- Tight Bounds for Online Stable Sorting
- Adaptive Techniques to find Optimal Planar Boxes
- Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
- Towards Lazy B-Trees
- Parallel batch queries on dynamic trees: algorithms and experiments
- Arithmetic Binary Search Trees: Static Optimality in the Matching Model
- A High Performance Memory Database for Web Application Caches
- Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing
- Flows in Almost Linear Time via Adaptive Preconditioning
- Maintaining Information in Fully-Dynamic Trees with Top Trees
- Self-Adjusting Packet Classification
- Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture
- The inverse Voronoi problem in graphs
- On Compressing Permutations and Adaptive Sorting
- Zip-Tries: Simple Dynamic Data Structures for Strings
- Maintaining information in fully dynamic trees with top trees
- Dynamic Optimality — Almost
- Maintaining bridge-connected and biconnected components on-line
- Optimum Binary Search Trees on the Hierarchical Memory Model
- On Balanced Clustering (Indices, Models, Examples)
- Parallel Ordered Sets Using Join
- Randomized search trees
- Dynamic storage allocation: A survey and critical review
- Improved Upper Bounds for Pairing Heaps
- Towards a Final Analysis of Pairing Heaps
- On the efficiency of pairing heaps and related data structures
- Computing Distances on Graph Associahedra is Fixed-parameter Tractable
- A new approach to the maximum-flow problem
- An O(nlog log n)-Time Algorithm for Triangulating a Simple Polygon
- The Greedy Binary Search Tree is Non-trivially Competitive
- A Cost-Aware Probability Monad for Liquid Haskell
- Self-organizing maps whose topologies can be learned with adaptive binary search trees using conditional rotations
- Calculation of the connective constant for self-avoiding walks via the pivot algorithm
- Large alphabets and incompressibility
- Dynamic Asymmetric Communication
- Real‐time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components
- Rotation distance, triangulations, and hyperbolic geometry
- Binary search tree [wikipedia]
- Splay tree [wikipedia]
- Input Pattern Classification Based on the Markov Property of the IMBT with Related Equations and Contingency Tables. [europepmc]
- Comparison of the performance of skip lists and splay trees in classification of internet packets. [europepmc]
- Algebraic Multi-Layer Network: Key Concepts. [europepmc]
Related