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

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

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

Типы

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

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

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

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

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

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

При поиске в глубину (DFS) дерево поиска максимально углубляется перед переходом к следующему родственнику.

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

  1. Если текущий узел пуст, вернитесь.
  2. Выполните следующие три операции в определенном порядке:
    N: посетить текущий узел.
    L: рекурсивно пройти по левому поддереву текущего узла.
    R: рекурсивно пройти по правому поддереву текущего узла.

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

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 - F

Предзаказ, NLR

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

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

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

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

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

В порядке, LNR

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

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

Обратный предзаказ, NRL

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

Обратный пост-заказ, RLN

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

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

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

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

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

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

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

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

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

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

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

Другие типы

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

Приложения

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

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

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

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

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

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

Реализации

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

Предзаказ

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)

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

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

Пост-заказ

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

procedure iterativePostorder(node)
    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)
    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

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

Объект, nodeс которого нужно начать, мог быть найден в двоичном дереве поиска bstс помощью стандартной функции поиска , которая показана здесь в реализации без родительских указателей, т.е. она использует a 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 возвращает в заказе-сосед node, либо в-заказ запасного SUC cessor (для dir=1) или в-заказ запасных предопределенных cessor (для 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)

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

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

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

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

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

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

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

Недостатки:

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

Обход Морриса - это реализация обхода по порядку, использующая потоки:

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

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

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

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 n −1 композиций из n ≥ 1 ), что дает обход. Ясно:

  1. ()
  2. (1)
  3. (1, 1) (2)
  4. (1, 1, 1) (1, 2) (2, 1) (3)
  5. (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

и т.п.

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

использованная литература

Источники

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

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