Treap: BST + Heap = Рандомный баланс

Цели урока

• Понять идею рандомизированного баланса
• Освоить структуру Tree + Heap
• Реализовать Split и Merge
• Узнать о применениях Implicit Treap

Предварительные знания

• Binary Search Tree
• Heap

• BST
• Heap

AVL и Red-Black деревья - это несколько страниц кода с мучительной отладкой. Treap даёт те же гарантии в 30 строках. Секрет? Случайность делает балансировку за нас.

• GNU libstdc++ - PBDS (policy-based data structures)
• Rope в текстовых редакторах
• Соревновательное программирование
• Алгоритмы на отрезках

Рандомизированные деревья поиска Зейделя и Арагон

Раймунд Зейдель и Сесилия Арагон представили treap в 1989 году в статье 'Randomized Search Trees'. Их идея состояла в том, чтобы прикрепить к каждому узлу второй, случайный ключ. Первый ключ сохраняет порядок двоичного дерева поиска, а случайный ключ задаёт поверх него порядок кучи, и само название treap это просто tree плюс heap. Поскольку ключ кучи случаен, форма дерева совпадает с формой двоичного дерева поиска, построенного вставкой тех же ключей в равномерно случайном порядке, а у такого дерева ожидаемая высота O(log n). Это позволяет обойти явные правила поворотов AVL и красно-чёрных деревьев: вместо того чтобы аккуратно восстанавливать инвариант после каждого изменения, структура сама остаётся сбалансированной в ожидании. Зейдель и Арагон также показали, как split и merge служат примитивами для всех остальных операций, и поэтому treap стал любимым выбором для отрезков и последовательностей в соревновательном программировании.

Проблема: Баланс без боли

**AVL и Red-Black** гарантируют O(log n), но их балансировка - головная боль при реализации.

**Treap** был изобретён Арагоном и Зейделем в 1989. Название = **Tree** + **Heap**.

Структура: Два свойства в одном

Каждый узел Treap имеет **два** значения:

1. **Key** (ключ) - для BST порядка
2. **Priority** (приоритет) - случайное число для Heap порядка

**Магия:** если приоритеты случайные, то структура дерева эквивалентна вставке ключей в случайном порядке - а это даёт сбалансированное BST!

Split и Merge: Ключевые операции

Treap имеет две мощные операции, на которых строится всё остальное:

Split(T, key) → (L, R)

Разбивает дерево T на два: L (все ключи < key) и R (все ключи ≥ key).

Merge(L, R) → T

Объединяет два дерева, где все ключи L < все ключи R.

**Обе операции O(log n)** в ожидании. Split идёт вниз по дереву, Merge тоже.

Insert и Delete через Split/Merge

**Вставка** и **удаление** компактно выражаются через Split и Merge!

**Красота Treap:** вся сложность спрятана в Split/Merge. Остальные операции - комбинации этих двух.

**Поиск** работает как в обычном BST - по ключам:

Применения Treap

Treap особенно полезен для задач, где нужны **операции на отрезках**:

• **Implicit Treap** - массив с O(log n) вставкой/удалением в любую позицию
• **Rope** - эффективные строки для текстовых редакторов
• **K-й элемент** - поддержка размера поддерева
• **Разрез массива** - split по позиции
• **Переворот отрезка** - с ленивыми флагами

**Rope** в текстовых редакторах (VS Code, Sublime) часто используют структуры типа Treap для быстрой вставки текста в середину файла.

Treap

• Treap = BST по key + Heap по priority
• Случайные приоритеты → ожидаемый O(log n)
• Split разбивает, Merge объединяет
• Insert/Delete через Split + Merge
• Implicit Treap - массив со вставкой за O(log n)

Рандомизированные структуры

Treap - пример силы рандомизации. Skip List использует похожую идею.

• Skip List — Рандомизированный список
• Splay Tree — Self-adjusting BST

Связанные уроки

• ds-11-bst — Treap - это BST, упорядоченное по ключам
• ds-14-heaps-intro — Случайные приоритеты подчиняются свойству кучи
• ds-22-skip-list — Обе используют случайность вместо явной перебалансировки
• ds-12-balanced-trees — Даёт ожидаемый баланс без строгих поворотов
• prob-22-concentration — Ожидаемая высота O(log n) требует вероятностной концентрации
• alg-10-binary-search