Деревья и рекурсивный обход: основы нелинейных структур

От массивов к иерархиям: анатомия бинарного дерева и реализация на Python

Если нужно быстро находить элементы, мы используем отсортированный массив и бинарный поиск, получая время . Но если в эту коллекцию требуется постоянно добавлять новые данные, динамический массив ответит штрафом в на каждую вставку из-за необходимости сдвигать элементы в памяти. Классический связный список элегантно решает проблему вставки за , но полностью убивает быстрый поиск, так как мы не можем прыгнуть в его середину, возвращая алгоритм к линейному времени . Разрешение этого конфликта требует отказа от линейных структур данных в пользу ветвящихся.

Предел линейности и рождение графов

Массивы, стеки, очереди и связные списки объединяет одно свойство: у каждого элемента (кроме крайних) есть строго один предыдущий и строго один следующий. Это одномерное пространство.

Дерево ломает это ограничение. Это структура данных, в которой каждый элемент может иметь один «предыдущий» элемент и множество «следующих». В строгих терминах информатики дерево — это связный ациклический ориентированный граф.

Граф, потому что состоит из узлов, соединённых связями.

Ориентированный, потому что связи имеют направление (сверху вниз).

Ациклический, потому что, двигаясь по направлениям связей, невозможно вернуться в узел, в котором вы уже были.

Связный, потому что от вершины можно добраться до любого узла.

В алгоритмических секциях Яндекса подавляющее большинство задач связано со специфическим подтипом этой структуры — бинарным (двоичным) деревом. Правило бинарного дерева максимально простое: у любого узла может быть не более двух исходящих связей. Либо ноль, либо одна, либо две.

Анатомия бинарного дерева

Для работы с деревьями используется устоявшаяся терминология, смешивающая ботанику и генеалогию.

!Анатомия бинарного дерева и его основные компоненты

Узел (Node) — базовая единица дерева. Хранит полезное значение (число, строку, объект) и ссылки на дочерние узлы.

Корень (Root) — единственный узел в дереве, у которого нет родителя. Это точка входа в структуру. Любой обход дерева начинается с корня.

Родитель (Parent) и Ребёнок (Child) — относительные термины. Узел, имеющий исходящую ссылку, является родителем для узла, на который эта ссылка указывает. В бинарном дереве дети строго позиционированы: есть левый ребёнок и правый ребёнок.

Лист (Leaf) — узел, у которого нет детей (обе ссылки указывают на пустоту). Листья образуют нижние границы дерева.

Братья/Сёстры (Siblings) — узлы, имеющие общего родителя.

Поддерево (Subtree) — любой узел дерева вместе со всеми его потомками образует полноценное дерево. Это свойство рекурсивной вложенности — фундамент для всех алгоритмов обхода. Левый ребёнок корня является корнем всего левого поддерева.

Реализация на Python: класс TreeNode

В Python бинарное дерево не является встроенной коллекцией вроде list или dict. Оно конструируется из пользовательских объектов, связанных друг с другом ссылками. Стандартный класс, который вы встретите на платформах вроде LeetCode, выглядит так:

Механика работы здесь идентична двусвязному списку, но меняется семантика. Если в списке ссылки prev и next выстраивали элементы в линию, то left и right формируют ветвление.

Создадим простое дерево из трёх узлов:

В памяти компьютера нет единого непрерывного блока «дерево». Есть три разрозненных объекта в куче (heap). Объект root хранит число 10 и два адреса памяти, указывающие на объекты node_left и node_right. Переменные node_left.left и node_left.right по умолчанию равны None, что делает узел 5 листом.

Важный нюанс: переменная root в коде — это не само дерево. Это лишь ссылка на один конкретный узел. Но поскольку через этот узел можно по цепочке ссылок добраться до всех остальных элементов, мы технически отождествляем ссылку на корень со всем деревом. Потеряете ссылку на корень — сборщик мусора Python уничтожит всю структуру.

Метрики иерархии: Глубина против Высоты

При оценке сложности алгоритмов (особенно пространственной сложности рекурсии) критически важно понимать метрики дерева. Термины «глубина» и «высота» часто путают, хотя они измеряют разные векторы.

Глубина (Depth) узла — это количество рёбер от корня до этого узла. Глубина измеряется сверху вниз.

Глубина корня всегда равна 0.

Глубина детей корня равна 1.

Это показатель того, насколько глубоко узел «погружён» в структуру.

Высота (Height) узла — это максимальное количество рёбер от этого узла до самого дальнего листа в его поддереве. Высота измеряется снизу вверх.

Высота любого листа всегда равна 0.

Высота дерева в целом — это высота его корня.

Это показатель того, насколько длинная цепочка вызовов потребуется, чтобы добраться до самого дна.

Рассмотрим вырожденный случай: бинарное дерево, в котором каждый узел имеет только правого ребёнка. Структурно это просто связный список. Если в нём 5 узлов, то высота корня будет 4, а глубина последнего листа — 4. В таком дереве алгоритм спустится на 4 уровня вниз.

Если же 5 узлов распределить оптимально (корень, два ребёнка, и у одного из них два своих ребёнка), максимальная глубина составит всего 2. Разница между высотой вырожденного дерева и сбалансированного — это главная причина, по которой структуру дерева нужно контролировать.

Архитектурные формы бинарных деревьев

Алгоритмические задачи часто накладывают дополнительные условия на форму дерева. Понимание этих форм помогает выбрать правильный подход к решению.

Полное бинарное дерево (Full Binary Tree). Правило: у каждого узла либо 0, либо 2 ребёнка. Узлов с ровно одним ребёнком быть не должно. Такая структура часто возникает при парсинге математических выражений, где оператор (корень) всегда требует двух операндов (листьев).

Идеальное бинарное дерево (Perfect Binary Tree). Правило: все внутренние узлы имеют по два ребёнка, и абсолютно все листья находятся на одной глубине. Это максимально плотная упаковка узлов. Количество узлов на каждом уровне удваивается: 1, 2, 4, 8, 16. Общее число узлов в таком дереве высоты строго равно .

Завершённое бинарное дерево (Complete Binary Tree). Правило: все уровни, кроме, возможно, последнего, заполнены полностью. Последний уровень заполняется строго слева направо, без пропусков.

Именно завершённое дерево обладает уникальным свойством: его можно эффективно хранить в обычном одномерном массиве без использования объектов TreeNode и ссылок left/right.

Массивы под прикрытием: как LeetCode хранит деревья

Когда вы решаете задачу на LeetCode, на вход вашей функции подаётся объект TreeNode. Но в описании задачи (и в тестовых кейсах) дерево представлено в виде массива: [5, 4, 8, 11, null, 13, 4].

Это представление основано на обходе дерева по уровням (Level-order traversal) и математических свойствах индексов завершённого дерева.

!Представление идеального бинарного дерева в виде массива с формулами вычисления индексов

Если мы поместим корень дерева в массив под индексом , то для любого узла, находящегося по индексу , справедливы следующие формулы:

Индекс его левого ребёнка:

Индекс его правого ребёнка:

Индекс его родителя: (целочисленное деление)

Проверим на массиве [5, 4, 8, 11, null, 13, 4]:

Корень 5 имеет индекс 0.

Его левый ребёнок: . Под индексом 1 лежит 4.

Его правый ребёнок: . Под индексом 2 лежит 8.

Возьмём узел 4 (индекс 1). Его левый ребёнок: . Под индексом 3 лежит 11.

Правый ребёнок узла 4: . Под индексом 4 лежит null. Это означает, что у узла 4 нет правого ребёнка.

Значение null в массиве выполняет роль заполнителя (placeholder). Оно необходимо, чтобы сохранить математическую связь индексов для последующих узлов. Если бы мы просто пропустили null и сдвинули массив, формула указала бы на совершенно другой узел, разрушив виртуальную иерархию.

Такой формат хранения (неявная структура данных) крайне эффективен по памяти, так как не требует хранения 64-битных указателей на объекты. Он активно используется при реализации бинарных куч (Heaps) — структур, лежащих в основе приоритетных очередей.

Переход от линейных структур к деревьям требует смены ментальной модели. В массиве мы мыслили индексами и циклами for от начала до конца. В деревьях нет чёткого «начала» и «конца» в линейном понимании. Есть корень и разветвляющиеся пути. Чтобы пройти по всем узлам дерева, цикл while становится неудобным, так как после обработки левого поддерева нужно каким-то образом вспомнить о существовании правого и вернуться к нему. Эта потребность в запоминании отложенных задач делает деревья идеальным полигоном для применения рекурсии.

Рекурсия как инструмент обхода: три стратегии Depth-First Search (DFS)

Обход линейного массива — это движение по прямой: от нулевого индекса к последнему с помощью единственного цикла for. Структура данных сама диктует маршрут. Бинарное дерево лишает нас этой роскоши. Находясь в любом узле, алгоритм сталкивается с выбором: пойти в левое поддерево или в правое? Выбрав одно направление, необходимо сохранить информацию о том, что второе осталось неисследованным, чтобы позже к нему вернуться. Эту задачу управления маршрутом и возвратами берёт на себя рекурсия, превращая сложную навигацию по графу в несколько строк элегантного кода.

Алгоритмы, которые исследуют структуру вглубь до самых листьев, прежде чем вернуться к развилке, объединяются под общим названием Depth-First Search (DFS), или поиск в глубину. В контексте бинарных деревьев DFS — это не один конкретный алгоритм, а семейство из трёх стратегий. Физический маршрут движения по ссылкам left и right у них абсолютно одинаков, разница заключается лишь в том, в какой именно момент времени мы решаем «обработать» текущий узел (прочитать его значение, изменить или вывести на экран).

Анатомия рекурсивного обхода

Любая рекурсивная функция для работы с деревом строится на фундаменте из двух элементов: базового случая и рекурсивного шага.

Базовый случай — это условие остановки. В деревьях таким условием почти всегда является достижение пустого указателя (None). Когда алгоритм пытается спуститься в левого или правого потомка у листа (узла без детей), он натыкается на пустоту. В этот момент функция должна просто завершить работу и вернуть управление на уровень выше.

Рекурсивный шаг — это вызов функцией самой себя для левого и правого поддеревьев.

Если мы напишем функцию, содержащую только базовый случай и рекурсивные вызовы, она молча обойдёт всё дерево и завершится:

Этот код уже реализует полноценный поиск в глубину. Алгоритм спускается максимально влево, натыкается на None, возвращается, пробует спуститься вправо, снова возвращается и так далее. Чтобы обход приносил пользу, в этот каркас нужно добавить полезное действие — обработку узла. Место, куда мы вставим строку print(node.val) (или любую другую логику), определит одну из трёх стратегий DFS.

Три стратегии: вопрос времени

!Сравнение порядков обхода бинарного дерева

Pre-order (Прямой обход): Сверху вниз

В прямом обходе (NLR — Node, Left, Right) узел обрабатывается до того, как алгоритм погружается в его поддеревья.

Порядок выполнения строго соответствует названию: мы сначала фиксируем родителя, а затем исследуем его потомков. Если применить Pre-order к дереву, корнем которого является узел A, левым ребенком B, а правым C, порядок вывода будет A -> B -> C.

Эта стратегия незаменима, когда нам нужно передать какую-то информацию от корня к листьям или когда мы исследуем структуру дерева сверху вниз. Классический пример применения Pre-order — копирование (клонирование) дерева. Чтобы создать точную копию иерархии, нам нужно сначала создать корневой узел новой структуры, и только потом рекурсивно прикреплять к нему скопированные левое и правое поддеревья. Также прямой обход используется для сериализации дерева в строку, так как корень всегда оказывается первым элементом, что упрощает последующую десериализацию.

In-order (Симметричный обход): Слева направо

В симметричном обходе (LNR — Left, Node, Right) обработка узла происходит между визитами в левое и правое поддеревья.

Алгоритм сначала проваливается в самую левую ветку до упора. Только когда левое поддерево полностью исследовано, он возвращается к родителю, обрабатывает его, и затем уходит в правое поддерево. Для дерева из узлов A (корень), B (левый) и C (правый), порядок будет B -> A -> C.

In-order обладает важнейшим свойством, которое делает его фундаментом для многих алгоритмических задач: при обходе бинарного дерева поиска (BST) In-order посещает узлы в строго отсортированном порядке по возрастанию. Это происходит потому, что в BST все значения слева меньше корня, а все значения справа — больше. Сначала алгоритм собирает все меньшие элементы, затем берет сам корень, а затем собирает все большие элементы.

!Пошаговый In-order обход бинарного дерева

Post-order (Обратный обход): Снизу вверх

В обратном обходе (LRN — Left, Right, Node) узел обрабатывается только после того, как полностью обработаны оба его поддерева.

Это стратегия работы «снизу вверх». Листья обрабатываются первыми, корень дерева всегда обрабатывается самым последним. Для дерева A (корень), B (левый), C (правый) результат будет B -> C -> A.

Post-order критически важен для задач, где состояние или решение для родительского узла зависит от результатов, полученных от его детей. Например, невозможно вычислить общую сумму значений в дереве или его максимальную высоту, не зная высоту и суммы левого и правого поддеревьев. Сначала мы отправляем запросы вниз, ждем ответов от детей, и только получив их, вычисляем ответ для родителя.

Другой классический пример — безопасное удаление дерева из памяти (в языках с ручным управлением памятью, таких как C++). Нельзя удалить родительский узел до удаления его детей, иначе мы потеряем указатели на них и получим утечку памяти. Post-order гарантирует, что родитель будет уничтожен только после того, как его поддеревья полностью зачищены.

Механика невидимого маршрутизатора: стек вызовов

Секрет рекурсивного обхода кроется в том, что мы не управляем возвратами явно. За нас это делает стек вызовов (Call Stack) интерпретатора Python. Каждый раз, когда функция вызывает саму себя, текущее состояние (включая локальные переменные и место, где выполнение было приостановлено) сохраняется в памяти в виде фрейма (кадра).

Проследим этот процесс детально на примере In-order обхода небольшого дерева. Пусть корень имеет значение 4, его левый потомок 2, правый 6. У узла 2 есть левый потомок 1 и правый 3. Узлы 1, 3 и 6 являются листьями.

Вызываем inorder(4).

Функция для узла 4 не пуста. Выполняется строка inorder(node.left), то есть inorder(2). Выполнение функции для 4 ставится на паузу. В стек вызовов кладется фрейм [inorder(4) - пауза на строке 1].

Входим в inorder(2). Выполняется inorder(node.left), то есть inorder(1). В стек добавляется фрейм [inorder(2) - пауза на строке 1].

Входим в inorder(1). Выполняется inorder(node.left), то есть inorder(None). Стек: [inorder(4)], [inorder(2)], [inorder(1) - пауза].

Входим в inorder(None). Срабатывает базовый случай if node is None: return. Функция завершается мгновенно.

Управление возвращается к inorder(1). Пауза снимается. Выполняется следующая строка: print(1).

Выполняется третья строка: inorder(node.right), то есть inorder(None). Она также мгновенно возвращает управление.

Функция inorder(1) дошла до конца своего кода и завершается. Её фрейм удаляется из стека.

Управление возвращается к inorder(2). Снимается пауза. Выполняется print(2).

Выполняется inorder(node.right) для узла 2, то есть inorder(3). Стек: [inorder(4)], [inorder(2) - пауза на строке 3].

Узел 3 обрабатывается аналогично узлу 1: пытается пойти влево (возврат), печатает 3, пытается пойти вправо (возврат), завершается.

Функция inorder(2) завершается, фрейм удаляется.

Управление возвращается к самому первому вызову inorder(4). Выполняется print(4).

Выполняется inorder(node.right), то есть inorder(6). Узел 6 печатает себя и завершается.

Обход окончен. Выведенная последовательность: 1, 2, 3, 4, 6.

Стек вызовов работает как хлебные крошки, которые алгоритм оставляет на каждой развилке. Возврат из функции (return) — это шаг назад по этим крошкам к последнему неисследованному пути.

Пространственная и временная сложность

При анализе сложности алгоритмов обхода дерева важно разделять время выполнения и потребление памяти.

Временная сложность любого из трёх DFS обходов составляет , где — общее количество узлов в дереве. Причина кроется в базовой механике: алгоритм посещает каждый узел ровно один раз для выполнения полезного действия и совершает константное количество переходов по ссылкам left и right. Ни один узел не обрабатывается дважды, и ни один не пропускается. Константы отбрасываются, оставляя строгую линейную зависимость от размера данных.

С пространственной сложностью (вспомогательной памятью) ситуация сложнее. Сам алгоритм не создает новых массивов или хэш-таблиц, поэтому может показаться, что память равна . Однако, как мы выяснили при разборе стека вызовов, каждый вложенный рекурсивный вызов потребляет оперативную память для хранения фрейма.

Максимальное количество одновременно существующих фреймов в стеке в точности равно максимальной глубине погружения алгоритма, то есть высоте дерева . Поэтому пространственная сложность рекурсивного обхода составляет .

Значение критически зависит от формы дерева:

В лучшем случае, если дерево идеально сбалансировано (похоже на густую крону, где каждый уровень заполнен), его высота растет логарифмически относительно количества узлов. Пространственная сложность составит . Для дерева из миллиона узлов стек вызовов не превысит 20 фреймов.

В худшем случае, если дерево вырождено (каждый узел имеет только одного потомка, превращая дерево в связный список), высота дерева становится равна количеству узлов. Пространственная сложность деградирует до . Для вырожденного дерева из миллиона узлов потребуется миллион фреймов в стеке, что почти гарантированно приведет к ошибке RecursionError (переполнение стека) в Python, так как лимит глубины рекурсии по умолчанию составляет 1000 вызовов.

Понимание этой скрытой цены рекурсии необходимо при проектировании систем, работающих с глубокими структурами данных. Если форма дерева не гарантирует сбалансированности, рекурсивный обход может стать причиной падения программы.

Выбор стратегии: как не ошибиться

На практике выбор между Pre-order, In-order и Post-order редко бывает случайным. Он диктуется зависимостями внутри задачи:

Нужна ли родительскому узлу информация от потомков, чтобы вычислить свой результат? Если да (подсчет узлов, поиск максимальной глубины, проверка сбалансированности) — это строгий Post-order.

Важен ли порядок обработки элементов слева направо, особенно в контексте деревьев поиска? Если нужно получить отсортированный массив или найти следующий по величине элемент — это In-order.

Нужно ли передать состояние сверху вниз или скопировать структуру как есть? Если родитель должен быть обработан раньше детей — это Pre-order.

Освоение рекурсивного обхода требует изменения мышления. Вместо попыток проследить весь маршрут целиком, достаточно сфокусироваться на локальной задаче одного узла: что он должен сделать со своим значением и в какой момент он должен делегировать работу своим левому и правому поддеревьям. Стек вызовов гарантирует, что эта локальная логика корректно масштабируется на дерево любого размера.