Self-Adjusting Binary Search Trees by Daniel Sleator and Robert Tarjan 2026-10-31
View more
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