타르잔의 오프라인 최저 공통 조상 알고리즘

Tarjan's off-line lowest common ancestors algorithm
타르잔의 강하게 연결된 성분 알고리즘과 혼동하지 않기 위해서입니다.

컴퓨터 과학에서 타르잔의 오프라인 최저 공통 조상 알고리즘은 연합 찾기 데이터 구조를 기반으로 나무의 노드 쌍에 대한 최저 공통 조상을 계산하는 알고리즘이다.뿌리깊은 나무 T에서 d와 e 두 개의 노드의 가장 낮은 공통조상은 d와 e 모두의 조상이며 T에서 가장 깊은 깊이를 가진 노드 g이다.1979년 이 기술을 발견한 로버트 타르잔의 이름을 따서 지은 것이다.타르잔의 알고리즘은 오프라인 알고리즘이다. 즉, 다른 가장 낮은 공통 조상 알고리즘과는 달리, 가장 낮은 공통 조상 알고리즘을 원하는 모든 노드 쌍을 미리 지정해야 한다.알고리즘의 가장 간단한 버전은 유니언 찾기 데이터 구조를 사용하는데, 다른 가장 낮은 공통 조상 데이터 구조와는 달리 노드 쌍의 수가 노드 수와 크기가 유사할 때 작업당 일정한 시간 이상이 소요될 수 있다.가보우&타르잔(1983)의 후기 정교화는 알고리즘을 선형 시간까지 가속시킨다.

가성음

아래의 가성소드는 노드 n의 자녀가 설정된 n.children에 있는 트리의 루트 r을 고려하여 P에서 각 쌍의 가장 낮은 공통 조상을 결정한다.이 오프라인 알고리즘의 경우 미리 P를 설정해 두어야 한다.그것은 분리된 숲의 MakeSet, Find, Union 기능을 사용한다.MakeSet(u)는 u를 싱글톤 세트로 제거하고, Find(u)는 u가 포함된 세트의 표준 대표자를 반환하며, Union(u,v)은 u가 포함된 세트와 v가 포함된 세트를 병합한다.TarjanOLCA(r)는 먼저 루트 r에서 호출된다. 

TarjanOLCA(u)는 MakeSet(u) u.ancestor :=유아동의 각 v에 대해 TarjanOLCA(v) Union(u, v) Find(u)이다.조상 :=u.color :=b.color ==black인 경우 P의 {u, v}이(가) "Tarjan의 가장 낮은 공통 조상 " + u + " 및 " + v + "은 " + Find(v).ancestor + "이다."를 인쇄한다.

각 노드는 처음에는 흰색이며, 그 뒤에 검은색으로 칠해져 있으며, 모든 아이들이 방문하였다.

조사할 각 노드 쌍 {u,v}에 대해:

  • v가 이미 검정색인 경우(viz. 트리의 사후 주문 트래버설에서 v가 u보다 앞에 오는 경우):u가 검은색인 후, 이 쌍의 가장 낮은 공통 조상은 Find(v).ancestor로 사용 가능하지만, u와 v의 LCA가 검정색이 아닌 경우에만 사용할 수 있다.
  • 그렇지 않은 경우:v가 검은색이면 LCA를 Find(u)로 사용할 수 있다.LCA는 검은색이 아닌 반면, 조상.

참고로, 다음은 분리된 포리스트에 대해 MakeSet, Find 및 Union의 최적화된 버전이다.

기능 MakeSet()):=-1x.rank:Union(), y)xRoot은=1기능:= Find())yRoot:= Find(y)만약xRoot.rank>yRoot.rank 다음 yRoot.parent:=xRoot 다른 만약xRoot.rank<>yRoot.rank 다음 xRoot.parent:=yRoot 다른 만약xRoot.rank == yRoot.rank 다음 yRoot.parent:=xRootx.parent 있다.         xRoot.순위 := xRoot.rank + 1 함수 Find(x)는 x.parent != x 다음 x.parent := Find(x.parent)가 x.parent를 반환하는 경우 입니다.

참조

  • Gabow, H. N.; Tarjan, R. E. (1983), "A linear-time algorithm for a special case of disjoint set union", Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 246–251, doi:10.1145/800061.808753.