Treap: Збалансоване Дерево BST, Будоване з Монетки

Introduction

This article explores the Treap data structure, a self-balancing binary search tree. Unlike traditional self-balancing trees like AVL or red-black trees, Treaps rely on a simple yet effective approach to maintain balance: assigning each node a random number.

Два порядки, що зберігаються одночасно

Кожен вузол зберігає ключ і пріоритет, вибраний випадковим чином під час вставки. Дерево підтримує обидва властивості одночасно:

Порядок BST: обхід у порядку залежності (in-order traversal) відвідує ключі в відсортованому порядку Порядок кущі: пріоритет кожного вузла >= пріоритетів його двох дітей Для будь-якого набору (ключ, пріоритет) з унікальними значеннями існує лише одна форма дерева, яка задовольняє обидва обмеження — тому структура визначається в момент вибору пріоритетів, незалежно від порядку прибуття ключів.

BST order:   in-order traversal visits keys in sorted order
Heap order:  every node's priority >= both children's priorities

Insertion via rotations

Insert like an ordinary BST — walk down comparing keys until you find the empty spot — then restore heap order by rotating the new node upward past any parent with a smaller priority, exactly like sift-up in a binary heap but using tree rotations instead of array swaps:

function rotateRight(y) {          // y becomes right child of x
  const x = y.left;
  y.left = x.right;
  x.right = y;
  return x;                        // x is the new subtree root
}
// insert(node), then while node.priority > node.parent.priority:
//   rotate right or left depending on which child node is

Why random priorities guarantee expected O(log n) height

This is the result Raimund Seidel and Cecilia Aragon proved in 1996: a treap built from any sequence of key insertions, as long as the priorities are drawn independently at random, has the exact same probability distribution over shapes as a plain BST built by inserting those same keys in a uniformly random order. It does not matter whether the actual insertion order was sorted, reverse-sorted or adversarially chosen — the priorities alone decide the shape, and a randomly-ordered BST is well known to have expected height O(log n). The treap gets the average-case guarantee of random insertion order for free, on any input.

Розділення та злиття: операції, які роблять трепи особливими

function merge(t1, t2) {

if (!t1) return t2;

if (!t2) return t1;

if (t1.priority > t2.priority) {

t1.right = merge(t1.right, t2);

return t1;

} else {

t2.left = merge(t1, t2.left);

return t2;

}

}

Розділення та злиття — це механічні операції, які дозволяють створити неявний треп — де "ключ" є просто позицією елемента в послідовності, а не збереженим значенням. Це підтримує операції, які в інших збалансованих деревах є складними: вирізати безперервний діапазон, перевернути його та вставити назад в іншому місці, все це за O(log n). Саме тому трепи використовуються як основа для текстових редакторів на основі ниток і масивів, які потребують перевертання діапазонів або зсуву діапазонів.

function merge(t1, t2) {
  if (!t1) return t2;
  if (!t2) return t1;
  if (t1.priority > t2.priority) {
    t1.right = merge(t1.right, t2);
    return t1;
  } else {
    t2.left = merge(t1, t2.left);
    return t2;
  }
}

Treap vs AVL vs red-black

AVL and red-black trees guarantee O(log n) height in the worst case, with no randomness involved — an adversary who sees every operation can never force bad performance. A treap only guarantees O(log n) in expectation; a run of terrible luck in the random priorities is possible, just vanishingly unlikely, and invisible to an adversary who does not know the random seed. In exchange, treap code is dramatically simpler — no color bits, no balance factors, no multi-case rotation logic for deletion — and it composes: split and merge let you build range operations, persistence and order statistics with a few extra lines rather than a redesign of the rebalancing logic.

Frequently asked questions

Спробуйте наживо

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