Деревья и их свойства

Деревья - самая распространённая структура данных после массивов. Файловая система - дерево. AST в компиляторе - дерево. DOM в браузере - дерево. Иерархия классов - дерево. Decision Tree в ML - дерево. Понять деревья значит понять половину CS.

• **Компиляторы:** AST (Abstract Syntax Tree) - промежуточное представление кода между парсингом и генерацией байткода
• **Базы данных:** B-Tree и B+-Tree - структуры индексов в PostgreSQL и MySQL, гарантируют O(log n) операции
• **ML:** Decision Tree и Random Forest - деревья решений для классификации, интерпретируемы в отличие от нейросетей
• **Git:** дерево объектов (blob, tree, commit) - основа хранения истории проекта

Предварительные знания

• Graph Theory Fundamentals

Определение и свойства дерева

Дерево - это связный граф без циклов. Все следующие утверждения эквивалентны для графа с n вершинами: 1. G - дерево 2. G связный и имеет n−1 рёбер 3. G ациклический и имеет n−1 рёбер 4. между любыми двумя вершинами существует ровно один простой путь.

**Ключевое свойство:** дерево с n вершинами имеет ровно n−1 рёбер. Добавление любого ребра создаёт ровно один цикл. Удаление любого ребра делает граф несвязным.

Файловая система - классическое дерево: корень (/), каждый файл/директория имеет ровно одного родителя, и только один путь ведёт от корня к любому файлу.

Остовные деревья: Крускал и Прим

Остовное дерево (spanning tree) связного графа G - подграф, содержащий все вершины G и являющийся деревом. **Минимальное остовное дерево (MST)** - остовное дерево с наименьшей суммой весов рёбер. MST решает задачу: «соединить все вершины с минимальной стоимостью».

**Алгоритм Крускала:** жадно добавляет рёбра в порядке возрастания веса, пропуская рёбра, создающие цикл (Union-Find). Сложность: O(E log E). **Алгоритм Прима:** растит дерево из одной вершины, каждый шаг добавляет минимальное ребро к текущему дереву. Сложность: O(E log V) с приоритетной очередью.

Практическое применение MST: прокладка кабельных сетей и трубопроводов (соединить N точек с минимальной длиной кабеля), кластеризация данных (удаление самого тяжёлого ребра MST разбивает граф на 2 кластера), построение приближённых решений задачи коммивояжёра.

Крускал удобен, когда рёбра уже отсортированы или рёбер мало (разреженный граф). Прим эффективнее на плотных графах, где E ≈ V².

Бинарные деревья

Бинарное дерево - корневое дерево, где у каждого узла не более двух потомков: левый и правый. **BST (бинарное дерево поиска)**: левый потомок < родитель < правый потомок. BST позволяет искать, вставлять и удалять за O(log n) в среднем при сбалансированном дереве.

**Высота дерева** h определяет производительность: в сбалансированном BST h = O(log n), операции O(log n). В вырожденном (все правые потомки) h = n, операции O(n). **AVL и Red-Black деревья** - самобалансирующиеся BST, гарантирующие h = O(log n).

Бинарные деревья в компиляторах: **AST (Abstract Syntax Tree)** - представление выражений. Выражение `(a + b) * c` - дерево с `*` в корне, `+` в левом поддереве, `c` в правом. Вычисление AST - обход дерева в порядке postorder.

Несбалансированный BST после N последовательных вставок возрастающих значений деградирует до связного списка: O(n) поиск вместо O(log n). В реальных проектах используйте TreeMap / SortedDict, реализованные на самобалансирующихся деревьях.

Обходы деревьев

Три классических обхода бинарного дерева различаются порядком посещения узлов относительно поддеревьев: **preorder** (корень → лево → право), **inorder** (лево → корень → право), **postorder** (лево → право → корень). Каждый нужен для разных задач.

**Inorder обход BST всегда даёт отсортированную последовательность.** Это фундаментальный факт: именно поэтому BST используют для реализации sorted sets и ordered maps в стандартных библиотеках.

Компилятор вычисляет AST через **postorder**: сначала рекурсивно вычисляются операнды (поддеревья), затем применяется операция корня. Для `(3 + 4) * 2`: вычисляется 3, затем 4, затем 3+4=7, затем 2, затем 7*2=14.

Ключевые идеи

• **Дерево = связный граф без циклов** с ровно n−1 рёбрами для n вершин
• **MST:** минимальное остовное дерево - Крускал (сортировка рёбер + Union-Find) или Прим (жадный рост от вершины)
• **BST:** бинарное дерево поиска - O(log n) в среднем, O(n) в вырожденном случае
• **Inorder BST = отсортированная последовательность** - фундаментальное свойство
• **Обходы:** preorder для сериализации, inorder для сортировки, postorder для вычислений снизу вверх

Связанные темы

Деревья - специальный случай графов с дополнительными ограничениями.

• Теория графов: основы — Дерево - частный случай графа: связный, ациклический
• Планарность и раскраска — Все деревья - планарные графы с хроматическим числом ≤ 2
• Потоки в сетях — BFS/DFS на деревьях - основа алгоритмов поиска путей

Вопросы для размышления

• Почему inorder обход BST даёт элементы в отсортированном порядке? Докажите это для конкретного примера.
• Чем Крускал лучше Прима для разреженных графов и почему?
• Если добавить одно ребро в дерево из n вершин, сколько циклов появится? Почему ровно один?

Связанные уроки

• alg-18-topological