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