В прошлом блоке мы разобрали кучу (heap) и приоритетную очередь — структуры, которые под капотом используют особое бинарное дерево, хранящееся в массиве. Теперь самое время разобраться с деревьями как таковыми: что это, как устроены, как с ними работать в коде.

До сих пор мы работали с линейными структурами: массивы, списки, стеки, очереди — элементы идут один за другим, как вагоны поезда. Но реальные данные часто устроены иерархически. Папки внутри папок — это иерархия. Отделы внутри компании — иерархия. Теги внутри HTML-страницы — иерархия. JSON-ответ от API — тоже иерархия. Для таких данных нужна структура, которая ветвится. Эта структура называется дерево.

Вы уже работаете с деревьями каждый день, просто не думаете об этом. Файловая система Windows или Linux — дерево. DOM-страница в браузере — дерево. Дерево разбора XML и JSON — тоже дерево. Дерево решений в игровом ИИ — тоже дерево. Оглавление этого курса — курс → блоки → уроки — и то дерево. Когда компилятор C# читает ваш код, он строит AST (Abstract Syntax Tree) — абстрактное синтаксическое дерево. Буквально каждое выражение вида a + b * c превращается в дерево с операторами в узлах и операндами в листьях.

Почему деревья так везде? Потому что иерархия — самый естественный способ организовать сложные данные. Генеалогическое древо семьи: каждый человек — это узел, его дети — его потомки. Организационная схема компании: CEO наверху, вице-президенты ниже, менеджеры ещё ниже. Мозг прекрасно справляется с иерархическими структурами, и программисты это давно поняли.

Почему «бинарное» — самое важное? Потому что на нём построены бинарные деревья поиска (BST), кучи (heap), AVL-деревья, красно-чёрные деревья — и все они живут внутри баз данных, файловых систем и стандартных библиотек. SortedDictionary в C# — красно-чёрное дерево. TreeMap в Java — тоже. std::map в C++ — тоже. Индексы в PostgreSQL — B-деревья. В алгоритмах машинного обучения деревья решений (decision trees) и случайные леса (random forests) — бинарные деревья. Понимание бинарных деревьев — ключ ко всему этому.

Разберём терминологию по схеме выше — она пригодится во всех следующих уроках. | Термин | Что означает | На схеме выше | | --- | --- | --- | | Корень (Root) | Верхний узел, у которого нет родителя | 10 | | Лист (Leaf) | Узел без потомков | 3, 7, 12, 20 | | Родитель (Parent) | Узел, у которого есть потомки | 10 — родитель 5 и 15 | | Потомок (Child) | Узел, у которого есть родитель | 5 — левый потомок 10 | | Братья (Siblings) | Узлы с одним и тем же родителем | 5 и 15 — братья (оба дети 10) | | Поддерево (Subtree) | Узел + все его потомки = тоже дерево | Узел 5 с детьми 3 и 7 — поддерево | | Уровень (Level) | Расстояние от корня в рёбрах (= глубина узла) | 10 на уровне 0, 5 и 15 на уровне 1 | | Глубина (Depth) | Количество рёбер от корня до конкретного узла | Корень: 0, узел 7: 2 | | Высота дерева (Height) | Рёбра на самом длинном пути от корня до листа | Высота: 2 |

Частая путаница: глубина считается от корня вниз, высота — от листьев вверх. Глубина узла 7 = 2 (два ребра от корня). Высота дерева = 2 (два ребра от корня до самого далёкого листа). У листа высота = 0. У пустого дерева принято считать высоту = -1. Запомните: глубина — «откуда ты», высота — «сколько ты можешь дотянуться вниз».

Деревья в программировании растут вниз. Корень — сверху, листья — снизу. Наоборот, чем в природе. Программисты — народ своеобразный. Не все бинарные деревья одинаковы. Три важных разновидности, которые встречаются в теории и на практике:

Полное бинарное дерево (Full Binary Tree) — каждый узел имеет либо 0, либо 2 потомка. Никаких «одиноких» детей. Если у узла есть хотя бы один ребёнок — значит их ровно двое.

Заполненное (Complete) бинарное дерево — все уровни полностью заполнены, кроме, возможно, последнего. Последний уровень заполнен слева направо без пропусков. Именно так устроена куча (heap) из прошлого блока — её хранят в массиве именно потому, что complete tree имеет чёткую индексацию: левый потомок узла i хранится в позиции 2i+1, правый — в 2i+2.

Совершенное (Perfect) бинарное дерево — все внутренние узлы имеют ровно двух потомков, а все листья находятся на одном уровне. Редкость в реальных данных, но идеальный случай для анализа сложности: дерево высоты h содержит ровно 2^(h+1) - 1 узлов. При h=10 — это 2047 узлов, при h=20 — больше двух миллионов. Именно поэтому O(log n) так мощно. Реализуем бинарное дерево на C#. Начнём с узла — он элементарен:

public class TreeNode
{
    public int Val;
    public TreeNode? Left;
    public TreeNode? Right;

    public TreeNode(int val, TreeNode? left = null, TreeNode? right = null)
    {
        Val = val;
        Left = left;
        Right = right;
    }
}

Три поля: значение, левый потомок, правый потомок. Знак ? после TreeNode означает nullable reference — потомок может быть null (тогда узел является листом). Конструктор с параметрами по умолчанию позволяет строить дерево вложенными вызовами:

// Построим дерево со схемы выше
var root = new TreeNode(10,
    new TreeNode(5,
        new TreeNode(3),
        new TreeNode(7)),
    new TreeNode(15,
        new TreeNode(12),
        new TreeNode(20))
);

// Или строим пошагово
var node5 = new TreeNode(5);
node5.Left  = new TreeNode(3);
node5.Right = new TreeNode(7);
var root2 = new TreeNode(10, node5, new TreeNode(15));

В продакшен-коде деревья строятся алгоритмически: BST вставляет узлы по правилу «меньше — налево, больше — направо», куча строится из массива, trie — из набора строк. Ручная сборка нужна в тестах и задачах на собеседованиях. Теперь напишем несколько рекурсивных функций. Все они следуют одному паттерну: проверь null — обработай текущий узел — рекурсия на левое поддерево — рекурсия на правое поддерево.

Высота дерева — рекурсия в чистом виде:

static int Height(TreeNode? node)
{
    if (node == null) return -1;  // Пустое дерево — высота -1
    return 1 + Math.Max(Height(node.Left), Height(node.Right));
}

Console.WriteLine(Height(root));  // 2

Три строки логики: базовый случай — null (высота пустого дерева = -1). Иначе: высота = 1 + максимум из высот левого и правого поддерева. Для листа оба поддерева null, возвращают -1, поэтому высота листа = 1 + max(-1, -1) = 0. Видите, как рекурсия и деревья созданы друг для друга?

Количество узлов:

static int CountNodes(TreeNode? node)
{
    if (node == null) return 0;
    return 1 + CountNodes(node.Left) + CountNodes(node.Right);
}

Console.WriteLine(CountNodes(root));  // 7

Логика простая: пустое дерево содержит 0 узлов. Непустое — 1 (текущий узел) плюс количество узлов в левом поддереве плюс правом.

Сумма всех значений:

static int Sum(TreeNode? node)
{
    if (node == null) return 0;
    return node.Val + Sum(node.Left) + Sum(node.Right);
}

Console.WriteLine(Sum(root));  // 10+5+15+3+7+12+20 = 72

Поиск значения в произвольном бинарном дереве (без гарантий порядка):

static bool Search(TreeNode? node, int target)
{
    if (node == null) return false;
    if (node.Val == target) return true;
    return Search(node.Left, target) || Search(node.Right, target);
}

Console.WriteLine(Search(root, 7));   // True
Console.WriteLine(Search(root, 99));  // False

Поиск в обычном бинарном дереве (не BST) — это полный обход: проверяем все узлы, O(n). В следующем уроке мы добавим правило порядка — и поиск ускорится до O(log n).

Все четыре функции — один и тот же шаблон. Это универсальный паттерн работы с деревьями. Именно поэтому рекурсия и деревья — лучшие друзья: каждое поддерево само по себе является деревом, и вы просто вызываете ту же функцию для меньшей версии задачи. Помните, как в блоке рекурсии мы решали задачи по принципу «реши для меньшего случая»? Здесь это работает идеально.

Подведём итог. Дерево — иерархическая структура: корень, узлы, листья, поддеревья. Бинарное дерево — максимум два потомка у каждого узла. Реализация — класс с тремя полями: Val, Left, Right. Глубина считается от корня вниз, высота — от листьев вверх, у пустого дерева = -1. Разновидности: Full (0 или 2 ребёнка), Complete (последний уровень слева), Perfect (все уровни полны). Все операции — рекурсия по одному паттерну. В C# SortedDictionary и SortedSet — деревья под капотом.

Дерево — иерархическая структура данных: узлы связаны отношением «родитель — потомок». Корень — верхний узел без родителя, листья — узлы без потомков. Братья — узлы с одним родителем.

Бинарное дерево — каждый узел имеет не более двух потомков (левый, правый). Реализация: класс с тремя полями — значение, левый потомок, правый потомок.

Глубина vs Высота: глубина узла = рёбра от корня до него (сверху вниз). Высота дерева = рёбра на самом длинном пути от корня до листа (снизу вверх). У пустого дерева высота = -1, у листа = 0.

Разновидности: Full (каждый узел — 0 или 2 ребёнка), Complete (все уровни полны, последний заполнен слева), Perfect (все уровни полностью заполнены).

Универсальный шаблон — обработай текущий узел + рекурсия на Left + рекурсия на Right. Высота, подсчёт, поиск, сумма — один и тот же паттерн.

Деревья повсюду — файловая система, DOM, AST компилятора, B-деревья в БД, стандартные библиотеки (SortedDictionary, SortedSet), алгоритмы ML.