Конспект раздела: деревья поиска

Карта раздела

Раздел отвечает на вопрос «как хранить упорядоченные данные так, чтобы и искать, и менять было быстро». Сквозная мысль: скорость дерева = его высота, и всё разнообразие деревьев - это разные способы держать высоту малой под разные условия.

BST                  ->  инвариант «левое < узел < правое»; всё за O(h); отсортированный ввод → цепочка h=n
     |
балансировка         ->  вращение O(1) хранит порядок; АВЛ (разница высот ≤1), красно-чёрное (цвет)
     |
B-деревья            ->  узел = дисковый блок на сотни ключей; высота log_b n: при b = 500 и 10⁹ ключей - 3-4 чтения
     |
случайность          ->  декартово (приоритеты), splay (амортизация), skip list (случайные уровни)
     |
дополнение           ->  поле в узле, восстановимое из детей: size → ранг, max → пересечение
     |
диапазоны            ->  дерево отрезков, Фенвик, lazy: запрос и обновление диапазона за log n

Сводная таблица деревьев

структура	высота / цена	гарантия	когда
голый BST	`O(h)`, до `n`	нет	только учебно
АВЛ	`≤ 1.44·log₂ n + 1`	худший случай	поиск ≫ правки
красно-чёрное	`≤ 2·log₂(n+1)`	худший случай	универсал (`std::map`, `TreeMap`)
B / B+-дерево	`log_b n`, 3-4 чтения	худший случай	диск: индексы БД, ФС
декартово (treap)	`O(log n)`	ожидание	простота, SPLIT/MERGE
splay	`O(log n)`	амортизация	горячие данные
список с пропусками	`O(log n)`	ожидание	простота, параллелизм
дерево отрезков	`O(log n)` запрос/обновление	худший случай	диапазоны, любая свёртка
дерево Фенвика	`O(log n)`	худший случай	динамические суммы

Три компромисса раздела

Строгость баланса против частоты правок. АВЛ ниже, но чаще вращает; красно-чёрное выше, но чинится реже (часто перекраской). Идеала «низко И редко чинить» нет.

Гарантия против ожидания. АВЛ/красно-чёрное дают O(log n) в худшем случае; treap и skip list - в ожидании (случайность внутри, вход подобрать нельзя); splay - амортизированно.

Цена зависит от уровня памяти. В памяти оптимум - двоичное дерево (считаем сравнения); на диске - широкий узел B-дерева (считаем чтения блоков): ветвление уходит в основание логарифма.

Два приёма, которые переносятся дальше

Вращение - атом балансировки: O(1), хранит порядок (серединное поддерево перевешивается на нужное место). Из него собраны АВЛ, красно-чёрное, декартово, splay.

Дополнение - добавь в узел поле, восстановимое из детей за O(1), - и получишь новую операцию, не ломая старых и не мешая вращениям. Дерево отрезков - этот же приём, доведённый до диапазонов; отложенные метки добавляют к нему ленивость.

Ловушки джокера всего раздела

Голый BST на отсортированных или потоковых данных - вырождение в цепочку, Θ(n).

Потерять серединное поддерево при вращении - дерево перестаёт быть BST.

Одинарный поворот для ломаного случая LR/RL - нужен двойной.

Двоичное дерево для дискового индекса - ~30 чтений вместо 3-4.

Считать treap, skip list или splay гарантией на каждую операцию - это ожидание или амортизация.

Поле дополнения, не восстановимое из детей - вращения станут O(n).

Префиксные суммы при обновлениях, Фенвик для min/max, забытый push_down в запросе.

Последовательность, которая меняет порядок

Задача	Инструмент	Условие или граница
Вставка, вырезание, разворот	Неявное декартово дерево	split по размеру и merge по порядку; ожидаемый логарифм при случайных приоритетах.
Сумма меняющегося диапазона	total в поддереве	Два split, ответ из корня, два merge; разворот сохраняет total.

Проверь себя

Почему цена операций дерева - высота и что её портит?

Как вращение меняет форму, не трогая порядок, и чем АВЛ отличается от красно-чёрного?

Почему индексы БД - B-деревья, а std::map - красно-чёрное?

Как случайность (treap, skip list) и амортизация (splay) заменяют явную балансировку?

Как поле в узле даёт новую операцию и чем дерево отрезков отличается от Фенвика?