Структуры данных
Сбалансированные деревья: AVL и Red-Black
Цели урока
- Понять почему обычный BST недостаточен
- Изучить AVL и его повороты
- Познакомиться с Red-Black деревом
- Научиться выбирать структуру под задачу
Предварительные знания
- Binary Search Tree
В 1962 году два советских математика решили проблему: как сделать так, чтобы дерево никогда не превращалось в список? Их изобретение - AVL-дерево - до сих пор используется в базах данных.
- Linux kernel - Red-Black для планировщика
- Java TreeMap/TreeSet - Red-Black
- C++ std::map - Red-Black
- PostgreSQL - AVL для индексов в памяти
Первое самобалансирующееся дерево
Слабость обычного BST на отсортированном входе решили советские математики Георгий Адельсон-Вельский и Евгений Ландис: в 1962 году они описали AVL-дерево, первую структуру, которая сама поддерживает баланс через повороты и гарантирует высоту O(log n). Десятилетием позже, в 1972 году, Рудольф Байер предложил симметричные бинарные B-деревья, а Лео Гибас и Роберт Седжвик в 1978 году переформулировали их как красно-чёрные деревья с привычной нам раскраской узлов. Эти идеи давно ушли из теории в практику: красно-чёрные деревья стоят за std::map в C++, TreeMap в Java и планировщиком CFS в ядре Linux. Так гарантия логарифмической высоты из этого урока работает в коде, которым мы пользуемся каждый день.
Проблема дисбаланса
BST обещает O(log n), но только для **сбалансированных** деревьев.
**Худший случай BST = связный список.** Поиск за O(n) - не лучше массива!
Какова сложность поиска в вырожденном BST из n элементов?
AVL-дерево: Строгий баланс
**AVL-дерево** (Адельсон-Вельский и Ландис, 1962) - первое самобалансирующееся BST.
**AVL свойство:** для каждого узла высота левого и правого поддеревьев отличается **не более чем на 1**.
AVL-дерево разрешает разницу высот поддеревьев:
Повороты: восстановление баланса
Когда баланс нарушен, AVL делает **повороты** - локальные перестановки узлов.
Правый поворот (Left-Left case)
4 случая дисбаланса
| Случай | Дисбаланс | Решение |
|---|---|---|
| Left-Left | z.left.left | Один правый поворот |
| Right-Right | z.right.right | Один левый поворот |
| Left-Right | z.left.right | Лево + право поворот |
| Right-Left | z.right.left | Право + лево поворот |
Сколько операций нужно для балансировки после вставки в AVL?
Red-Black Tree: Менее строгий баланс
**Red-Black Tree** - более гибкое самобалансирующееся дерево.
**Правила Red-Black:**
- Каждый узел красный или чёрный
- Корень всегда чёрный
- Листья (NIL) чёрные
- Красный узел не может иметь красного ребёнка
- Все пути от узла до листьев содержат одинаковое число чёрных узлов
**Гарантия:** высота Red-Black ≤ 2·log₂(n+1). Менее строго чем AVL, но проще поддерживать.
Какое правило нарушает: красный узел с красным ребёнком?
AVL vs Red-Black: Что выбрать?
| Свойство | AVL | Red-Black |
|---|---|---|
| Строгость баланса | Высокая (разница ≤1) | Умеренная (≤2x) |
| Поиск | Немного быстрее | Чуть медленнее |
| Вставка/удаление | Больше поворотов | Меньше поворотов |
| Использование | Read-heavy workloads | Write-heavy workloads |
**Java TreeMap, C++ std::map, Linux kernel** используют Red-Black. **Базы данных с частыми чтениями** предпочитают AVL.
**На практике:** обе структуры дают O(log n). Разница в константах - важна только для высоконагруженных систем.
Для приложения с частыми вставками и редкими поисками лучше:
Итоги
- AVL: строгий баланс, разница высот ≤ 1
- Red-Black: мягче баланс, меньше поворотов
- Оба гарантируют O(log n) для всех операций
- AVL → чтение, Red-Black → запись
Следующие темы
От сбалансированных деревьев к специализированным структурам.
- Trie — Префиксные деревья для строк - другой угол на древовидные структуры
- B-tree — Сбалансированные деревья высокого порядка - основа индексов в БД
Связанные уроки
- ds-11-bst — Balanced trees extend BST with self-balancing operations
- ds-13-trie — Trie is another specialised tree for string keys
- ds-23-btree — B-tree generalises balanced BST for disk-based storage
- ds-06-hash-intro — Both support O(log n) ordered map; hash is O(1) unordered
- db-09-indexes-btree