Treaps: How Random Priorities Make Binary Search Trees Fast
Treap (Cartesian Tree)
A treap fuses a binary search tree with a binary heap: nodes are ordered by key for search and by random priority for balance. Proposed by Raimund Seidel and Cecilia Aragon in 1989, it guarantees expected O(log n) operations without complex rebalancing. The article explains the structure, its advantages, and implements split, merge, insert, erase, build, and union in C++.
Obviously, if you choose the priorities randomly, you will get non-degenerate trees on average, which will ensure logarithmic complexity for the main operations.