The splay trees paper by Sleator and Tarjan (1985) https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf https://www.cs.cmu.edu/~sleator/papers/self-adjusti

The splay trees paper by Sleator and Tarjan (1985) https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf It's just such a cool result and the paper is very well written. Further, the dynamic optimality conjecture at the end is still an open problem.