Кратко и по делу.
Определения и инварианты
- AVL: для любого узла $v$ баланс-фактор $BF(v)=$ высота правого поддерева − высота левого поддерева (или наоборот; важно согласованно). Допустимые значения $$BF(v)\in \{-1,0,1\}.$$ Это гарантирует жесткую высотную сбалансированность.
- Красно‑чёрное (RB): каждому узлу присвоен цвет из $\{\text{red},\text{black}\}$ и выполняются свойства:
1. корень — чёрный;
2. ни у одного красного узла нет красных детей (нет двух подряд красных);
3. для каждого узла все простые пути к листьям (nil) содержат одинаковое число чёрных узлов (чёрная высота).
Эти свойства обеспечивают высоту $O(\log n)$.
Шаги при вставке
- AVL:
1. Вставка как в обычное BST.
2. Поднимаясь к корню, обновляем высоты и вычисляем $BF$.
3. Если найден узел с $|BF|>1$, выполняем одну из четырёх ротаций:
- LL (правый поворот) для $BF=+2$ и $B{F}_{right}\ge 0$,
- RR (левый поворот) для $BF=-2$ и $B{F}_{left}\le 0$,
- LR (левый в дочери, затем правый) и RL (правый в дочери, затем левый) для смешанных случаев.
4. После одной корректной ротации баланс восстанавливается для всего пути ниже первой невыровненной вершины — дальнейшие ротации обычно не нужны.
Свойства: вставка требует $O(\log n)$ для поиска и обновлений; ротаций максимум одна (или двойная, считаем как две).
- RB:
1. Вставка как в BST, красим новый узел в красный.
2. Если родитель красный — нарушена проблема двух подряд красных. Применяем процедуру fix-up:
- если дядя красный — перекрасить родителя и дядю в чёрное, дедушку в красное и подняться к дедушке (повтор);
- если дядя чёрный — выполнить одну или две ротации и перекраски (зависит от конфигурации).
3. В конце корень красим чёрным.
Свойства: поиск/вставка $O(\log n)$; в fix-up может быть $O(\log n)$ перекрасок, но не более двух ротаций.
Шаги при удалении
- AVL:
1. Удаление как в BST (если нужно — заменить на преемника).
2. Поднимаясь к корню, обновляем высоты и проверяем $BF$.
3. При $|BF|>1$ выполняем ротации (LL, RR, LR, RL) и продолжаем подниматься — удаление может потребовать перерасстановки и в нескольких вершинах по пути к корню.
Свойства: удаление $O(\log n)$ поиском; может потребоваться $O(\log n)$ ротaций в худшем случае.
- RB:
1. Удаляем узел как в BST; если удаляемый узел чёрный, может возникнуть «двойной чёрный» (extra black) — нарушение чёрной высоты.
2. Применяем сложную фиксирующую процедуру: кейсы с красным/чёрным братом, перекрасками и вращениями; в ряде шагов проблема либо устраняется, либо поднимается выше.
Свойства: поиск/удаление $O(\log n)$; количество перекрасок/шагов может быть $O(\log n)$; число вращений в худшем случае — тоже $O(\log n)$ (реальные реализации обычно выполняют небольшое число вращений).
Сравнение сложностей и констант
- Высота:
- AVL: строгая граница, приблизительно $$h_{AVL}\le c{\log }_2(n),c\approx \mathrm{1.44.}$$ - RB: менее жёсткая, но всё равно логарифмическая: $$h_{RB}\le 2{\log }_2(n+1).$$ - Временные сложности (по операциям):
- Поиск: в обоих $O(\log n)$, но на практике AVL быстрее из‑за меньшей высоты (лучшие константы).
- Вставка/удаление: оба $O(\log n)$. AVL: вставка обычно требует максимум одной балансировки; удаление может потребовать до $O(\log n)$ ротaций. RB: вставка — часто множество перекрасок и максимум константное число вращений (на практике быстро); удаление — более сложное (в худшем $O(\log n)$ шагов).
- Память: AVL обычно хранит высоту или баланс-фактор (несколько байт), RB — один бит/флаг цвета (меньше накладных расходов).
Практические сценарии использования
- AVL:
- Подходит для read-heavy (много операций поиска, мало модификаций).
- Используют там, где требуется максимально быстрый поиск и стабильная минимальная высота.
- RB:
- Хорош в mixed workloads и write-heavy ситуациях; менее строгая балансировка даёт более простые локальные модификации и часто лучшую производительность вставок/удалений в реальных данных.
- Широко используется в стандартных библиотеках (например, std::map в C++ historically) и в ядрах/системах, где важна устойчивость и простота реализации.
- Дополнительно:
- Если важна минимальная задержка при модификациях или память критична — RB часто предпочтительнее.
- Если важен максимум скорости поиска при статичном или редко меняющемся наборе — AVL предпочтительнее.
Короткая рекомендация
- Выбирайте AVL для преимущественно чтения (лучшие константы поиска).
- Выбирайте RB для общего случая с частыми вставками/удалениями и когда нужен простой, надёжный код с минимальной памятью на цвет.