Можно ли обходить дерево без рекурсии, стека или очереди, и только с горсткой указателей?

15

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

Так это возможно или невозможно? Почему или почему нет?

Редактировать: чтобы добавить некоторые пояснения, я реализовал это в двоичном дереве, которое имело три элемента - данные, хранящиеся в каждом узле и указатели на двух дочерних элементов. Мое решение может быть распространено на n-арные деревья с несколькими изменениями.

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

NL - извиниться перед Моникой
источник
3
Вам необходимо указать ограничения. Могу ли я мутировать дерево? Как представлено дерево? (Например, имеет ли каждый узел родительский указатель на своего родителя?) Ответ будет зависеть от конкретных ограничений; без указания этих ограничений это не является корректной задачей.
DW
2
Я предполагаю, что противопоставление, которое профессора действительно хотели выразить, было «с дополнительным пространством». Но каким было ваше решение? О(1)
Рафаэль

Ответы:

17

Много исследований в этой области было проведено с использованием метода «дешевого» обхода деревьев и общих структур списков в контексте сбора мусора.

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

Насколько я знаю, двоичные деревья, реализованные с использованием указателей обычным способом (указатель слева и справа на узел), могут быть пройдены с использованием метода потоков в методе, приписанном Моррису . NIL-указатели временно повторно используются для наведения пути к корню. Умная часть заключается в том, что во время обхода можно отличить исходные ребра от временных нитей-связей, используя способ, которым они образуют циклы в дереве).

Хорошая часть: нет дополнительной структуры данных. Плохая часть: немного жульничает, стек хитроумно лежит внутри дерева. Очень умно.

Доказательство скрытого стека показано в P. Mateti и R. Manghirmalani: пересмотрен алгоритм обхода дерева Морриса DOI: 10.1016 / 0167-6423 (88) 90063-9

Дж. М. Моррис: Обход бинарных деревьев просто и дешево. IPL 9 (1979) 197-200 DOI: 10.1016 / 0020-0190 (79) 90068-1

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

Г. Линдстрем: Сканирование структур списка без стеков или битов тегов. IPL 2 (1973) 47-51. DOI: 10.1016 / 0020-0190 (73) 90012-4

Возможно, самый простой способ - это метод Робсона . Здесь стек, необходимый для классического алгоритма, проходит через листья.

JM Robson: улучшенный алгоритм обхода двоичных деревьев без вспомогательного стека IPL 1 (1973) 149-152. 10,1016 / 0020-0190 (73) 90018-5

IPL = письма для обработки информации

Хендрик Ян
источник
Мне тоже нравится это решение, хотя я бы не придумал его на первом курсе компьютерных наук. Да, вероятно, измена по правилам моего профессора.
NL - извиниться перед Моникой
2
Можете ли вы дать ссылки / ссылки на стратегии?
Рафаэль
1
Плохая часть этого метода в том, что вы не можете одновременно выполнять более одного обхода.
Жиль "ТАК - перестань быть злым"
6

v

Юваль Фильмус
источник
Это похоже на решение, которое профессор структур данных, предложивший проблему, использовал для ее решения. Дискретный профессор математики возразил, что «это стало графиком, а не деревом», если есть указатели на родителей.
NL - извиниться перед Моникой
@NathanLiddle: Это будет зависеть от используемого определения дерева (которое вы не дали). В «реальном мире» представление дерева Ювала разумно, даже если теория графов скажет, что определяемые им вещи, конечно, не являются деревьями.
Рафаэль
@ Рафаэль Да, и это соответствует требованиям оригинального профессора, так что это приемлемый ответ для меня.
NL - извиниться перед Моникой
0

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

Pseudocode:
root = pointer root 
depth = integer 0
finished = bool false
//If we n-ary tree also track how many children have been found 
//on the node with the most children for the purposes of this psuedocode 
//we'll assume a binary tree and insert a magic number of 2 so that we 
//can use bitwise operators instead of integer division 
while(!finished)
    ++depth
    treePosition = pointer root
    finished = true;
    for i := 0..2**depth
        for j := 0..depth
            if (i & j) //bitwise operator explained below
                // if right child doesn't exist break the loop
                treePosition = treePosition.rightChild
            else
                // if left child doesn't exist break the loop
                treePosition = treePosition.leftChild
        if j has any children
            finished = false
            do anything else you want when visiting the node

Для первых нескольких уровней это будет выглядеть так, как вы можете видеть, побитовый оператор в псевдокоде просто решает повернуть влево или вправо двоичное дерево:

2**1       0               1
2**2   00      01      10      11
2**3 000 001 010 011 100 101 110 111

Для n-ар вы бы взяли i% (maxChildren ** j) / j, чтобы определить, какой путь выбрать между 0 и maxChildren.

В каждом узле n-ary вам также необходимо проверить, больше ли число дочерних элементов, чем maxChildren, и обновить его соответствующим образом.

NL - извиниться перед Моникой
источник
Если вы хотите использовать больше, чем двоичный код, вам нужно будет заменить магическое число 2 на переменную, которая будет увеличиваться, чтобы соответствовать максимальному количеству дочерних элементов, которые он видел, и вместо побитовых операторов вам придется делить на ту же самую переменную, возведенную в сила глубины дерева, где вы были.
NL - извиниться перед Моникой
О(1)О(Л.Г.N)О(1)О(N)О(1)дополнительное пространство "). Например, что вы делаете, если depthширина превышает int?
DW
DW, профессор, который поставил проблему, не навязывал эту проблему этому ограничению, и что меня очень беспокоило в моей беседе с дискретным профессором математики, так это то, что он НИКОГДА не признавал, что можно даже обходить дерево без рекурсии, составлять стеки, или очередь, любой ценой. Единственное, что демонстрирует мое решение, это то, что можно делать все итеративно, что можно сделать рекурсивно, даже если вы удалите опции для стека, очереди и т. Д.
NL - Приносим свои извинения Монике
Одно дело сказать, что это неразрешимо без O (1) дополнительного пространства, совсем другое - объявить проблему неразрешимой без рекурсии, стека или очереди. И на самом деле, увидев мой код, дискретный профессор математики все равно не согласится с этим, потому что он сказал, что «i» в первом цикле for занимает место в очереди. Как это для упрямых?
NL - извиниться перед Моникой
1
idepthdepthΘ(N)Θ(N)iО(1)