Обход дерева - Tree traversal

«Поиск по дереву» перенаправляется сюда. Не следует путать с Дерево поиска.
График и дерево
алгоритмы поиска
Списки
похожие темы

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

Типы

В отличие от связанные списки, одномерный массивы и другие линейные структуры данных, проход по которым канонически выполняется в линейном порядке, деревья можно обходить разными способами. Их можно пройти в в глубину или же в ширину порядок. Есть три распространенных способа просмотреть их в порядке глубины: по порядку, по предварительному заказу и после.[1] Помимо этих основных обходов возможны различные более сложные или гибридные схемы, такие как поиск с ограниченной глубиной подобно итеративный поиск в глубину с углублением. Последний, а также поиск в ширину также можно использовать для обхода бесконечных деревьев, см. ниже.

Структуры данных для обхода дерева

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

Поиск в глубину легко реализуется через стек, в том числе рекурсивно (через стек вызовов), в то время как поиск в ширину легко реализуется через очередь, в том числе corecursively.

Обход примерного дерева в глубину:
предварительный заказ (красный): F, B, A, D, C, E, G, I, H;
в порядке (желтый): A, B, C, D, E, F, G, H, I;
почтовый заказ (зеленый): A, C, E, D, B, H, I, G, F.

Поиск в глубину двоичного дерева

Эти поиски называются поиск в глубину (DFS), поскольку дерево поиска максимально углубляется для каждого дочернего элемента перед переходом к следующему брату. Для двоичного дерева они определяются как операции доступа к каждому узлу, начиная с текущего узла, алгоритм которых следующий:[2][3]

Общий рекурсивный паттерн для обхода двоичного дерева таков:

Спуститесь на один уровень к рекурсивному аргументу N. Если N существует (не пусто) выполняет следующие три операции в определенном порядке:
(L)Рекурсивный ход Nлевое поддерево.
(Р)Рекурсивный ход NПравое поддерево.
(N)Обработать текущий узел N сам.
Вернитесь, поднявшись на один уровень и достигнув родительского узла N.

В примерах (L) в основном выполняется до (R). Но (R) перед (L) также возможно, см. (RNL).

Предзаказ (NLR)

  1. Получите доступ к части данных текущего узла.
  2. Обойдите левое поддерево, рекурсивно вызывая функцию предварительного заказа.
  3. Пройдите по правому поддереву, рекурсивно вызывая функцию предварительного заказа.
Обход предварительного заказа - это топологически отсортированный один, потому что родительский узел обрабатывается до того, как будет обработан любой из его дочерних узлов.

В порядке (LNR)

  1. Обойдите левое поддерево, рекурсивно вызывая функцию упорядочения.
  2. Получите доступ к части данных текущего узла.
  3. Пройдите по правому поддереву, рекурсивно вызывая функцию упорядочения.
В двоичное дерево поиска упорядоченный таким образом, что в каждом узле ключ больше, чем все ключи в его левом поддереве и меньше, чем все ключи в его правом поддереве, обход по порядку извлекает ключи в Восходящий отсортированный порядок.[4]

Реверс по порядку (RNL)

  1. Пройдите по правому поддереву, рекурсивно вызывая функцию обратного порядка.
  2. Получите доступ к части данных текущего узла.
  3. Обойдите левое поддерево, рекурсивно вызывая функцию обратного порядка.
В двоичное дерево поиска, обратный обход по порядку извлекает ключи в нисходящий отсортированный порядок.

Пост-заказ (LRN)

  1. Пройдите по левому поддереву, рекурсивно вызывая функцию пост-заказа.
  2. Пройдите по правому поддереву, рекурсивно вызывая функцию пост-заказа.
  3. Получите доступ к части данных текущего узла.

След обхода называется секвенированием дерева. Трассировка обхода - это список каждого посещенного корня. Ни одна секвенирование в соответствии с предварительным, обратным или последующим порядком не описывает однозначно лежащее в основе дерево. Для дерева с различными элементами достаточно либо предварительного, либо последующего порядка в паре с упорядочением, чтобы однозначно описать дерево. Однако предварительный заказ с пост-заказом оставляет некоторую неоднозначность в древовидной структуре.[5]

Общее дерево

Чтобы пройти любое дерево с поиском в глубину, рекурсивно выполните следующие операции на каждом узле:

  1. Выполните операцию предварительного заказа.
  2. Для каждого я от 1 до количества детей делают:
    1. Посещение я-th, если есть.
    2. Выполните операцию по порядку.
  3. Выполните операцию пост-заказа.

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

Поиск в ширину / порядок уровней

Порядок уровней: F, B, G, A, D, I, C, E, H.
Основная статья: Поиск в ширину

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

Другие типы

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

Приложения

Дерево, представляющее арифметическое выражение А * (B − C) + (D + E)

Обход предварительного заказа может использоваться для создания префиксного выражения (Польская нотация ) из деревья выражения: предварительно пройти дерево выражений. Например, переход по изображенному арифметическому выражению в предварительном порядке дает "+ * А − B C + D E".

Обход пост-заказа может генерировать постфиксное представление (Обратная польская запись ) двоичного дерева. Переход по изображенному арифметическому выражению в выходных данных после заказа "А B C − * D E + + "; последнее легко трансформируется в Машинный код оценить выражение с помощью штабелеукладчик.

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

Пост-заказ обход при удалении или освобождении узлов и значений может удалить или освободить все двоичное дерево. Таким образом, узел освобождается после освобождения своих дочерних узлов.

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

Реализации

Поиск в глубину

Предварительный заказ

Предварительный заказ(узел) если (узел == ноль)        возвращаться    посещение (узел) предварительный заказ (node.left) предварительный заказ (node.right)
iterativePreorder(узел) если (узел == ноль)    возвращаться  s ← пустой стек  s.push (узел) пока (нет s.isEmpty ()) node ← s.pop () visit (node) // правый дочерний элемент помещается первым, так что сначала обрабатывается левый если node.right ≠ ноль      s.push (node.right) если node.left ≠ ноль      s.push (node.left)

Чтобы

чтобы(узел) если (узел == ноль)        возвращаться    inorder (node.left) посещение (node) inorder (node.right)
iterativeInorder(узел) s ← пустой стек  пока (нет s.isEmpty () или же узел ≠ ноль)    если (узел ≠ ноль) s.push (узел) узел ← node.left еще      узел ← s.pop () посещение (узел) узел ← node.right

Пост-заказ

почтовый заказ(узел) если (узел == ноль)        возвращаться    postorder (node.left) postorder (node.right) визит (node)
iterativePostorder(узел) s ← пустой стек  lastNodeVisited ← ноль  пока (нет s.isEmpty () или же узел ≠ ноль)    если (узел ≠ ноль) s.push (узел) узел ← node.left еще      peekNode ← s.peek () // если правый дочерний элемент существует и пересекает узел // от левого дочернего элемента, то двигаться вправо если (peekNode.right ≠ ноль и lastNodeVisited ≠ peekNode.right) узел ← peekNode.right еще        visit (peekNode) lastNodeVisited ← s.pop ()

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

Обход Морриса по порядку с использованием потоков

Основная статья: Многопоточное двоичное дерево

Бинарное дерево распределяется по потокам, заставляя каждый левый дочерний указатель (который в противном случае был бы нулевым) указывать на упорядоченного предшественника узла (если он существует), а каждый правый дочерний указатель (который в противном случае был бы нулевым) указывал на входящий порядок преемника узла (если он существует).

Преимущества:

  1. Избегает рекурсии, которая использует стек вызовов и потребляет память и время.
  2. Узел ведет учет своего родителя.

Недостатки:

  1. Дерево более сложное.
  2. Мы можем делать только один обход за раз.
  3. Он более подвержен ошибкам, когда оба дочерних элемента отсутствуют, и оба значения узлов указывают на их предков.

Обход Морриса - это реализация обхода по порядку, использующая многопоточность:[6]

  1. Создайте ссылки на преемника в порядке.
  2. Распечатайте данные, используя эти ссылки.
  3. Отменить изменения, чтобы восстановить исходное дерево.

Поиск в ширину

Кроме того, ниже указан псевдокод для простого очередь основанный на обходе порядка уровней и потребует пространства, пропорционального максимальному количеству узлов на заданной глубине. Это может быть столько, сколько общее количество узлов / 2. Более экономичный подход для этого типа обхода может быть реализован с использованием итеративный поиск в глубину с углублением.

уровень(корень) q ← пустая очередь    q.enqueue (корень) пока нет q.isEmpty () делать        узел ← q.dequeue () посещение (узел) если node.left ≠ ноль тогда            q.enqueue (node.left) если node.right ≠ ноль тогда            q.enqueue (node.right)

Бесконечные деревья

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

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

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

Более сложный анализ времени работы может быть дан с помощью бесконечного порядковые номера; например, поиск в ширину дерева глубины 2 выше займет ω · 2 шага: ω для первого уровня, а затем еще ω для второго уровня.

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

Конкретно, учитывая бесконечно ветвящееся дерево бесконечной глубины, пометьте корень (), потомков корня (1), (2),…, внуков (1, 1), (1, 2),…, (2 , 1), (2, 2),… ​​и так далее. Таким образом, узлы находятся в один к одному соответствие с конечными (возможно, пустыми) последовательностями положительных чисел, которые счетны и могут быть упорядочены сначала по сумме записей, а затем по лексикографический порядок в пределах заданной суммы (только конечное число последовательностей суммируется с заданным значением, поэтому все элементы достигаются - формально существует конечное число композиции заданного натурального числа, а именно 2п−1 композиции из п ≥ 1), что дает обход. Ясно:

0: ()1: (1)2: (1, 1) (2)3: (1, 1, 1) (1, 2) (2, 1) (3)4: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

и Т. Д.

Это можно интерпретировать как отображение двоичного дерева бесконечной глубины на это дерево с последующим применением поиска в ширину: замена «нижних» ребер, соединяющих родительский узел со вторым и последующими дочерними узлами, на «правые» ребра от первого дочернего узла ко второму. дочерний элемент, от второго дочернего элемента к третьему дочернему элементу и т. д. Таким образом, на каждом шаге можно либо спуститься (добавить (, 1) в конец), либо пойти вправо (добавить единицу к последнему числу) (за исключением корня, который является дополнительным и может идти только вниз), который показывает соответствие между бесконечным двоичным деревом и приведенной выше нумерацией; сумма записей (минус один) соответствует расстоянию от корня, что согласуется с 2п−1 узлы на глубине п − 1 в бесконечном двоичном дереве (2 соответствует двоичному).

Рекомендации

  1. ^ «Лекция 8, обход дерева». Получено 2 мая 2015.
  2. ^ [1]
  3. ^ «Алгоритм обхода предзаказа». Получено 2 мая 2015.
  4. ^ Виттман, Тодд. "Обход дерева" (PDF). UCLA Математика. Архивировано из оригинал (PDF) 13 февраля 2015 г.. Получено 2 января, 2016.
  5. ^ «Алгоритмы, какие комбинации пре-, пост- и упорядоченной секвенирования уникальны ?, Computer Science Stack Exchange». Получено 2 мая 2015.
  6. ^ Моррис, Джозеф М. (1979). «Простой и дешевый обход бинарных деревьев». Письма об обработке информации. 9 (5). Дои:10.1016/0020-0190(79)90068-1.
Общий
  • Дейл, Нелл. Лилли, Сьюзен Д. «Структуры данных Pascal Plus». Д. К. Хит и компания. Лексингтон, Массачусетс. 1995. Издание четвертое.
  • Дроздек, Адам. «Структуры данных и алгоритмы в C ++». Брук / Коул. Пасифик Гроув, Калифорния. 2001. Издание второе.
  • [2]

внешняя ссылка