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

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

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

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

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

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

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

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

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

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

Узел (Node) — базовая единица дерева. Хранит полезное значение (число, строку, объект) и ссылки на дочерние узлы.
Корень (Root) — единственный узел в дереве, у которого нет родителя. Это точка входа в структуру. Любой обход дерева начинается с корня.
Родитель (Parent) и Ребёнок (Child) — относительные термины. Узел, имеющий исходящую ссылку, является родителем для узла, на который эта ссылка указывает. В бинарном дереве дети строго позиционированы: есть левый ребёнок и правый ребёнок.
Лист (Leaf) — узел, у которого нет детей (обе ссылки указывают на пустоту). Листья образуют нижние границы дерева.
Братья/Сёстры (Siblings) — узлы, имеющие общего родителя.
Поддерево (Subtree) — любой узел дерева вместе со всеми его потомками образует полноценное дерево. Это свойство рекурсивной вложенности — фундамент для всех алгоритмов обхода. Левый ребёнок корня является корнем всего левого поддерева.

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

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

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

# Создаем изолированные узлы в памяти
root = TreeNode(10)
node_left = TreeNode(5)
node_right = TreeNode(15)

# Выстраиваем иерархию через ссылки
root.left = node_left
root.right = node_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. Разница между высотой вырожденного дерева $O(N)$ и сбалансированного $O(\log N)$ — это главная причина, по которой структуру дерева нужно контролировать.

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

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

Полное бинарное дерево (Full Binary Tree). Правило: у каждого узла либо 0, либо 2 ребёнка. Узлов с ровно одним ребёнком быть не должно. Такая структура часто возникает при парсинге математических выражений, где оператор (корень) всегда требует двух операндов (листьев).
Идеальное бинарное дерево (Perfect Binary Tree). Правило: все внутренние узлы имеют по два ребёнка, и абсолютно все листья находятся на одной глубине. Это максимально плотная упаковка узлов. Количество узлов на каждом уровне удваивается: 1, 2, 4, 8, 16. Общее число узлов в таком дереве высоты $h$ строго равно $2^{h+1} - 1$ .
Завершённое бинарное дерево (Complete Binary Tree). Правило: все уровни, кроме, возможно, последнего, заполнены полностью. Последний уровень заполняется строго слева направо, без пропусков.

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

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

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

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

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

Индекс его левого ребёнка: $2i + 1$
Индекс его правого ребёнка: $2i + 2$
Индекс его родителя: $(i - 1) // 2$ (целочисленное деление)

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

Корень 5 имеет индекс 0.
Его левый ребёнок: $2 \times 0 + 1 = 1$ . Под индексом 1 лежит 4.
Его правый ребёнок: $2 \times 0 + 2 = 2$ . Под индексом 2 лежит 8.
Возьмём узел 4 (индекс 1). Его левый ребёнок: $2 \times 1 + 1 = 3$ . Под индексом 3 лежит 11.
Правый ребёнок узла 4: $2 \times 1 + 2 = 4$ . Под индексом 4 лежит null. Это означает, что у узла 4 нет правого ребёнка.

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

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

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

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

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

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

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

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

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

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

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

def traverse(node):
    if node is None:
        return

    traverse(node.left)
    traverse(node.right)

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

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

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

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

def preorder(node):
    if node is None:
        return

    print(node.val)      # 1. Действие
    preorder(node.left)  # 2. Левое поддерево
    preorder(node.right) # 3. Правое поддерево

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

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

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

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

def inorder(node):
    if node is None:
        return

    inorder(node.left)   # 1. Левое поддерево
    print(node.val)      # 2. Действие
    inorder(node.right)  # 3. Правое поддерево

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

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

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

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

def postorder(node):
    if node is None:
        return

    postorder(node.left)   # 1. Левое поддерево
    postorder(node.right)  # 2. Правое поддерево
    print(node.val)        # 3. Действие

Это стратегия работы «снизу вверх». Листья обрабатываются первыми, корень дерева всегда обрабатывается самым последним. Для дерева 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 обходов составляет $O(N)$ , где $N$ — общее количество узлов в дереве. Причина кроется в базовой механике: алгоритм посещает каждый узел ровно один раз для выполнения полезного действия и совершает константное количество переходов по ссылкам left и right. Ни один узел не обрабатывается дважды, и ни один не пропускается. Константы отбрасываются, оставляя строгую линейную зависимость от размера данных.

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

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

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

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

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

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

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

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

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

Бинарное дерево поиска (BST): эффективный поиск, вставка и валидация структуры

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

Бинарное дерево поиска (Binary Search Tree, BST) вводит фундаментальное правило организации данных — инвариант BST. Это правило звучит так: для любого узла $X$ все значения в его левом поддереве должны быть строго меньше значения $X$ , а все значения в его правом поддереве — строго больше значения $X$ .

Ключевое слово здесь — «поддереве». Ошибка многих начинающих разработчиков заключается в том, что они применяют правило только к непосредственным детям узла. Однако инвариант требует, чтобы свойство выполнялось для всех потомков на любой глубине. Если корень дерева имеет значение 10, то нигде в его левой ветви, даже на глубине в сто уровней, не может появиться значение 11.

Обычно в классическом BST дубликаты не допускаются. Если бизнес-логика требует хранения одинаковых значений, их либо помещают строго в правое поддереве (допуская условие $\geq$ ), либо добавляют в узел счетчик частоты. В рамках алгоритмических задач по умолчанию предполагается строгое неравенство.

Механика поиска: бинарный поиск на графах

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

Рекурсивная реализация этого процесса выглядит лаконично и естественно отражает саму структуру дерева.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def search_bst(root: TreeNode, target: int) -> TreeNode:
    # Базовый случай: дошли до пустого узла или нашли цель
    if root is None or root.val == target:
        return root

    # Рекурсивный шаг: выбираем направление
    if target < root.val:
        return search_bst(root.left, target)
    else:
        return search_bst(root.right, target)

Каждый рекурсивный вызов отсекает ровно одну ветвь дерева. Временная сложность такого алгоритма напрямую зависит от высоты дерева $H$ и составляет $O(H)$ .

Если дерево идеально сбалансировано (каждый уровень заполнен полностью), при каждом сравнении мы отбрасываем ровно половину оставшихся узлов. В этом случае высота дерева логарифмически зависит от количества узлов, и сложность поиска составляет $O(\log N)$ . Это колоссальный прирост производительности: для миллиарда элементов потребуется не более 30 сравнений.

Однако, если элементы добавлялись в отсортированном порядке (например, 1, 2, 3, 4, 5), каждый новый узел будет становиться правым потомком предыдущего. Дерево выродится в связный список. В таком вырожденном дереве высота $H$ равна количеству узлов $N$ , и временная сложность поиска деградирует до $O(N)$ .

Пространственная сложность рекурсивного поиска также составляет $O(H)$ из-за затрат памяти на стек вызовов. Примечательно, что поиск в BST легко переписать в итеративном виде, используя цикл while. Это снизит пространственную сложность до $O(1)$ , так как нам потребуется только один указатель, перемещающийся по узлам, без сохранения контекста предыдущих шагов в стеке.

Вставка новых узлов: формирование структуры

Добавление нового элемента в BST тесно связано с алгоритмом поиска. Чтобы структура сохранила свой инвариант, новый узел всегда должен добавляться в качестве листа (leaf node) в ту позицию, где алгоритм поиска завершился бы неудачей (нашел бы None).

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

def insert_into_bst(root: TreeNode, val: int) -> TreeNode:
    # Если дерево пустое, новый узел становится корнем
    if not root:
        return TreeNode(val)

    # Если значение меньше, идем влево
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    # Если значение больше, идем вправо
    elif val > root.val:
        root.right = insert_into_bst(root.right, val)

    # Возвращаем неизмененный корень текущего поддерева
    return root

При рекурсивной вставке происходит важный процесс перестраивания связей. Вызов insert_into_bst(root.left, val) возвращает узел, который должен стать новым левым потомком. В 99% случаев это будет тот же самый узел, который был там раньше. Но в момент достижения базового случая (not root), функция вернет свежесозданный TreeNode, и именно он будет присвоен в root.left или root.right родителя.

Временная сложность вставки также составляет $O(H)$ . Мы делаем ровно один проход от корня до листа. Алгоритм не требует сдвига элементов, как при вставке в середину массива, что делает BST крайне привлекательной структурой для динамически меняющихся наборов данных.

Валидация BST: ловушка локальных проверок

Одной из самых частых задач на алгоритмических секциях (известной как LeetCode 98: Validate Binary Search Tree) является проверка того, является ли произвольное бинарное дерево корректным BST.

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

# ОШИБОЧНЫЙ ПОДХОД
def is_valid_bst_wrong(root: TreeNode) -> bool:
    if not root:
        return True

    if root.left and root.left.val >= root.val:
        return False
    if root.right and root.right.val <= root.val:
        return False

    return is_valid_bst_wrong(root.left) and is_valid_bst_wrong(root.right)

Этот код вернет True для дерева, которое не является BST. Рассмотрим структуру: корень имеет значение 5. Его правый ребенок — 7. Левый ребенок узла 7 имеет значение 4. Локальные проверки пройдут успешно: 7 больше 5, а 4 меньше 7. Но узел со значением 4 находится в правом поддереве корня 5, что грубо нарушает инвариант BST (все элементы правого поддерева должны быть больше 5).

Проблема заключается в том, что узел «забывает» глобальные ограничения, наложенные на него его предками. Узел 4 знает, что он должен быть меньше 7, но он «не знает», что он также обязан быть больше 5.

Нисходящая валидация: передача границ

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

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

Используя стратегию Pre-order (сначала проверяем сам узел, затем идем к детям), мы можем реализовать надежную валидацию:

def is_valid_bst(root: TreeNode) -> bool:
    def validate(node: TreeNode, low: float, high: float) -> bool:
        # Пустое дерево всегда валидно
        if not node:
            return True

        # Проверяем нарушение глобальных границ
        if node.val <= low or node.val >= high:
            return False

        # Рекурсивно проверяем поддеревья с обновленными границами
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))

    return validate(root, float('-inf'), float('inf'))

В примере с некорректным узлом 4 процесс будет выглядеть так:

Корень 5 проверяется с границами (-inf, inf). Валидно.
Переход вправо к узлу 7. Нижняя граница обновляется до 5. Диапазон для 7: (5, inf). Валидно.
Переход влево от 7 к узлу 4. Верхняя граница обновляется до 7. Диапазон для 4 становится (5, 7).
Значение 4 не попадает в диапазон (5, 7), так как $4 \leq 5$ . Алгоритм корректно возвращает False.

Сложность этого алгоритма по времени составляет $O(N)$ , так как в худшем случае нам придется посетить каждый узел дерева ровно один раз, чтобы убедиться в его корректности. Пространственная сложность — $O(H)$ на поддержание стека вызовов.

Восходящая валидация: использование In-order обхода

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

Если применить In-order обход к корректному бинарному дереву поиска, мы посетим все его узлы в строго возрастающем порядке. Это прямое следствие инварианта: мы сначала обрабатываем все элементы, которые меньше текущего, затем сам элемент, а затем все, которые больше.

Следовательно, для валидации BST достаточно выполнить In-order обход и убедиться, что каждое следующее посещенное значение строго больше предыдущего. Нам не нужно собирать все значения в массив (что потребовало бы $O(N)$ дополнительной памяти), достаточно хранить только значение предыдущего посещенного узла.

class Solution:
    def __init__(self):
        # Храним значение предыдущего посещенного узла
        self.prev = float('-inf')

    def is_valid_bst_inorder(self, root: TreeNode) -> bool:
        if not root:
            return True

        # 1. Обходим левое поддерево
        if not self.is_valid_bst_inorder(root.left):
            return False

        # 2. Обрабатываем текущий узел
        if root.val <= self.prev:
            return False
        self.prev = root.val

        # 3. Обходим правое поддерево
        return self.is_valid_bst_inorder(root.right)

Этот подход также работает за $O(N)$ времени и $O(H)$ памяти. Его преимущество заключается в том, что при обнаружении первого же нарушения порядка (например, встретили 4 после 7) алгоритм немедленно прерывается благодаря раннему возврату False, не обходя оставшуюся часть дерева.

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

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

В идеальном мире поиск в бинарном дереве работает за логарифмическое время. Но, как мы выяснили ранее, при неудачной последовательности вставок дерево может выродиться в связный список, и скорость поиска рухнет до $O(N)$ . Чтобы алгоритмически предотвратить эту катастрофу, структура должна уметь оценивать саму себя. Главная метрика «здоровья» дерева — это его высота.

Вычисление высоты: мыслим снизу вверх

Вспомним определение: высота узла — это максимальное расстояние от него до самого глубокого листа в его поддереве.

Если мы попытаемся вычислить высоту дерева, двигаясь сверху вниз (от корня к листьям), мы столкнемся с проблемой: стоя в корне, мы не знаем, насколько глубоко уходят ветви. Корень вынужден спросить своих детей: «Какая у вас высота?». Дети задают тот же вопрос своим детям, и так до тех пор, пока запрос не достигнет листьев. Листья (или, точнее, пустые ссылки под ними) знают ответ наверняка: их высота равна нулю.

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

Формула вычисления предельно проста: высота текущего узла равна максимуму из высот его детей плюс единица (само ребро, соединяющее узел с ребенком).

def maxDepth(root: TreeNode) -> int:
    # Базовый случай: если узла нет, его высота 0
    if not root:
        return 0

    # Рекурсивный шаг (Post-order)
    left_height = maxDepth(root.left)
    right_height = maxDepth(root.right)

    # Обработка текущего узла
    return max(left_height, right_height) + 1

При таком обходе каждый узел дерева посещается ровно один раз. Следовательно, временная сложность алгоритма составляет $O(N)$ , а пространственная — $O(H)$ из-за стека вызовов, где $H$ — высота дерева.

Что такое сбалансированность?

Знать абсолютную высоту дерева полезно, но для оценки эффективности поиска важнее относительная разница высот его ветвей.

Дерево считается сбалансированным по высоте, если для каждого его узла выполняется условие: разница высот левого и правого поддеревьев не превышает единицы. Математически это записывается так: $|H_{left} - H_{right}| \leq 1$ .

Критически важное слово здесь — каждого. Дерево может выглядеть идеально симметричным у корня (например, левое поддерево имеет высоту 10, и правое имеет высоту 10), но если где-то в глубине правого поддерева скрывается вырожденная ветвь-список, дерево в целом не является сбалансированным.

Наивный подход: ловушка квадратичной сложности

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

def isBalanced_naive(root: TreeNode) -> bool:
    if not root:
        return True

    left_height = maxDepth(root.left)
    right_height = maxDepth(root.right)

    # Проверяем текущий узел
    if abs(left_height - right_height) > 1:
        return False

    # Рекурсивно проверяем детей (Top-down)
    return isBalanced_naive(root.left) and isBalanced_naive(root.right)

Код выглядит логично, но таит в себе серьезную проблему производительности. Функция maxDepth обходит все узлы поддерева. Для корня она обойдет все $N$ узлов. Затем для левого ребенка она снова обойдет все узлы его поддерева (примерно $N/2$ ). Для внука — $N/4$ , и так далее.

Мы многократно вычисляем высоту одних и тех же узлов. В худшем случае (когда дерево вырождено) сложность этого алгоритма деградирует до $O(N^2)$ . Это классический пример того, как алгоритм, корректный математически, проваливает тесты на производительность из-за избыточных вычислений.

Оптимизация: совмещение обхода и проверки

Чтобы достичь сложности $O(N)$ , нам нужно избавиться от повторных обходов. Решение кроется в возвращении к стратегии Post-order.

Если мы вычисляем высоту снизу вверх, мы можем проверять баланс в тот же самый момент. Узел-лист вычисляет свою высоту (1) и сообщает ее родителю. Родитель получает высоты от обоих детей, тут же проверяет их разницу, и если баланс нарушен — немедленно бьет тревогу.

Как технически передать наверх сигнал о нарушении баланса, если наша функция должна возвращать число (высоту)? Мы используем фиктивное значение (sentinel value). Поскольку высота дерева всегда неотрицательна ( $\geq 0$ ), мы можем использовать -1 как сигнал «баланс нарушен».

def isBalanced(root: TreeNode) -> bool:
    def check_height(node: TreeNode) -> int:
        if not node:
            return 0

        left_height = check_height(node.left)
        # Если левое поддерево не сбалансировано, пробрасываем ошибку выше
        if left_height == -1:
            return -1

        right_height = check_height(node.right)
        # Если правое поддерево не сбалансировано, пробрасываем ошибку выше
        if right_height == -1:
            return -1

        # Проверяем баланс текущего узла
        if abs(left_height - right_height) > 1:
            return -1

        # Если всё хорошо, возвращаем реальную высоту
        return max(left_height, right_height) + 1

    # Если результат не -1, значит дерево сбалансировано
    return check_height(root) != -1

В этом коде мы реализовали концепцию «раннего выхода» (early exit). Как только где-то на самом дне дерева обнаруживается перекос, функция возвращает -1. Родительский вызов видит -1 и, не делая лишних вычислений, тоже возвращает -1. Сигнал мгновенно всплывает к корню. Каждый узел посещается ровно один раз, что гарантирует строгую линейную сложность $O(N)$ .

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