Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
«Поиск по дереву» перенаправляется сюда. Его не следует путать с деревом поиска .
Алгоритмы поиска по графам и деревьям
Списки
похожие темы
  • v
  • т
  • е

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

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

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

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

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

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

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

Обход двоичного дерева в глубину (пунктирный путь):
  • Предварительный заказ (доступ к узлу в красной позиции ● ) :
        F, B, A, D, C, E, G, I, H;
  • В порядке (доступ к узлу в зеленой позиции ● ) :
        A, B, C, D, E, F, G, H, I;
  • Пост-заказ (доступ к узлу в позиции синий ● ) :
        A, C, E, D, B, H, I, G, F.

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

Общий рекурсивный шаблон для обхода двоичного дерева таков:

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

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

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. Пройдите по правому поддереву, рекурсивно вызывая функцию предварительного заказа.

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

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

  1. Пройдите по левому поддереву, рекурсивно вызывая функцию упорядочения.
  2. Доступ к части данных текущего узла (на рисунке: позиция зеленая).
  3. Пройдите по правому поддереву, рекурсивно вызывая функцию упорядочения.

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

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

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

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

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

  1. Пройдите по левому поддереву, рекурсивно вызывая функцию пост-заказа.
  2. Пройдите по правому поддереву, рекурсивно вызывая функцию пост-заказа.
  3. Доступ к части данных текущего узла (на рисунке: синяя позиция).

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

Общее дерево [ править ]

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

  1. Если узел отсутствует, вернитесь.
  2. Доступ (= посещение) узла (позиция предварительного заказа).
  3. Для каждого i от 1 до number_of_children - 1 выполните:
    1. Рекурсивно пройти i -й дочерний элемент.
    2. Узел доступа (в порядке).
  4. Рекурсивно пройти по последнему дочернему элементу.
  5. Узел доступа (позиция после заказа).

В зависимости от решаемой проблемы предварительный заказ, последующий заказ и особенно одна из (number_of_children - 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копирования в рекурсивной процедуре. . Это означает, что родительский элемент не может быть завершен до завершения всех дочерних элементов.

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

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

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

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

В порядке [ править ]

inorder (node) if (node ​​== null ) return inorder (node.left) посещение (узел) inorder (node.right)
iterativeInorder (узел) s ← пустой стек  while ( не s.isEmpty () или node null ) if (node ​​≠ null ) s.push (узел) узел ← node.left еще узел ← s.pop () посещение (узел) узел ← узел.права

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

postorder (узел) if (node ​​== null ) return postorder (node.left) postorder (node.right) посещение (узел)
iterativePostorder (узел) s ← пустой стек lastNodeVisited ← null  while ( не s.isEmpty () или node ≠ null ) if (node ​​≠ null ) s.push (узел) узел ← node.left еще peekNode ← s.peek () // если правый дочерний элемент существует и пересекает узел // от левого дочернего элемента, затем двигаться вправо если (peekNode.right ≠ null  и lastNodeVisited ≠ peekNode.right) узел ← peekNode.right еще посещение (peekNode) lastNodeVisited ← s.pop ()

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

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

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

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

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

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

Недостатки:

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

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

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

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

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

levelorder (корень) q ← пустая очередь q.enqueue (корень) пока  не q.isEmpty () делать узел ← q.dequeue () посещение (узел) если node.left ≠ null,  то q.enqueue (node.left) если node.right ≠ null,  то q.enqueue (node.right)

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

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

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

С другой стороны, для дерева глубины 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)

и т.п.

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

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

  1. ^ «Лекция 8, Обход дерева» . Дата обращения 2 мая 2015 .
  2. ^ Пфафф, Бен (2004). Введение в деревья двоичного поиска и сбалансированные деревья . Фонд свободного программного обеспечения, Inc.
  3. ^ Методы обхода двоичного дерева
  4. ^ "Алгоритм обхода предзаказов" . Дата обращения 2 мая 2015 .
  5. ^ L перед R означает (стандартный) обход против часовой стрелки - как на рисунке.
    Выполнение N до, между или после L, R определяет один из описанных методов.
    Если паркур берется в обратном направлении (по часовой стрелке), то обход называется обратным. Это описано, в частности, для обратного порядка , когда данные должны быть получены в порядке убывания.
  6. ^ Виттман, Тодд. «Обход дерева» (PDF) . UCLA Math . Архивировано из оригинального (PDF) 13 февраля 2015 года . Проверено 2 января 2016 года .
  7. ^ «Алгоритмы, какие комбинации пре-, пост- и упорядоченной секвенирования уникальны ?, Computer Science Stack Exchange» . Дата обращения 2 мая 2015 .
  8. ^ Моррис, Джозеф М. (1979). «Простой и дешевый обход бинарных деревьев». Письма об обработке информации . 9 (5). DOI : 10.1016 / 0020-0190 (79) 90068-1 .

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

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

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

  • Хранение иерархических данных в базе данных с примерами обхода в PHP
  • Управление иерархическими данными в MySQL
  • Работа с графиками в MySQL
  • Пример кода для рекурсивного и итеративного обхода дерева, реализованного на C.
  • Пример кода для рекурсивного обхода дерева на C #.
  • Посмотрите, как обход дерева реализован на различных языках программирования в Rosetta Code.
  • Обход дерева без рекурсии