 Randomized Search Trees by Raimund Seidel and Cecilia R. Aragon

By Raimund Seidel, Cecilia R. Aragon.

Primary source: faculty.washington.edu/aragon/pubs/rst96.pdf

Section 2, treap invariants and split/join; later sections analyze expected depth and operation cost.