Вопрос по algorithm, time-complexity, ancestor, tree, preorder – Проверьте, связаны ли 2 узла дерева (предок / потомок) в O (1) с предварительной обработкой

10

Проверьте, связаны ли 2 узла дерева (т. Е. Потомок-предок)

solve it in O(1) time, with O(N) space (N = # of nodes) pre-processing is allowed

That's it. I'll be going to my solution (approach) below. Please stop if you want to think yourself first.

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

Позвольте мне объяснить метки в деталях. Каждая метка будет состоять из разделенных запятыми натуральных чисел, таких как «1,2,1,4,5» - длина этой последовательности равна(the depth of the node + 1), Например. метка корня является «1», дочерние элементы корня будут иметь метки «1,1», «1,2», «1,3»; и т. д. Узлы следующего уровня будут иметь метки, подобные «1,1,1», «1,1,2», ..., «1,2,1», «1,2,2»; ...

Предположим, что & quot;the order number& Quot; узла является & quot;1-based index of this node& Quot; в списке детей его родителя.

Общее правило: метка узла состоит из его родительской метки, за которой следуют запятая и & quot;the order number& Quot; узла.

Таким образом, чтобы ответить, связаны ли два узла (т. Е. Предка-потомка) в O (1), я 'проверю, является ли метка одного из них & quot;a prefix& Quot; другой метки. Хотя я не уверен, можно ли считать, что такие метки занимают O (N) место.

Ожидается любая критика с исправлениями или альтернативный подход.

это пространство O (N ^ 2) в худшем случае, когда каждый узел имеет одного ребенка (лапшу). WeaselFox

Ваш Ответ

3   ответа
0

о крайней мере, в автономном режиме). Например, посмотритеВот, Вы также можете посмотреть наавтономный алгоритм LCA тарджана, Обратите внимание, что эти статьи требуют, чтобы вы знали пары, для которых вы будете выполнять LCA заранее. Я думаю, что существуют также онлайновые алгоритмы для вычисления времени линейного времени, но они очень сложны. Например, существует линейный алгоритм времени предварительного вычисления для задачи с минимальным диапазоном запросов. Насколько я помню, это решение прошло через проблему LCA дважды. Проблема с алгоритмом заключается в том, что он имеет такую большую константу, что требует огромного ввода, чтобы быть на самом деле быстрее, чем алгоритм O (n * log (n)).

Существует гораздо более простой подход, который требует O (n * log (n)) дополнительной памяти и снова отвечает в постоянном времени.

Надеюсь это поможет.

LCA излишне для этого.
1

где узел в дереве имеет n / 2 дочерних элементов (скажем), время установки меток будет равно O (n * n). Так что эта схема маркировки не будет работать ....

16

ранство O (n) с временем запроса O (1), если вы сохраняете номер предзаказа и номер почтового отряда для каждой вершины и используете этот факт:

For two given nodes x and y of a tree T, x is an ancestor of y if and only if x occurs before y in the preorder traversal of T and after y in the post-order traversal.

(С этой страницы:http://www.cs.arizona.edu/xiss/numbering.htm)

В худшем случае вы сделали тета (d), где d - глубина более высокого узла, и поэтому не O (1). Пространство тоже не O (n).

тогда как насчет сценария с лапшой? wouldent preorder и postorder точно так же, так что ни один узел не является предком другого?
@WeaselFox: Вы имеете в виду как связанный список? Разве обходы не будут взаимными?
Благодарю. Известная собственность относительно номеров почты / предзаказа. Alec
ты абсолютно прав .. мой плохой

Похожие вопросы