Comments 4
Правда, "классические" алгоритмы для решения этой задачи работают лишь с парой узлов (раз, два, три, четыре)
Скорее всего из-за следующего тождества
LCA(a1, a2, ..., an) = LCA(a1, LCA(a2, a3, ..., an))
В отдельных случаях можно сделать сделать LCA для n узлов быстрее, чем n раз сделать LCA двух узлов, но это уже редкость (хотя я на практике сталкивался с такой необходимостью)
а мы, используя всю мощь PostgreSQL,
Вот вам тоже самое только на питоне
from collections import Counter
from typing import List, Tuple
class LCAfinder:
def __init__(self, arcs: List[Tuple[int, int]]):
self.parents = dict()
for arc in arcs:
self.parents[arc[0]] = arc[1]
def query(self, nodes: List[int]):
num_nodes = Counter()
for node in nodes:
while node is not None:
num_nodes[node] += 1
node = self.parents[node]
node = nodes[0]
while node is not None:
if num_nodes[node] == len(nodes):
return node
node = self.parents[node]
lca_finder = LCAfinder([(1, None)
, (2, 1)
, (3, 1)
, (4, 2)
, (5, 2)
, (6, 5)
, (7, 5)])
print(lca_finder.query([4, 6, 7]))Поставлю плюс статье, потому что узнал, что SQL может не только тормознутый JOIN, но и по дереву пройтись. Но вообще на хабре в алгоритмическом треде хотелось бы более серьезного изучения материала перед написанием статьи.
Однако, в приведенном python-коде видится ошибка:
if num_nodes[node] == len(nodes):
return nodeОн почему-то неявно предполагает, что необходимый из достигнутых всеми путями узлов почему-то окажется первым при переборе. То есть сортировка по сумме длин путей не применена - а без ее учета мы рискуем получить 1 вместо 2.
Впрочем, необходимые правки тривиальны.
SQL HowTo: ближайший общий предок в дереве (LCA)