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

14

Это может быть очень наивно, но мне было интересно, это контекст бинарных деревьев (простые, отсортированные и сбалансированные) всех типов обхода:

  • предварительный заказ в глубину
  • в порядке глубины
  • первый заказ на глубину
  • в ширину

Какова реальная полезность до и после заказа? Я имею в виду, есть ли какой-то тип и / или конфигурация бинарного дерева, в котором обход до и / или после заказа даст (некоторые) преимущество (преимущества) над двумя другими?

AFAICS, существуют определенные типы и конфигурации бинарных деревьев, для которых порядок и ширина могут дать определенное преимущество:

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

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

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

Дракон Шиван
источник

Ответы:

14

В статье в Википедии есть хорошее краткое описание того, когда вы хотите использовать различные типы поиска в глубину:

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

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

Карл Билефельдт
источник
Wikipedia по состоянию на 10 ноября 2019 года изменилась, и первое описание также принадлежит Post-Order, что сбивает с толку. Вот почему я попал сюда в поисках другого источника информации.
whoan
13

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

Например, предположим, что у вас есть дерево разбора, например:

    *
   / \
  +   \
 / \   \
A   B   C

Вы могли бы сериализовать его как * + A B Cв порядке префикса или A B + C *в порядке постфикса. Если вы вообще работаете с языковыми процессорами, такие вещи должны быть второстепенными.

Майк Данлавей
источник
Очень хороший пример! И обратите внимание на то, как получился бы обход в порядке A + B * C, что гораздо проще понять обычным пользователям, чем любой префикс порядка постфикса.
Килиан Фот
3
@KilianFoth, кроме того, что это не то, что говорит дерево - оно говорит (A + B) * C, по крайней мере, на мой взгляд. Хотя мои пальцы HP-28s как версия AB + C * просто отлично. :-)
sdg
@ Килиан: СДГ прав. С inorder вы должны заботиться о приоритете, если вы не ставите круглые скобки вокруг всего.
Майк Данлавей
5

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

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

Килиан Фот
источник