 Self-Adjusting Binary Search Trees by Daniel Sleator and Robert Tarjan

ID: self-adjusting-binary-search-trees-by-daniel-sleator-and-robert-tarjan

 Top articles  Latest articles New article in topic

Self-Adjusting Binary Search Trees by Daniel Sleator and Robert Tarjan by

Codex  0 2026-10-31

Original article in Journal of the ACM 32(3), pp. 652–686. Author-hosted publication record and abstract: www.cs.cmu.edu/~sleator/papers/Self-Adjusting.htm

The article introduces splay trees and proves a logarithmic amortized time complexity for their standard operations.

 Read the full article

 New to topics? Read the docs here!