В информатике обход дерева (также известный как поиск по дереву и обход дерева ) является формой обхода графа и относится к процессу посещения (например, извлечения, обновления или удаления) каждого узла в структуре данных дерева ровно один раз. Такие обходы классифицируются по порядку посещения узлов. Следующие алгоритмы описаны для бинарного дерева , но их можно обобщить и для других деревьев.
В отличие от связанных списков , одномерных массивов и других линейных структур данных , которые канонически обходят в линейном порядке, деревья можно обходить несколькими способами. Их можно обходить в глубину или в ширину . Существует три распространенных способа обхода их в глубину: в порядке, в прямом и в обратном порядке. [1] Помимо этих основных обходов, возможны различные более сложные или гибридные схемы, такие как поиск с ограниченной глубиной , такой как итеративный поиск в глубину . Последний, а также поиск в ширину, также можно использовать для обхода бесконечных деревьев, см. ниже.
Обход дерева подразумевает итерацию по всем узлам некоторым образом. Поскольку из данного узла существует более одного возможного следующего узла (это не линейная структура данных), то, предполагая последовательное вычисление (не параллельное), некоторые узлы должны быть отложены — сохранены каким-то образом для последующего посещения. Это часто делается с помощью стека (LIFO) или очереди (FIFO). Поскольку дерево является самореферентной (рекурсивно определенной) структурой данных, обход может быть определен рекурсией или, более тонко, корекурсией , естественным и понятным образом; в этих случаях отложенные узлы неявно хранятся в стеке вызовов .
Поиск в глубину легко реализуется через стек, в том числе рекурсивно (через стек вызовов), тогда как поиск в ширину легко реализуется через очередь, в том числе и корекурсивно. [2] : 45−61
При поиске в глубину (DFS) дерево поиска углубляется настолько, насколько это возможно, прежде чем перейти к следующему элементу.
Для обхода бинарных деревьев с поиском в глубину выполните следующие операции в каждом узле: [3] [4]
След обхода называется секвенцией дерева. Трассировка обхода представляет собой список каждого посещённого узла. Ни одна секвенция в соответствии с предварительным, ин- или постпорядком не описывает базовое дерево однозначно. Если дерево содержит различные элементы, то для однозначного описания дерева достаточно либо предварительный порядок, либо постпорядок в паре с ин-порядком. Однако предварительный порядок с постпорядком оставляет некоторую двусмысленность в структуре дерева. [6]
Существует три метода, при которых положение обхода относительно узла (на рисунке: красный, зеленый или синий) должно иметь место посещение узла. Выбор ровно одного цвета определяет ровно одно посещение узла, как описано ниже. Посещение всех трех цветов приводит к трехкратному посещению одного и того же узла, что дает последовательность «всех порядков»:
Предварительный обход является топологически отсортированным , поскольку родительский узел обрабатывается до того, как будет обработан любой из его дочерних узлов.
Постфиксный обход может быть полезен для получения постфиксного выражения бинарного дерева выражений .
В бинарном дереве поиска, упорядоченном таким образом, что в каждом узле ключ больше, чем все ключи в его левом поддереве и меньше, чем все ключи в его правом поддереве, упорядоченный обход извлекает ключи в порядке возрастания сортировки. [7]
В бинарном дереве поиска, упорядоченном таким образом, что в каждом узле ключ больше, чем все ключи в его левом поддереве и меньше, чем все ключи в его правом поддереве, обратный обход в обратном порядке извлекает ключи в порядке убывания, отсортированные.
Для обхода произвольных деревьев (не обязательно бинарных) с поиском в глубину выполните следующие операции в каждом узле:
В зависимости от решаемой задачи предварительный порядок, обратный порядок и особенно одна из операций порядка поддеревьев − 1 могут быть необязательными. Кроме того, на практике может потребоваться более одной операции предварительного порядка, обратного порядка и обратного порядка. Например, при вставке в троичное дерево предварительная операция выполняется путем сравнения элементов. После этого может потребоваться обратная операция для повторной балансировки дерева.
При поиске в ширину (BFS) или поиске по уровням дерево поиска максимально расширяется перед переходом на следующую глубину.
Существуют также алгоритмы обхода дерева, которые не классифицируются ни как поиск в глубину, ни как поиск в ширину. Одним из таких алгоритмов является поиск по дереву Монте-Карло , который концентрируется на анализе наиболее перспективных ходов, основывая расширение дерева поиска на случайной выборке пространства поиска.
Обход в прямом порядке может использоваться для создания префиксного выражения ( польская запись ) из деревьев выражений : обход дерева выражений в прямом порядке. Например, обход изображенного арифметического выражения в прямом порядке дает "+ * A − B C + D E ". В префиксной записи нет необходимости в скобках, если каждый оператор имеет фиксированное количество операндов. Обход в прямом порядке также используется для создания копии дерева.
Пост-порядковый обход может генерировать постфиксное представление ( обратная польская запись ) двоичного дерева. Обход изображенного арифметического выражения в пост-порядке дает " A B C − * D E + +"; последний может быть легко преобразован в машинный код для вычисления выражения стековой машиной . Пост-порядковый обход также используется для удаления дерева. Каждый узел освобождается после освобождения его потомков.
Упорядоченный обход очень часто используется в двоичных деревьях поиска , поскольку он возвращает значения из базового набора в порядке, соответствующем компаратору, который настроил двоичное дерево поиска.
Если дерево представлено массивом (первый индекс равен 0), то можно вычислить индекс следующего элемента: [8] [ необходимо пояснение ]
процедура bubbleUp(массив, i, лист) к ← 1 я ← (я - 1)/2 пока (лист + 1) % (k * 2) ≠ k я ← (я - 1)/2 к ← 2 * к вернуть япроцедура preorder(массив) я ← 0 пока я ≠ array.size визит(массив[i]) если i = размер - 1 я ← размер иначе если я < размер/2 я ← я * 2 + 1 еще лист ← i - размер/2 родитель ← bubble_up(массив, i, лист) я ← родитель * 2 + 2
Элемент node, с которого следует начать, может быть найден в двоичном дереве поиска bstс помощью стандартной функции поиска , которая показана здесь в реализации без родительских указателей, т.е. она использует stackдля хранения указателей предков.
процедура поиска(bst, key) // возвращает (узел, стек) узел ← bst.root стек ← пустой стек , пока узел ≠ null стек.push(узел) если ключ = узел.ключ вернуть (узел, стек) если ключ < узел.ключ узел ← узел.левый еще узел ← узел.правый возврат ( ноль , пустой стек )
Функция inorderNext [2] : 60 возвращает соседа по порядку для node, либо последователя по порядку ( для dir=1), либо предшественника по порядку (для dir=0), и обновленный stack, так что бинарное дерево поиска может быть последовательно пройдено по порядку и выполнен поиск в заданном направлении dirдалее.
процедура inorderNext(узел, каталог, стек) newnode ← node.child[dir] если newnode ≠ null сделать узел ← новыйузел стек.push(узел) newnode ← узел.child[1-dir] пока newnode = null не вернет (узел, стек) // узел не имеет дочернего каталога: do if stack.isEmpty() возвращает ( null , пустой стек ) старыйузел ← узел узел ← stack.pop() // родительский узел oldnode пока oldnode ≠ node.child[dir] // теперь oldnode = node.child[1-dir], // т.е. узел = предок (и предшественник/последователь) исходного узла возврат (узел, стек)
Обратите внимание, что функция не использует ключи, что означает, что последовательная структура полностью записана ребрами бинарного дерева поиска. Для обходов без изменения направления ( амортизированная ) средняя сложность такова , что полный обход занимает шагов для BST размером 1 шаг для ребра вверх и 1 для ребра вниз. Худшая сложность равна высоте дерева.
Все вышеперечисленные реализации требуют стекового пространства, пропорционального высоте дерева, которое является стеком вызовов для рекурсивных и родительским (предковым) стеком для итеративных. В плохо сбалансированном дереве это может быть значительным. С итеративными реализациями мы можем устранить требование стека, сохраняя родительские указатели в каждом узле или разбивая дерево на потоки (следующий раздел).
Бинарное дерево разветвляется путем указания каждого левого дочернего указателя (который в противном случае был бы нулевым) на предшествующий узел (если он существует), а каждого правого дочернего указателя (который в противном случае был бы нулевым) на предшествующий узел (если он существует).
Преимущества:
Недостатки:
Обход Морриса — это реализация упорядоченного обхода, использующая потоки: [9]
Также ниже приведен псевдокод для простого обхода по уровням на основе очереди , который потребует пространства, пропорционального максимальному количеству узлов на заданной глубине. Это может быть до половины от общего количества узлов. Более эффективный с точки зрения пространства подход для этого типа обхода может быть реализован с использованием итеративного углубляющегося поиска в глубину .
процедура levelorder(узел) очередь ← пустая очередь очередь.enqueue(узел) пока не queue.isEmpty() узел ← очередь.dequeue() визит(узел) если узел.left ≠ null очередь.enqueue(узел.left) если узел.право ≠ нуль очередь.enqueue(узел.right)
Если дерево представлено массивом (первый индекс равен 0), достаточно выполнить итерацию по всем элементам:
процедура levelorder(array) для i от 0 до array.size визит(массив[i])
Хотя обход обычно выполняется для деревьев с конечным числом узлов (и, следовательно, конечной глубиной и конечным фактором ветвления ), его также можно выполнять для бесконечных деревьев. Это представляет особый интерес в функциональном программировании (особенно с ленивым вычислением ), поскольку бесконечные структуры данных часто можно легко определить и с ними работать, хотя они (строго) не оцениваются, так как это заняло бы бесконечное время. Некоторые конечные деревья слишком велики для явного представления, например, игровое дерево для шахмат или го , и поэтому полезно анализировать их так, как если бы они были бесконечными.
Базовое требование для обхода — в конечном итоге посетить каждый узел. Для бесконечных деревьев простые алгоритмы часто не справляются с этим. Например, если у вас есть бинарное дерево бесконечной глубины, то поиск в глубину будет проходить по одной стороне (по соглашению, по левой стороне) дерева, никогда не посещая остальные, и, действительно, обход в порядке или обратном порядке никогда не посетит ни один узел, поскольку он не достиг листа (и фактически никогда не достигнет). Напротив, обход в ширину (по уровню) без проблем обойдет бинарное дерево бесконечной глубины и, действительно, обойдет любое дерево с ограниченным фактором ветвления.
С другой стороны, если задано дерево глубины 2, где корень имеет бесконечно много потомков, и каждый из этих потомков имеет двух потомков, поиск в глубину посетит все узлы, так как как только он исчерпает внуков (потомков потомков одного узла), он перейдет к следующему (предполагая, что это не обратный порядок, в этом случае он никогда не достигнет корня). Напротив, поиск в ширину никогда не достигнет внуков, так как он стремится сначала исчерпать потомков.
Более сложный анализ времени выполнения можно дать с помощью бесконечных порядковых чисел ; например, поиск в ширину дерева глубиной 2, представленного выше, займет ω ·2 шагов: ω для первого уровня, а затем еще ω для второго уровня.
Таким образом, простые поиски в глубину или в ширину не обходят каждое бесконечное дерево и неэффективны на очень больших деревьях. Однако гибридные методы могут обходить любое (счетно) бесконечное дерево, по сути, через диагональный аргумент («диагональ» — комбинация вертикали и горизонтали — соответствует комбинации глубины и ширины).
Конкретно, учитывая бесконечно разветвленное дерево бесконечной глубины, обозначим корень (), потомков корня (1), (2), ..., внуков (1, 1), (1, 2), ..., (2, 1), (2, 2), ... и т. д. Узлы, таким образом, находятся во взаимно однозначном соответствии с конечными (возможно, пустыми) последовательностями положительных чисел, которые являются счетными и могут быть размещены в порядке сначала по сумме записей, а затем по лексикографическому порядку в пределах данной суммы (только конечное число последовательностей в сумме дает заданное значение, поэтому все записи достигаются — формально существует конечное число композиций данного натурального числа, а именно 2 n −1 композиций n ≥ 1 ), что дает обход. Явно:
и т. д.
Это можно интерпретировать как отображение бесконечного двоичного дерева глубины на это дерево и затем применение поиска в ширину: заменить «нисходящие» ребра, соединяющие родительский узел с его вторым и последующими дочерними узлами, на «правые» ребра от первого дочернего узла ко второму дочернему узлу, от второго дочернего узла к третьему дочернему узлу и т. д. Таким образом, на каждом шаге можно либо спуститься вниз (добавить (, 1) в конец), либо спуститься вправо (добавить единицу к последнему числу) (за исключением корня, который является дополнительным и может идти только вниз), что показывает соответствие между бесконечным двоичным деревом и приведенной выше нумерацией; сумма записей (минус один) соответствует расстоянию от корня, что согласуется с 2 n −1 узлами на глубине n − 1 в бесконечном двоичном дереве (2 соответствует двоичному).
