Вывести двоичное дерево в стиле BFS с пробелом O (1)

Question

Мне было интересно, возможно ли напечатать двоичное дерево в первом порядке, используя только пробел O (1)?

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

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

Есть идеи?

Answer 1

Это будет зависеть от некоторых более тонких определений, например, если у ребер есть обратные ссылки.Тогда это легко, потому что вы можете просто перейти по обратной ссылке вверх по дереву.В противном случае я не могу придумать способ сделать это без O (lg количество узлов ) пробела, потому что вам нужно запомнить хотя бы узлы "выше".

Обновление

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

Проблема в том, что это O (1) пробел, но O (n ^ 2) время.

Другое обновление

Давайте предположим, что мы достигли узла n_i, и мы хотим связаться с родителем этого узла, который мы назовем wlg n_j.Мы определили выделенный корневой узел n_0.

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

Когда вы снова запускаете BFS из n_0, вы гарантированно (предполагая, что это действительно дерево), что в НЕКОТОРОЙ точке вы перейдете край(n_j, n_i).В этот момент вы замечаете, что вернулись в n_i.Вы сохранили n_j, и, таким образом, вы знаете, что обратный край равен (n_i, n_j).

Таким образом, вы получаете этот единственный возвратный путь только с двумя дополнительными ячейками, одна для n_0 и одна для «сохраненного» узла.Это O (1)

Я не очень уверен в O (n ^ 2) - уже поздно, и это был тяжелый день, поэтому я не хочу сочинять доказательства.Я уверен, что это O ((| N | + | E |) ^ 2) где | N |и | E |являются размерами наборов вершин и ребер соответственно.

Answer 2

Интересный особый случай - кучи.

С heapq Документы :

Кучи - это двоичные деревья, для которых каждый родительский узел имеет значение меньше чем или равно любому из его детей. Эта реализация использует массивы для которых heap[k] <= heap[2*k+1] и heap[k] <= heap[2*k+2] для всех k, считая элементы с нуля. Для сравнения не существует элементы считаются бесконечными. Интересное свойство куча в том, что его самый маленький элемент всегда является корнем, heap[0]. [объяснение Франсуа Пинар]

Как дерево представлено в памяти (индексы массива):

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

В этом случае узлы в массиве уже хранятся в первом порядке по ширине.

for value in the_heap:
    print(value)

O (1) в пространстве.

Answer 3

Я знаю, что это строго не ответ на вопрос, но посещение узлов дерева в порядке по ширине можно сделать, используя пространство O ( d ), где d - это глубина дерева, по рекурсивному итеративному поиску по глубине, первый поиск (IDDFS). Конечно, для стека требуется место. В случае сбалансированного дерева, d = O (lg n ), где n - количество узлов. Честно говоря, я не понимаю, как бы вы делали это в постоянном пространстве без обратных ссылок, предложенных @Charlie Martin.