Обход дерева

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

Типы [ править ]

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

Структуры данных для обхода дерева [ править ]

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

Поиск в глубину легко реализуется через стек, в том числе рекурсивно (через стек вызовов), а поиск в ширину легко реализуется через очередь, в том числе корекурсивно. ^[2]^: 45−61

Поиск в глубину [ править ]

При поиске в глубину (DFS) дерево поиска углубляется настолько, насколько это возможно, прежде чем перейти к следующему одноуровневому элементу.

Чтобы пройти по двоичным деревьям с помощью поиска в глубину, выполните следующие операции на каждом узле: ^[3]^[4]

Если текущий узел пуст, вернитесь.
Выполните следующие три операции в определенном порядке: ^[5]
N: Посетите текущий узел.

L: рекурсивно пройти левое поддерево текущего узла.

R: Рекурсивно пройти по правому поддереву текущего узла.

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

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

F - B - A - A - A - B - D - C - C - C - D - E - E - E - D - B - F - G - G - I - H - H - H - I - I - Г - Ж

Предзаказ, NLR [ править ]

Посетите текущий узел (на рисунке: позиция красного цвета).
Рекурсивно обойти левое поддерево текущего узла.
Рекурсивно обойти правое поддерево текущего узла.

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

Пост-заказ, LRN [ править ]

Рекурсивно обойти левое поддерево текущего узла.
Рекурсивно обойти правое поддерево текущего узла.
Посетите текущий узел (на рисунке: позиция синего цвета).

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

В порядке, ЛНР [ править ]

Рекурсивно обойти левое поддерево текущего узла.
Посетите текущий узел (на рисунке: позиция зеленая).
Рекурсивно обойти правое поддерево текущего узла.

В двоичном дереве поиска, упорядоченном так, что в каждом узле ключ больше, чем все ключи в его левом поддереве и меньше, чем все ключи в его правом поддереве, обход по порядку извлекает ключи в возрастания . порядке ^[7]

Обратный предзаказ, NRL [ править ]

Посетите текущий узел.
Рекурсивно обойти правое поддерево текущего узла.
Рекурсивно обойти левое поддерево текущего узла.

Обратный пост-заказ, RLN [ править ]

Рекурсивно обойти правое поддерево текущего узла.
Рекурсивно обойти левое поддерево текущего узла.
Посетите текущий узел.

Обратный порядок, RNL [ править ]

Рекурсивно обойти правое поддерево текущего узла.
Посетите текущий узел.
Рекурсивно обойти левое поддерево текущего узла.

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

Произвольные деревья [ править ]

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

Если текущий узел пуст, вернитесь.
Посетите текущий узел для обхода предварительного заказа.
Для каждого i от 1 до количества поддеревьев текущего узла - 1 или от последнего до первого для обратного обхода выполните:
1. -е поддерево текущего узла Рекурсивно пройти i .
2. Посетите текущий узел для обхода по порядку.
Рекурсивно обойти последнее поддерево текущего узла.
Посетите текущий узел для обхода пост-заказа.

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

Поиск в ширину [ править ]

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

Другие типы [ править ]

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

Приложения [ править ]

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

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

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

Реализации [ править ]

Реализация поиска в глубину [ править ]

Реализация предзаказа [ править ]

предварительный заказ процедуры  (узел) 
      если  узел =  нулевой 
         возврат 
      посетить (узел) 
      предзаказ (узел.слева) 
      предварительный заказ (узел.справа)

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

Реализация после заказа [ править ]

постзаказ процедуры  (узел) 
      если  узел =  нулевой 
         возврат 
      постзаказ (узел.слева) 
      постзаказ (узел.право) 
      посетить (узел)

итеративная процедураPostorder  (узел) 
      стопка ←  пустая стопка 
      LastNodeVisited ←  null 
     , пока   не  stack.isEmpty()  или  node ≠  null 
         , если  node ≠  null 
              stack.push(узел) 
              узел ← node.left 
          еще 
              peekNode ← stack.peek() 
              // если правый дочерний элемент существует и проходит узел 
              // от левого дочернего элемента, затем перемещаемся вправо 
              если  peekNode.right ≠  null   и  LastNodeVisited ≠ peekNode.right 
                  узел ← peekNode.right 
              еще 
                  посетить (peekNode) 
                  LastNodeVisited ← stack.pop()

Порядковая реализация [ править ]

порядок процедуры  (узел) 
      если  узел =  нулевой 
         возврат 
      порядок (узел.слева) 
      посетить (узел) 
      порядок(узел.справа)

процедура  iterativeInorder(узел) 
      stack ←  пустой стек 
     , пока   не  stack.isEmpty()  или  node ≠  null 
         , если  node ≠  null 
              stack.push(узел) 
              узел ← node.left 
          еще 
              узел ← stack.pop() 
              посетить (узел) 
              узел ← node.right

Еще один вариант предзаказа [ править ]

Если дерево представлено массивом (первый индекс равен 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

Переход к следующему или предыдущему узлу [ править ]

The node с которого нужно начать, возможно, было найдено в дереве двоичного поиска bst с помощью стандартной функции поиска , которая показана здесь в реализации без родительских указателей, т.е. она использует stack для хранения указателей предков.

поиск процедуры  (bst, ключ) 
      // возвращает (узел, стек) 
      узел ← bst.root 
      стек ←  пустой стек 
     , а  узел ≠  ноль 
          stack.push(узел) 
          если  ключ = node.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], 
      // т.е. узел = предок (и предшественник/преемник) исходного узла 
      возврат  (узел, стек)

Обратите внимание, что функция не использует ключи, а это значит, что последовательная структура полностью записывается рёбрами двоичного дерева поиска. Для обходов без изменения направления ( амортизированная ) средняя сложность равна ${\mathcal {O}}(1),$ потому что полный обход занимает $2n-2$ шаги для BST размера $n,$ 1 шаг для края вверх и 1 для края вниз. Наихудшая сложность составляет ${\mathcal {O}}(h)$ с $h$ как высота дерева.

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

Порядковый обход Морриса с использованием многопоточности [ править ]

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

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

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

Недостатки:

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

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

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

Поиск в ширину [ править ]

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

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

Если дерево представлено массивом (первый индекс равен 0), достаточно перебрать все элементы:

порядок уровня процедуры  (массив) 
      для  меня  от  0  до  array.size 
          посетить (массив [я])

Бесконечные деревья [ править ]

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

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

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

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

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

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

()
(1)
(1, 1) (2)
(1, 1, 1) (1, 2) (2, 1) (3)
(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

и т. д.

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

Ссылки [ править ]

^ «Лекция 8. Обход дерева» . Проверено 2 мая 2015 г.
^ Перейти обратно: ^а ^б Пфафф, Бен (2004). Введение в бинарные деревья поиска и сбалансированные деревья . Фонд свободного программного обеспечения, Inc.
^ Методы обхода двоичного дерева
^ «Алгоритм обхода предзаказа» . Проверено 2 мая 2015 г.
^ L перед R означает (стандартное) движение против часовой стрелки, как показано на рисунке.
Выполнение N до, между или после L и R определяет один из описанных методов.
Если обход осуществляется в обратную сторону (по часовой стрелке), то обход называется обратным. Это описано, в частности, для обратного порядка , когда данные должны быть получены в порядке убывания.
^ «Алгоритмы. Какие комбинации предварительной, пост- и упорядоченной секвенализации уникальны? , Обмен компьютерными науками» . Проверено 2 мая 2015 г.
^ Уиттман, Тодд. «Обход дерева» (PDF) . Калифорнийский университет в Лос-Анджелесе, математика . Архивировано из оригинала (PDF) 13 февраля 2015 года . Проверено 2 января 2016 г.
^ «деревовидные структуры constexpr» . Блог Фекира . 9 августа 2021 г. Проверено 15 августа 2021 г.
^ Моррис, Джозеф М. (1979). «Обход бинарных деревьев просто и дешево». Письма об обработке информации . 9 (5): 197–200. дои : 10.1016/0020-0190(79)90068-1 .

Источники [ править ]

Дейл, Нелл. Лилли, Сьюзен Д. «Структуры данных Pascal Plus». Округ Колумбия Хит и компания. Лексингтон, Массачусетс. 1995. Четвертое издание.
Дроздек, Адам. «Структуры данных и алгоритмы в C++». Брук/Коул. Пасифик Гроув, Калифорния. 2001. Второе издание.
«Трансверсаль дерева» (math.northwestern.edu)

Внешние ссылки [ править ]

[holtenotes-1] «Лекция 8. Обход дерева» . Проверено 2 мая 2015 г.

[Pfaff-2] Перейти обратно: ^а ^б Пфафф, Бен (2004). Введение в бинарные деревья поиска и сбалансированные деревья . Фонд свободного программного обеспечения, Inc.

[3] Методы обхода двоичного дерева

[4] «Алгоритм обхода предзаказа» . Проверено 2 мая 2015 г.

[5] L перед R означает (стандартное) движение против часовой стрелки, как показано на рисунке.
Выполнение N до, между или после L и R определяет один из описанных методов.
Если обход осуществляется в обратную сторону (по часовой стрелке), то обход называется обратным. Это описано, в частности, для обратного порядка , когда данные должны быть получены в порядке убывания.

[6] «Алгоритмы. Какие комбинации предварительной, пост- и упорядоченной секвенализации уникальны? , Обмен компьютерными науками» . Проверено 2 мая 2015 г.

[7] Уиттман, Тодд. «Обход дерева» (PDF) . Калифорнийский университет в Лос-Анджелесе, математика . Архивировано из оригинала (PDF) 13 февраля 2015 года . Проверено 2 января 2016 г.

[8] «деревовидные структуры constexpr» . Блог Фекира . 9 августа 2021 г. Проверено 15 августа 2021 г.

[9] Моррис, Джозеф М. (1979). «Обход бинарных деревьев просто и дешево». Письма об обработке информации . 9 (5): 197–200. дои : 10.1016/0020-0190(79)90068-1 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v т Это графов и деревьев Алгоритмы обхода
Поиск	α–β обрезка А* ИДА* МПА* СМА* Поиск по принципу «лучшее в первую очередь» Поиск луча Двунаправленный поиск Поиск в ширину Лексикографический Параллельно Б* Поиск в глубину Итеративное углубление Д* Граничный поиск Поиск точки прыжка Поиск по дереву Монте-Карло ССС*
Кратчайший путь	Беллман-Форд Дейкстры Флойд-Уоршалл Джонсонс Кратчайший путь быстрее Йен
Минимальное связующее дерево	Черника Крускала Prim's Обратное удаление
Список алгоритмов поиска по графу