Инфиксный обход

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

Алгоритм и принцип работы

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

Рекурсивная реализация

Псевдокод на языке, подобном Python:

`` def inorder(node): if node is None: return inorder(node.left) print(node.value) inorder(node.right) ``

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

Итеративная реализация

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

1. Инициализировать пустой стек.
2. Установить текущий узел curr в корень дерева.
3. Пока curr не равен None или стек не пуст:

• Пока curr не равен None: поместить curr в стек, перейти к curr.left.
• Извлечь узел из стека (это будет curr).
• Обработать curr (вывести значение).
• Перейти к curr.right.

1. Повторять, пока не будут обработаны все узлы.

Этот метод позволяет избежать рекурсии и работает за O(n) времени, используя O(h) дополнительной памяти, где h — высота дерева.

Свойства инфиксного обхода

• Для бинарного дерева поиска (BST): инфиксный обход выводит узлы в строго возрастающем порядке значений ключей. Это свойство используется для проверки корректности BST, а также для получения отсортированной последовательности элементов из дерева.
• Для произвольного бинарного дерева: порядок вывода не имеет специального смысла, но сохраняет структуру обхода «лево-корень-право».
• Сложность: время выполнения O(n), где n — количество узлов. Память O(h) при итеративной реализации (h — высота дерева) или O(n) в худшем случае при рекурсии (глубоко несбалансированное дерево).

Применение

Инфиксный обход используется в следующих задачах:

• Сортировка данных: если элементы хранятся в BST, то инфиксный обход позволяет получить отсортированный список за линейное время.
• Проверка корректности BST: сравнивая значения узлов при обходе с предыдущим, можно убедиться, что дерево является BST (все значения идут по возрастанию).
• Построение математических выражений: в абстрактных синтаксических деревьях (AST) инфиксный обход соответствует записи выражения в привычной инфиксной нотации (например, (a + b) * c). При этом требуется учитывать приоритет операций и расставлять скобки.
• Обход бинарных деревьев в алгоритмах: например, при восстановлении дерева по двум другим обходам (префиксному и инфиксному) или при кодировании/декодировании (алгоритм Хаффмана).
• Вывод дерева в виде строки: для отладки или визуализации.

Пример

Рассмотрим бинарное дерево поиска:

`` 5 / \ 3 7 / \ \ 2 4 8 ``

Инфиксный обход (LNR) даст последовательность: 2, 3, 4, 5, 7, 8. Как видно, значения идут по возрастанию.

Для сравнения:

• Префиксный обход (NLR): 5, 3, 2, 4, 7, 8.
• Постфиксный обход (LRN): 2, 4, 3, 8, 7, 5.

Варианты и обобщения

• Обратный инфиксный обход (RNL): сначала правое поддерево, затем узел, затем левое. Для BST даёт убывающий порядок значений.
• Для n-арных деревьев: инфиксный обход не определён однозначно, так как узел может иметь более двух потомков. Обычно для таких деревьев применяют префиксный или постфиксный обход.
• Моррисов обход (Morris traversal): вариант инфиксного обхода, который использует временное изменение структуры дерева (threaded binary tree) для достижения O(1) дополнительной памяти (без стека). Алгоритм работает за O(n) времени, но требует модификации дерева.

Критика и ограничения

• Рекурсивная реализация может вызвать переполнение стека при глубине дерева более нескольких тысяч узлов (зависит от языка и настроек стека). Итеративная версия решает эту проблему, но требует больше кода.
• Для больших деревьев итеративная реализация со стеком может потреблять O(h) памяти, что в худшем случае (вырожденное дерево, похожее на список) даёт O(n) — то есть не лучше рекурсии.
• Моррисов обход экономит память, но изменяет дерево (временно или постоянно), что может быть неприемлемо для неизменяемых структур данных.

Источники

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание, 2009.
• Дональд Э. Кнут. «Искусство программирования», том 1: «Основные алгоритмы», 3-е издание, 1997.
• Robert Sedgewick, Kevin Wayne. «Algorithms», 4th edition, 2011.
• Материалы курса «Структуры данных и алгоритмы» (Computer Science, различные университеты), лекции по обходу деревьев.