Дерево — иерархическая структура данных: один корень, каждый узел имеет родителя и любое число потомков, циклов нет. Основа баз данных, файловых систем и компиляторов.
💻Деревья
Деревья — иерархические структуры данных. BST: поиск за O(log n). AVL и красно-чёрные — самобалансирующиеся. B-деревья — основа PostgreSQL и MySQL.
Загрузка карты...
Дерево — это граф без циклов
Файловая система на компьютере — дерево. Дерево решений в машинном обучении — дерево. HTML-страница (DOM) — дерево. Иерархия папок, XML, JSON — везде деревья.
Дерево: один корень, каждый узел имеет родителя (кроме корня) и любое число детей. Нет циклов. Это делает деревья идеальными для иерархических данных и быстрого поиска.
Бинарное дерево поиска (BST)
Самая простая форма. Правило: левый ребёнок меньше родителя, правый — больше. Поиск, вставка, удаление — все O(h), где h — высота дерева.
Если дерево сбалансировано — h = log n. Из миллиона элементов найдёшь за 20 шагов. Но BST без балансировки может деградировать: если вставлять элементы по возрастанию, получится список, h = n, всё за O(n).
Сравнение деревьев
| Структура | Поиск | Вставка | Память | Применение |
|---|---|---|---|---|
| BST (несбалансированный) | O(n)* | O(n)* | O(n) | Учебные задачи |
| AVL | O(log n) | O(log n) | O(n) | Частое чтение |
| Красно-чёрное | O(log n) | O(log n) | O(n) | STL, TreeMap |
| B-дерево | O(log n) | O(log n) | O(n) | Базы данных, диск |
| Trie | O(m) | O(m) | O(n·m) | Строки, автодополнение |
| Heap (куча) | O(n) | O(log n) | O(n) | Очереди с приоритетами |
Сравнительная таблица: анализ различий
AVL-деревья: автоматический баланс
Придуманы советскими математиками Адельсоном-Вельским и Ландисом в 1962 году — первое самобалансирующееся дерево. Правило: разница высот левого и правого поддерева любого узла — не более 1. При нарушении — автоматический поворот.
Гарантирует h = O(log n) всегда. Поиск чуть медленнее красно-чёрного из-за частых поворотов, но идеален для задач с частым чтением.
Красно-чёрные деревья
Более relaxed балансировка: высота гарантированно не больше 2 log n. Это чуть менее строго, чем AVL, зато вставка и удаление требуют меньше поворотов — быстрее на запись.
Используются везде: C++ STL (map, set), Java TreeMap, Linux планировщик задач (CFS). Внутри большинства языковых стандартных библиотек — красно-чёрные деревья.
B-деревья: для дисков и баз данных
BST, AVL, красно-чёрные — для оперативной памяти. Когда данных больше, чем помещается в RAM, нужно читать с диска. Диск в тысячи раз медленнее памяти.
B-дерево — многопутевое: каждый узел хранит сотни ключей и имеет сотни детей. Высота дерева при миллиарде записей — всего 3–4. Три чтения с диска вместо 30. PostgreSQL, MySQL, MongoDB — все используют B-деревья или B+-деревья для индексов.
Trie: специализация для строк
Prefix tree (Trie) — каждый узел — символ. Слово — путь от корня. Поиск слова «apple» — 5 шагов независимо от словаря. Используется: автодополнение, поиск по префиксу, словарные проверки. Google подсказывает поисковые запросы именно так.
Высота дерева с 1 млн элементов
Высота (шагов)
Как выбрать структуру
Частый поиск, редкая запись — AVL. Частая запись — красно-чёрное дерево. Данные на диске — B-дерево. Работа со строками — Trie. Просто нужна очередь с приоритетами — Heap (куча).
❓Часто задаваемые вопросы
Без неё дерево может стать «списком» высотой n. Поиск займёт O(n) вместо O(log n). Балансировка гарантирует высоту O(log n) всегда.