найти самого низкого общего предка в общем дереве, имеющем родительские идентификаторы
Моя задача — найти LCA для общего дерева, которое будет создано из списка в текстовом файле. Я ищу наиболее эффективную реализацию. Данные представлены в виде:
Id, информация, ParentId
Данные не сортируются никак. Я думал о создании дерева, но это заняло бы по крайней мере O (nlogn). Хотя база журнала не 2. Это зависит от среднего числа детей, я полагаю.
Вместо этого, если я сохраню узлы в хеш-таблице, то поиск LCA будет лучше, чем O (nlogn). Правильно? Для каждого родителя узла назначения я должен проверить, был ли он посещен исходным узлом или нет (предположим, что мы начинаем с исходного узла до корня и отмечаем всех родителей в пути как посещенные), что занимает O (LOGN). Поскольку мы просто проверяем родителей, это будет лучше, чем O (nlogn).
Есть идея получше?
Решение
Предположим, что ваше дерево каким-то образом сбалансировано, т.е. Высота O (logn), ваша структура хеш-таблицы должна давать алгоритм O (n).
Первый след от источника и места назначения до корня. У вас будет два пути длины O (logn). Например. SXYZR и DWYZR. S и D — источник и пункт назначения. R является корнем. Это занимает O (logn) время.
Тогда вы можете найти самый длинный постфикс, который является YZR. Y будет LCA. Это занимает O (logn) время.
Помните, что вам нужно O (n) время, чтобы прочитать ввод и построить хеш-таблицу.
Другие решения