Обход дерева

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

Типы

В отличие от связанных списков , одномерных массивов и других линейных структур данных , которые канонически просматриваются в линейном порядке, деревья можно проходить несколькими способами. Их можно проходить в порядке «в глубину» или «в ширину» . Существует три распространенных способа перемещения по ним в порядке глубины: по порядку, в предварительном порядке и после порядка. ^[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 - Г - Ж

Предзаказ, РНР

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

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

Постзаказ, LRN

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

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

В порядке, ЛНР

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

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

Обратный предзаказ, НРЛ

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

Обратный постзаказ, РЛН

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

Обратный порядок, RNL

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

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

Произвольные деревья

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

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

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

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

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

Другие типы

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

Приложения

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

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

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

Реализации

Реализация поиска в глубину

Реализация предзаказа

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

procedure iterativePreorder(node)
    if node = null
        return
    stack ← empty stack
    stack.push(node)
    while not stack.isEmpty()
        node ← stack.pop()
        visit(node)
        // right child is pushed first so that left is processed first
        if node.right ≠ null
            stack.push(node.right)
        if node.left ≠ null
            stack.push(node.left)

Постзаказная реализация

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

procedure iterativePostorder(node)
    if node = null
        return
    stack ← empty stack
    lastNodeVisited ← null
    while not stack.isEmpty() or node ≠ null
        if node ≠ null
            stack.push(node)
            node ← node.left
        else
            peekNode ← stack.peek()
            // if right child exists and traversing node
            // from left child, then move right
            if peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right
                node ← peekNode.right
            else
                visit(peekNode)
                lastNodeVisited ← stack.pop()

Порядковая реализация

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

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

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

Если дерево представлено массивом (первый индекс равен 0), то можно вычислить индекс следующего элемента: ^[8]^{[ нужны разъяснения ]}

procedure bubbleUp(array, i, leaf)
    k ← 1
    i ← (i - 1)/2
    while (leaf + 1) % (k * 2) ≠ k
        i ← (i - 1)/2
        k ← 2 * k
    return i

procedure preorder(array)
    i ← 0
    while i ≠ array.size
        visit(array[i])
        if i = size - 1
            i ← size
        else if i < size/2
            i ← i * 2 + 1
        else
            leaf ← i - size/2
            parent ← bubble_up(array, i, leaf)
            i ← parent * 2 + 2

Переход к следующему или предыдущему узлу

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

procedure search(bst, key)
    // returns a (node, stack)
    node ← bst.root
    stack ← empty stack
    while node ≠ null
        stack.push(node)
        if key = node.key
            return (node, stack)
        if key < node.key
            node ← node.left    
        else
            node ← node.right
    return (null, empty stack)

Функция InorderNext ^[2]^: 60 возвращает соседа по порядку node, либо - преемник порядок (для dir=1) или порядку по предшествующий (для dir=0) и обновленный stack, так что двоичное дерево поиска можно последовательно обходить и искать в заданном направлении. dir дальше.

procedure inorderNext(node, dir, stack)
    newnode ← node.child[dir]
    if newnode ≠ null
        do
            node ← newnode
            stack.push(node)
            newnode ← node.child[1-dir]
        until newnode = null
        return (node, stack)
    // node does not have a dir-child:
    do
        if stack.isEmpty()
            return (null, empty stack)
        oldnode ← node
        node ← stack.pop()   // parent of oldnode
    until oldnode ≠ node.child[dir]
    // now oldnode = node.child[1-dir],
    // i.e. node = ancestor (and predecessor/successor) of original node
    return (node, stack)

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

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

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

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

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

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

Недостатки:

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

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

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

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

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

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

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

procedure levelorder(array)
    for i from 0 to array.size
        visit(array[i])

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

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

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

С другой стороны, если дано дерево глубины 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 г.
^ Jump up to: ^а ^б Пфафф, Бен (2004). Введение в бинарные деревья поиска и сбалансированные деревья . Фонд свободного программного обеспечения, Inc.
^ Методы обхода двоичного дерева
^ «Алгоритм обхода предзаказа» . Проверено 2 мая 2015 г.
^ L перед R означает (стандартное) движение против часовой стрелки, как показано на рисунке.
Выполнение N до, между или после L и R определяет один из описанных методов.
Если обход производится в обратную сторону (по часовой стрелке), то обход называется обратным. Это описано, в частности, для обратного порядка , когда данные должны быть получены в порядке убывания.
^ «Алгоритмы. Какие комбинации предварительной, пост- и упорядоченной секвенализации уникальны?», Computer Science Stack Exchange . Проверено 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] Jump up to: ^а ^б Пфафф, Бен (2004). Введение в бинарные деревья поиска и сбалансированные деревья . Фонд свободного программного обеспечения, Inc.

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

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

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

[6] «Алгоритмы. Какие комбинации предварительной, пост- и упорядоченной секвенализации уникальны?», Computer Science Stack Exchange . Проверено 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 т и графов и деревьев Алгоритмы обхода
Поиск	обрезка a–b А* ИДА* МПА* СМА* Поиск по принципу «лучшее в первую очередь» Поиск луча Двунаправленный поиск Поиск в ширину Лексикографический Параллельно Б* Поиск в глубину Итеративное углубление Д* Граничный поиск Поиск точки прыжка Поиск по дереву Монте-Карло ССС*
Кратчайший путь	Беллман-Форд Дейкстры Флойд-Уоршалл Джонсонс Кратчайший путь быстрее Йен
Минимальное связующее дерево	Черника Крускала Прим Обратное удаление
Список алгоритмов поиска по графу