Обход дерева

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

Типы

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

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

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

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

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

Основная статья: Поиск в глубину

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

Основной рекурсивный подход для обхода (непустого) бинарного дерева: Начиная с узла N делаем следующее:

(L) Рекурсивно обходим левое поддерево. Этот шаг завершается при попадании опять в узел N.

(R) Рекурсивно обходим правое поддерево. Этот шаг завершается при попадании опять в узел N.

(N) Обрабатываем сам узел N.

Эти шаги могут быть проделаны в любом порядке. Если (L) осуществляется перед (R), процесс называется обходом слева направо, в противном случае — обходом справа налево. Следующие методы показывают обходы слева направо:

Прямой обход (NLR)

Прямой обход: F, B, A, D, C, E, G, I, H.
  1. Проверяем, не является ли текущий узел пустым или null.
  2. Показываем поле данных корня (или текущего узла).
  3. Обходим левое поддерево рекурсивно, вызвав функцию прямого обхода.
  4. Обходим правое поддерево рекурсивно, вызвав функцию прямого обхода.

Центрированный обход (LNR)

Центрированный обход: A, B, C, D, E, F, G, H, I.
  1. Проверяем, не является ли текущий узел пустым или null.
  2. Обходим левое поддерево рекурсивно, вызвав функцию центрированного обхода.
  3. Показываем поле данных корня (или текущего узла).
  4. Обходим правое поддерево рекурсивно, вызвав функцию центрированного обхода.


В двоичном дереве поиска центрированный обход извлекает данные в отсортированном порядке.[4].

Обратный обход (LRN)

Обратный порядок: A, C, E, D, B, H, I, G, F.
  1. Проверяем, не является ли текущий узел пустым или null.
  2. Обходим левое поддерево рекурсивно, вызвав функцию обратного обхода.
  3. Обходим правое поддерево рекурсивно, вызвав функцию обратного обхода.
  4. Показываем поле данных корня (или текущего узла).

Последовательность обхода называется секвенциализацией дерева. Последовательность обхода — это список всех посещённых узлов. Ни одна из секвенциализаций согласно прямому, обратному или центрированному порядку не описывает дерево однозначно. Если задано дерево с различными элементами, прямой или обратный обход вместе с центрированным обходом достаточны для описания дерева однозначно. Однако прямой обход вместе с обратным оставляет некоторую неоднозначность в структуре дерева[5].

Дерево общего вида

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

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

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

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

Уровневый порядок: F, B, G, A, D, I, C, E, H.

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

Другие виды

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

Приложения

Прямой обход при дублировании узлов и рёбер может сделать полный дубликат двоичного дерева. Это можно использовать для создания префиксного выражения (польской нотации) из деревья выражений[англ.], для чего обходим выражение в прямом порядке.

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

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

Реализация

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

Прямой обход

preorder(node)
  if (node = null)
    return
  visit(node)
  preorder(node.left)
  preorder(node.right)

iterativePreorder(node)
  if (node = null)
    return
  s ← empty stack
  s.push(node)
  while (not s.isEmpty())
    node ← s.pop()
    visit(node)
    //правый потомок заносится первым, так что левый потомок обрабатывается первым
    if (node.right ≠ null)
      s.push(node.right)
    if (node.left ≠ null)
      s.push(node.left)

Центрированный обход

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

Обратный обход

postorder(node)
  if (node = null)
    return
  postorder(node.left)
  postorder(node.right)
  visit(node)

iterativePostorder(node)
  s ← empty stack
  lastNodeVisited ← null
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      peekNode ← s.peek()
      // если правый потомок существует и обход пришёл из левого потомка, двигаемся вправо
      if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
        node ← peekNode.right
      else
        visit(peekNode)
        lastNodeVisited ← s.pop()

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

Центрированный обход Морриса с помощью прошивки

Основная статья: Прошитое двоичное дерево

Двоичное дерево прошивается путём присвоения каждому левому указателю потомка (который в противном случае всегда пуст = null) указателя на предшественника узла в центрированном порядке (если таковой существует), а каждому правому указателю потомка (который в противном случае всегда пуст) указателя на следующий узел в центрированном порядке (если таковой существует).

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

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

Недостатки:

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

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

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

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

Основная статья: Поиск в ширину

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

levelorder(root)
  q ← empty queue
  q.enqueue(root)
  while (not q.isEmpty())
    node ← q.dequeue()
    visit(node)
    if (node.left ≠ null)
      q.enqueue(node.left)
    if (node.right ≠ null)
      q.enqueue(node.right)

    void wide(TreeNode* root){
        std::queue<TreeNode*> q;
        q.push(root);
        TreeNode* node;
        while (!q.empty()){
            node = q.front();
            q.pop();
            visit(node);
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
    }

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

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

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

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

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

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

Конкретно, если дано бесконечно ветвящееся дерево бесконечной глубины, помечаем корень (), детей корня (1), (2), …, внуков (1, 1), (1, 2), …, (2, 1), (2, 2), …, и так далее. Узлы тогда находятся в один-к-одному соответствии с конечными (возможно пустыми) последовательностями положительных чисел, множество которых счётно и может быть упорядочено сначала по сумме элементов, а затем по лексикографическому порядку внутри последовательностей с данной суммой (только конечное число последовательностей даёт заданную сумму, так что все узлы достигаются; формально говоря, существует конечное число композиций заданного натурального числа, а именно 2n−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) в конец) или идём вправо (добавляем единицу к последнему числу) (за исключением корня, от которого можно идти только вниз), что показывает связь между бесконечным бинарным деревом и приведённой выше нумерацией. Сумма входов (без единицы) соответствует расстоянию от корня, что согласуется с 2n−1 узлов и глубиной n − 1 в бесконечном двоичном дереве (2 соответствует бинарности дерева).

Примечания

  1. ↑ Lecture 8, Tree Traversal. Дата обращения: 2 мая 2015. Архивировано 5 августа 2018 года.
  2. ↑ Архивированная копия. Дата обращения: 29 мая 2018. Архивировано 28 августа 2017 года.
  3. ↑ Preorder Traversal Algorithm. Дата обращения: 2 мая 2015. Архивировано 11 апреля 2019 года.
  4. ↑ Wittman, Todd Tree Traversal (PDF). UCLA Math. Дата обращения: 2 января 2016. Архивировано из оригинала 13 февраля 2015 года.
  5. ↑ Algorithms, Which combinations of pre-, post- and in-order sequentialisation are unique?, Computer Science Stack Exchange. Дата обращения: 2 мая 2015. Архивировано 12 февраля 2015 года.
  6. ↑ Morris, 1979.

Литература

  • Nell Dale, Susan D. Lilly. Pascal Plus Data Structures. — Fourth Edition. — Lexington, MA: D. C. Heath and Company, 1995.
  • Adam Drozdek. Data Structures and Algorithms in C++. — Second edition. — Brook/Cole. Pacific Grove, CA, 2001.
  • Кормен, Лейзерсон, Ривест, Штайн. Глава 12. Бинарные деревья поиска // Алгоритмы: построение и анализ. — 3-е. — СПб.: Диалектика, 2020. — С. 319—322. — 1328 с.

Ссылки