Деревья
Деревья — иерархические структуры данных. BST: поиск за O(log n). AVL и красно-чёрные — самобалансирующиеся. B-деревья — основа PostgreSQL и MySQL.
Бинарные деревья поиска (BST)
Дерево с упорядочением: левое поддерево < узел < правое поддерево. Операции поиск/вставка/удаление O(h), где h — высота. В худшем случае h = n (вырождение в список). Среднее h = log n.
AVL-деревья — сбалансированные BST
Самобалансирующееся бинарное дерево поиска (Адельсон-Вельский, Ландис, 1962). Высота поддеревьев различается не более чем на 1. Повороты (LL, RR, LR, RL) при нарушении баланса. Гарантированная высота O(log n).
Красно-чёрные деревья
Самобалансирующееся BST с цветом узла (красный/чёрный). Правила: корень чёрный, красный узел имеет чёрных детей, все пути от корня до листьев содержат одинаковое число чёрных узлов. Высота ≤ 2 log(n+1).
B-деревья — многопутевые деревья
Дерево с множественными ключами в узле (порядок t: от t-1 до 2t-1 ключей). Все листья на одном уровне. Применяются в базах данных и файловых системах (минимизация операций диска). B+-дерево: все данные в листьях.
Префиксные деревья (Trie)
Дерево для хранения строк, где путь от корня — префикс. Каждый узел содержит символ. Операции O(m), где m — длина строки. Применение: автодополнение, словари, IP-маршрутизация. Память O(ALPHABET_SIZE × N).
Кучи (Heap) — бинарные кучи
Полное бинарное дерево с условием упорядоченности: max-heap (родитель ≥ детей), min-heap (родитель ≤ детей). Реализация массивом: родитель i, дети 2i+1 и 2i+2. Применение: priority queue, HeapSort.
Сравнение AVL и красно-чёрных деревьев
AVL: строже сбалансировано (высота ≤ 1.44 log n), больше ротаций при вставке. Red-Black: меньше ротаций (max 3), быстрее вставка/удаление. AVL быстрее поиск. C++ map использует Red-Black.
Бинарное дерево поиска (BST)
Каждый узел: левые потомки меньше, правые больше. Поиск/вставка/удаление O(log n) в среднем, O(n) в худшем (вырожденное). Основа для сбалансированных деревьев.
АВЛ-дерево
Самобалансирующееся BST (1962, Адельсон-Вельский и Ландис). Разница высот поддеревьев ≤ 1. Гарантированно O(log n). Повороты при дисбалансе. Строже красно-чёрных.
Красно-чёрное дерево
Самобалансирующееся BST с цветовой маркировкой (1972, Р. Байер). Менее строгий баланс чем AVL, но меньше перебалансировок. Используется в std::map, TreeMap.
B-дерево
Многопутевое сбалансированное дерево для дисковых систем (1970, Р. Байер). Узлы содержат множество ключей. Минимизирует дисковые операции. Основа файловых систем и БД.
Префиксное дерево (Trie)
Дерево для хранения строк по префиксам. Поиск O(m) где m — длина ключа. Применения: автодополнение, проверка орфографии, IP-маршрутизация (PATRICIA).