Проверьте, связаны ли 2 узла дерева (предок / потомок) в O(1) с предварительной обработкой
Проверьте, связаны ли 2 узла дерева (т. Е. Предок-потомок)
- решить это за O(1) время, с O(N) пространством (N = количество узлов)
- предварительная обработка разрешена
Вот и все. Я пойду к своему решению (подходу) ниже. Пожалуйста, прекратите, если вы хотите думать в первую очередь.
Для предварительной обработки я решил сделать предварительный заказ (сначала рекурсивно пройти через корень, затем потомки) и назначить метку каждому узлу.
Позвольте мне объяснить метки в деталях. Каждая метка будет состоять из разделенных запятыми натуральных чисел, таких как "1,2,1,4,5" - длина этой последовательности равна (глубина узла + 1). Например, метка корня - "1", дочерние элементы корня будут иметь метки "1,1", "1,2", "1,3" и т. Д. Узлы следующего уровня будут иметь метки вроде "1,1,1". "," 1,1,2 ",..., "1,2,1 ", "1,2,2 ",...
Предположим, что " порядковый номер " узла является " индексом этого узла на основе 1 " в списке дочерних элементов его родителя.
Общее правило: метка узла состоит из его родительской метки, за которой следуют запятая и " порядковый номер " узла.
Таким образом, чтобы ответить, связаны ли два узла (т. Е. Предка-потомка) в O(1), я проверю, является ли метка одного из них " префиксом " метки другого. Хотя я не уверен, что такие метки можно считать занимающими O(N) место.
Ожидается любая критика с исправлениями или альтернативный подход.
3 ответа
Вы можете сделать это за время предварительной обработки O(n) и пространство O(n) с временем запроса O(1), если вы сохраняете номер предзаказа и номер почтового отряда для каждой вершины и используете этот факт:
Для двух заданных узлов x и y дерева T x является предком y тогда и только тогда, когда x встречается до y в обходе предзаказа T и после y в обходе после заказа.
(С этой страницы: http://www.cs.arizona.edu/xiss/numbering.htm)
То, что вы сделали в худшем случае, это тета (d), где d - глубина более высокого узла, и поэтому не O(1). Пространство тоже не O(n).
Если вы рассматриваете дерево, где узел в дереве имеет n/2 дочерних элементов (скажем), время установки меток будет равно O(n*n). Так что эта схема маркировки не будет работать....
Существуют алгоритмы общего предка линейного времени с наименьшим временем (по крайней мере, в автономном режиме). Например, посмотрите здесь. Вы также можете взглянуть на автономный алгоритм LCA Тарьяна. Обратите внимание, что эти статьи требуют, чтобы вы знали пары, для которых вы будете выполнять LCA заранее. Я думаю, что существуют также онлайновые алгоритмы с предварительным вычислением времени, но они очень сложны. Например, существует линейный алгоритм времени предварительного вычисления для задачи с минимальным диапазоном запросов. Насколько я помню, это решение дважды проходило через проблему LCA. Проблема с алгоритмом заключается в том, что он имеет такую большую константу, что требует огромных входных данных, чтобы быть на самом деле быстрее, чем алгоритм O(n*log(n)).
Существует гораздо более простой подход, который требует O(n*log(n)) дополнительной памяти и снова отвечает в постоянном времени.
Надеюсь это поможет.