Self-Adjusting Binary Search Trees by Daniel Sleator and Robert Tarjan
= Self-Adjusting Binary Search Trees by Daniel Sleator and Robert Tarjan
{c}
{tag=Work by Daniel Sleator}
{tag=Work by Robert Tarjan}
{title2=1985}
{title2=10.1145/3828.3835}
Original article in \i[Journal of the ACM] 32(3), pp. 652–686. Author-hosted publication record and abstract: https://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.