Tarjan의 오프라인 최소 공통 조상 알고리즘

Question

현재 이진 트리에서 두 노드의 최소 공통 조상을 얻는 방법에 대해 Tarjan의 알고리즘에 대해 읽고 있습니다.

나는 의사 코드 Wikipedia을 읽었지만 그 요점은 파악하지 못했습니다. 나는 주어진 이진 트리에 알고리즘을 적용 할 수 없다는 것을 의미한다. 나는 또한 Google에서 각 단계에 대한 설명을 찾으려고했지만 가치가 없었습니다. 그래서, 만약 누군가이 알고리즘이 어떻게 이진 트리에서 작동하는지 이해하는데 도움을 줄 수 있다면, 그것은 정말로 두드러 질 것입니다.

Answer 1

이진 트리 외에도이 알고리즘을 적용하기 위해 분리 집합이라는 다른 데이터 구조를 구현해야합니다. 이 데이터 구조, MAKE-SET, UNION, FIND-SET의 세 가지 주요 방법이 있습니다. 더 나은 이해를 위해 21 장 "알고리즘 소개"의 "불연속 집합에 대한 데이터 구조"를 읽으시기 바랍니다.