Треп — це рандомізоване двійкове дерево пошуку, назва якого поєднує «tree» (дерево) і «heap» (купа), представлене Сесілією Арагон і Раймундом Зайделем у 1989 році. Кожен вузол зберігає ключ і незалежно обраний випадковий пріоритет.

Подвійний інваріант

Дерево одночасно є ДДП за ключами — ключі лівого піддерева менші, правого — більші — і максимальною купою за пріоритетами — пріоритет кожного вузла не менший за пріоритети його нащадків.

Чому очікувана O(log n)

Оскільки пріоритети обираються рівномірно й випадково, форма, що виникає при впорядкуванні вузлів за пріоритетом, розподілена так само, як ДДП, побудоване вставкою ключів у випадковому порядку. Випадкові ДДП — класичний результат з очікуваною висотою O(log n), тож треп успадковує цю гарантію автоматично — без жодних явних правил балансування.

Вставка

Ключ вставляється звичайною рекурсивною вставкою ДДП, стає листком, і йому призначається новий випадковий пріоритет. Далі вузол піднімається поворотом вгору — правий поворот, якщо він лівий нащадок, лівий поворот, якщо правий — поки його пріоритет перевищує пріоритет предка, відновлюючи властивість максимальної купи.

Видалення

Знайдіть вузол за ключем. Поки в нього два нащадки, опускайте поворотом вниз: піднімайте того нащадка, чий пріоритет вищий (вважаючи власний пріоритет вузла, що видаляється, рівним −∞), проштовхуючи цільовий вузол ближче до листка. Коли він має щонайбільше одного нащадка, його просто вилучають.

Без явного обліку балансу

На відміну від AVL чи червоно-чорних дерев, які відстежують висоти чи бітові кольори й застосовують детерміновані правила перебалансування після кожного оновлення, треп не потребує нічого з цього — випадковість сама тримає очікувану висоту логарифмічною.

Бонус: розщеплення та злиття

Треп також підтримує елегантні операції O(log n) розщеплення та злиття, що робить його популярним будівельним блоком для впорядкованих множин, мотузок (ropes) і персистентних структур даних.