В информатике обход дерева ( также известный как поиск по дереву и обход дерева ) представляет собой форму обхода графа и относится к процессу посещения (например, извлечения, обновления или удаления) каждого узла в древовидной структуре данных ровно один раз. Такие обходы классифицируются по порядку посещения узлов. Следующие алгоритмы описаны для двоичного дерева , но их можно обобщить и на другие деревья.
В отличие от связанных списков , одномерных массивов и других линейных структур данных , которые канонически просматриваются в линейном порядке, деревья можно проходить несколькими способами. Их можно проходить в порядке глубины или ширины . Существует три распространенных способа перемещения по ним в порядке глубины: по порядку, в предварительном порядке и после порядка. [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(массив, я, лист) к ← 1 я ← (я - 1)/2 в то время как (лист + 1) % (k * 2) ≠ k я ← (я - 1)/2 к ← 2 * к вернуть япредварительный заказ процедуры (массив) я ← 0 пока я ≠ array.size посетить (массив [я]) если я = размер - 1 я ← размер иначе, если я <размер/2 я ← я * 2 + 1 еще лист ← i - размер/2 родитель ← bubble_up(массив, я, лист) я ← родитель * 2 + 2
Элемент, nodeс которого нужно начать, мог быть найден в двоичном дереве поиска bstс помощью стандартной функции поиска , которая показана здесь в реализации без родительских указателей, т.е. она использует stackдля хранения указателей предков.
поиск процедуры (bst, ключ) // возвращает (узел, стек) узел ← bst.root стек ← пустой стек , а узел ≠ ноль stack.push(узел) if key = node.key возвращает (узел, стек) , if key < node.key узел ← node.left еще узел ← node.right возврат ( ноль , пустой стек )
Функция inorderNext [2] : 60 возвращает соседа по порядку node, либо преемника по порядку (для dir=1), либо предшественника по порядку (для dir=0), а также обновленное stackдерево двоичного поиска. можно последовательно и последовательно обходить и искать в заданном направлении dirдалее.
процедура inorderNext(узел, каталог, стек) новыйузел ← node.child[каталог] если новыйузел ≠ ноль, сделайте узел ← новый узел stack.push(узел) новыйузел ← node.child[1-dir] до тех пор, пока newnode = null return (узел, стек) // узел не имеет дочернего каталога: сделать , если stack.isEmpty() вернет ( ноль , пустой стек ) старый узел ← узел node ← stack.pop() // родительский элемент oldnode пока oldnode ≠ node.child[dir] // теперь oldnode = node.child[1-dir], // т.е. узел = предок (и предшественник/преемник) исходного узла возврат (узел, стек)
Обратите внимание, что функция не использует ключи, а это значит, что последовательная структура полностью записывается рёбрами двоичного дерева поиска. Для обходов без изменения направления ( амортизированная ) средняя сложность определяется тем, что полный обход требует шагов для BST размером 1 шаг для края вверх и 1 для края вниз. Наихудшая сложность связана с высотой дерева.
Все вышеперечисленные реализации требуют стекового пространства, пропорционального высоте дерева, которое является стеком вызовов для рекурсивных и родительским (предковым) стеком для итеративных. В плохо сбалансированном дереве это может быть значительным. С помощью итеративных реализаций мы можем устранить требования к стеку, сохранив родительские указатели в каждом узле или задействовав дерево (следующий раздел).
Бинарное дерево является многопоточным, заставляя каждый указатель левого дочернего узла (который в противном случае был бы нулевым) указывать на предшествующего по порядку узла (если он существует), а каждый указатель правого дочернего узла (который в противном случае был бы нулевым) указывать на входной узел. порядок преемника узла (если он существует).
Преимущества:
Недостатки:
Обход Морриса — это реализация упорядоченного обхода, использующая многопоточность: [9]
Кроме того, ниже приведен псевдокод для простого обхода уровня на основе очереди , для которого потребуется пространство, пропорциональное максимальному количеству узлов на заданной глубине. Это может составлять до половины общего количества узлов. Более экономичный подход для этого типа обхода можно реализовать с помощью итеративного поиска в глубину с углублением .
порядок уровня процедуры (узел) очередь ← пустая очередь очередь.enqueue(узел) пока не очередь.isEmpty() узел ← очередь.dequeue() посетить (узел) если node.left ≠ ноль очередь.enqueue(узел.слева) если node.right ≠ ноль очередь.enqueue(узел.право)
Если дерево представлено массивом (первый индекс равен 0), достаточно перебрать все элементы:
процедура levelorder(array) для i от 0 до array.size посетить (массив [я])
Хотя обход обычно выполняется для деревьев с конечным числом узлов (и, следовательно, с конечной глубиной и конечным коэффициентом ветвления ), его также можно выполнять и для бесконечных деревьев. Это представляет особый интерес в функциональном программировании (особенно с отложенными вычислениями ), поскольку бесконечные структуры данных часто можно легко определить и работать с ними, хотя они не оцениваются (строго) так как это заняло бы бесконечное время. Некоторые конечные деревья слишком велики, чтобы их можно было представить явно, например дерево игры в шахматы или го , поэтому полезно анализировать их, как если бы они были бесконечными.
Основное требование для обхода — в конечном итоге посетить каждый узел. Для бесконечных деревьев простые алгоритмы часто не справляются с этой задачей. Например, для двоичного дерева бесконечной глубины поиск в глубину будет идти вниз по одной стороне (условно левой стороне) дерева, никогда не посещая остальную часть, и действительно, обход по порядку или по порядку никогда не будет посетить любой узел, так как он не достиг листа (и фактически никогда не достигнет). Напротив, обход в ширину (по уровню) без проблем проходит двоичное дерево бесконечной глубины и действительно проходит через любое дерево с ограниченным коэффициентом ветвления.
С другой стороны, если дано дерево глубины 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 соответствует двоичному).
