Триверс деревьев

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

Типы

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

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

Посетите текущий узел (на рисунке: положение красного).
Рекурсивно пересечь левый поддерев текущего узла.
Рекурсивно пересечь правый поддерев текущего узла.

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

Пост-заказ, LRN

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

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

По заказу, Lnr

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

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

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

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

Обратный пост-кедр, rln

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

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

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

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

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

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

Если текущий узел пуст, верните.
Посетите текущий узел для прохождения предварительного заказа.
Для каждого I от 1 до текущего узла подделки - 1 или от последнего до первого для обратного обхода, делай:
1. текущего узла Рекурсивно пройти через подделки .
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

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

А 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$ как высота дерева.

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

Morris in Order Traversal с использованием резьбы

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

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

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

Недостатки:

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

Morris Traversal-это реализация обхода в заказ, которая использует потоки: ^{[ 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])

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

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

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

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

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

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

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

Ссылки

^ «Лекция 8, обход дерева» . Получено 2 мая 2015 года .
^ Jump up to: ^а ^{беременный} Пфафф, Бен (2004). Введение в бинарные поисковые деревья и сбалансированные деревья . Free Software Foundation, Inc.
^ Методы прохождения бинарного дерева
^ «Алгоритм обхода предварительного заказа» . Получено 2 мая 2015 года .
^ L до R означает (стандартный) обход против часовой стрелки-как на рисунке.
Выполнение N до, между или после L и R определяет один из описанных методов.
Если обход проходит наоборот (по часовой стрелке), то обход называется обратным. Это описано, в частности, для обратного порядка , когда данные должны быть извлечены в порядке убывания.
^ «Алгоритмы, какие комбинации последовательности до и после порядка уникальны ? Получено 2 мая 2015 года .
^ Виттман, Тодд. «Триверсл деревьев» (PDF) . UCLA Math . Архивировано из оригинала (PDF) 13 февраля 2015 года . Получено 2 января 2016 года .
^ "Структуры дерева контейкспр" . Блог Фекира . 9 августа 2021 года . Получено 2021-08-15 .
^ Моррис, Джозеф М. (1979). «Пройдя бинарные деревья просто и дешево». Информационная обработка букв . 9 (5): 197–200. doi : 10.1016/0020-0190 (79) 90068-1 .

Источники

Дейл, Нелл. Лилли, Сьюзен Д. "Паскаль плюс структуры данных". DC Heath и компания. Лексингтон, Массачусетс. 1995. Четвертое издание.
Дроздек, Адам. «Структуры данных и алгоритмы в C ++». Брук/Коул. Pacific Grove, CA. 2001. Второе издание.
«Походная деревья» (Math.northwestern.edu)

Внешние ссылки

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

[Pfaff-2] Jump up to: ^а ^{беременный} Пфафф, Бен (2004). Введение в бинарные поисковые деревья и сбалансированные деревья . Free Software Foundation, Inc.

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

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

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

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

[7] Виттман, Тодд. «Триверсл деревьев» (PDF) . UCLA Math . Архивировано из оригинала (PDF) 13 февраля 2015 года . Получено 2 января 2016 года .

[8] "Структуры дерева контейкспр" . Блог Фекира . 9 августа 2021 года . Получено 2021-08-15 .

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

v Т и графика и деревьев Алгоритмы обхода
Поиск	А -b обрезка A* ИДА* LPA* SMA* Лучший поиск Лучший поиск ДИВКАЛЬНЫЙ ПОИСК Поиск по ширине Лексикография Параллель Б* Глубина-первый поиск Итеративное углубление D* Fringe Search Поиск точки прыжка Поиск дерева Монте -Карло SSS*
Кратчайший путь	Беллман - Форд Дейкстра Флойд-Варшалл Джонсон Краткий путь быстрее Иена
Минимальное охвативное дерево	Черника Крускал Прим Обратный отбор
Список алгоритмов поиска графика