Treap: как случайные приоритеты спасают бинарное дерево поиска от вырождения

Treap (Cartesian Tree)

Treap (дерево + куча) — структура данных, объединяющая бинарное дерево поиска по ключам и бинарную кучу по случайным приоритетам. Благодаря уникальным приоритетам дерево строится однозначно и в среднем остаётся сбалансированным, что даёт O(log n) на вставку, поиск и удаление. Статья подробно разбирает операции Split и Merge, на которых строятся все остальные, и приводит компактную реализацию на C++.