수준 상위 문제

Level ancestor problem

그래프 이론과 이론 컴퓨터 과학에서, 레벨 조상 문제는 주어진 루트 트리 T를 트리의 루트로부터 주어진 거리에서 주어진 노드의 조상을 결정할 수 있는 데이터 구조로 전처리하는 문제이다.

보다 정확하게는 T를 n개의 노드가 있는 루트 트리로 하고 v를 T의 임의 노드라고 합니다.수준 상위 쿼리 LA(v,d)는 깊이 d에서 노드 v의 상위 항목을 요청합니다. 여기서 트리의 노드 v 깊이는 트리의 루트에서 노드 v로 가는 최단 경로의 에지 수입니다.O(n)를 취하고 [1][2]O(n) 스토리지 공간을 사용하는 데이터 구조를 구축하는 전처리 알고리즘 후 쿼리당 일정한 시간 내에 이 문제를 해결할 수 있습니다.

순진한 방법

(v,2)의 수준 상위 항목 및 루트 r에서 노드 v로의 경로입니다.

노드의 수평 조상을 찾는 가장 간단한 방법은 트리의 뿌리를 향해 트리를 오르는 것입니다.트리의 루트에 대한 경로에서 노드의 모든 상위 항목을 방문할 수 있으므로 보고할 수 있습니다.이 경우 트리를 전처리할 필요가 없으며 쿼리에 응답하는 시간은 O(h)입니다. 여기서 "h"는 트리의 높이입니다.이 접근방식은 트리의 높이가 크고 대량의 쿼리를 처리해야 하는 상황에서는 실행할 수 없습니다.

또는 가능한 모든 솔루션을 사전에 계산하여 표에 저장할 수도 있습니다.이 경우 쿼리는 O(1)에서 응답할 수 있지만 공간과 전처리 시간은 O(n2)입니다.

전처리 없이 일정한 시간에 응답할 수 있는 가장 간단한 쿼리는 LA(v, 0)와 LA(v, depth(v)입니다.전자의 경우 답은 항상 트리의 루트이며 후자의 경우 답은 노드 v 자체입니다.이러한 결과는 각각 O(1)가 됩니다.

트리를 통과하는 경로를 스큐 바이너리 랜덤 액세스 목록에 저장하면 트리를 한 번에 한 O(1) 단계 아래로 확장할 수 있지만 이제 검색을 O(log(p)로 진행할 수 있습니다. 여기서 "p"는 v에서 요청된 깊이까지의 거리입니다.이 접근방식은 트리가 특히 넓거나 온라인으로 확장될 예정이기 때문에 스토리지와 액세스 시간은 경로 [3]길이에 따라 결정되므로 효과적으로 전처리할 수 없는 경우에 실현 가능합니다.

점프 포인터 알고리즘

점프 포인터[1] 알고리즘은 트리를 O(n log n) 시간 내에 사전 처리하고 O(log n) 시간 내에 레벨 상위 쿼리에 응답합니다.점프 포인터 알고리즘은 트리의 각 정점에 최대 n개의 포인터를 기록합니다.이러한 포인터는 트리의 루트를 향해 트리 위로 점프하기 때문에 점프 포인터라고 불립니다.나무의 주어진 노드 v의 경우, 알고리즘}. 이 배열의 지점2ith 조상과 v 같은 데이터 구조의 사용은ith 요소 우릴톤 반쯤 달려서 점프가 어디 ℓ)⌊ 로그 2⁡(깊이 ⁡(v))⌋{\displaystyle \ell =\lfloor \log_{2}(\operatorname{깊이}(v))\rfloor 길이 l{나는\displaystyle}의 점퍼들 배열을 저장합니다그트리를 만듭니다.알고리즘이 쿼리를 처리하도록 요구받으면 이러한 포인터를 사용하여 트리를 반복적으로 점프합니다.점프 횟수는 최대 로그 n회이므로, 쿼리는 로그 n회로 응답할 수 있다.

사다리 알고리즘

사다리 알고리즘은 트리를 경로 집합으로 단순화하는 아이디어를 기반으로 합니다.그 이유는 레벨 상위 쿼리의 경우 경로를 쿼리하기가 더 쉽기 때문입니다.노드 r에 루트가 있는n개의 노드로 구성된 패스 P를 생각해 보겠습니다.경로를 Ladder라고 하는 크기 n의 배열에 저장할 수 있으며 Ladder[d] if depth(v)≤d를 반환하여 LA(v, d)의 레벨 상위 쿼리에 빠르게 응답할 수 있습니다.이 작업은 O(1)가 필요합니다.단, 이것은 지정된 트리가 경로인 경우에만 작동합니다.그렇지 않으면 경로로 분해해야 합니다.이것은 2단계로 이루어집니다.장경로 분해와 장경로를 사다리로 확장합니다.

스테이지 1: 롱패스 분해

이것은 주어진 트리를 경로로 분해하는 재귀 메서드입니다.이 단계는 트리에서 가장 긴 루트-잎 경로를 찾는 것으로 시작합니다.그런 다음 트리에서 이 경로를 제거하고 트리의 나머지 부분을 하위 트리로 분할하여 각 하위 트리를 재귀적으로 처리합니다.경로가 분해될 때마다 루트에서 리프까지의 경로에 요소를 포함하는 경로와 관련하여 배열이 생성됩니다.이 재귀의 기본 케이스는 트리가 제거되면 빈 그래프가 남는 경로인 경우입니다.각 꼭지점 v는 그것을 포함하는 사다리인 독특한 사다리를 가지고 있으며 우리는 그것을 "v의 사다리"라고 부릅니다.그러나 이 전처리 단계 후에는 쿼리에 빠르게 응답할 수 없습니다.실제로 레벨 상위 쿼리에 응답하려면 알고리즘은 루트에 도달할 때까지 경로에서 다른 경로로 점프해야 합니다.또한 이러한 경로의 δ('n)가 리프 투 루트 경로에 존재할 수 있습니다.이를 통해 O(n) 시간 내에 트리를 전처리할 수 있고 O( on) 시간 내에 쿼리에 응답할 수 있는 알고리즘이 개발됩니다.최적의 질의 시간에 도달하기 위해서는 아래에 설명된 두 번째 단계에서 결과를 처리해야 합니다.

2단계: 긴 경로를 사다리로 확장

알고리즘의 첫 번째 단계는 트리를 여러 개의 분리된 경로로 분해합니다.알고리즘의 두 번째 단계에서는 각 경로가 확장되므로 결과 경로가 서로 배타적이지 않습니다.알고리즘의 첫 번째 단계에서는 각 경로가 h' 크기의 배열과 관련지어집니다.우리는 같은 배열의 경로 맨 위에 h' 직계 조상을 추가함으로써 이 경로를 확장합니다.이렇게 하면 각 어레이가 원래 크기의 최대 2배까지 확장되므로 모든 래더의 총 노드 수가 2n개가 됩니다.사다리 수는 변경되지 않으며 각 노드의 사다리는 동일하게 유지됩니다.현재는 노드 v를 여러 경로에 나열할 수 있지만 알고리즘의 첫 번째 단계에서 노드 v와 연결된 노드 v가 래더입니다.이 두 단계는 O(n)의 프로세스일 수 있지만 쿼리 시간은 아직 일정하지 않습니다.높이 h의 노드 u에 대한 수평 조상 쿼리를 고려합니다. u의 사다리 맨 위로 이동하면 최소 2h 높이의 정점에 도달합니다.모든 노드의 높이가 최소 1이므로 이 작업을 수행한 후 높이가 최소i 2인 노드에 도달하므로 로그 n회까지 이 작업을 수행해야 합니다.그러면 쿼리 시간이 O(log n)가 됩니다.

스테이지 3: 두 가지 접근법의 조합

사다리 알고리즘은 그 자체로는 효과가 없는 것으로 판명되었습니다.실제로 점프 포인터 알고리즘과 래더 알고리즘은 서로 보완합니다.두 알고리즘은 반대 방향으로 작동합니다. 점프 포인터 알고리즘은 기하급수적으로 홉을 줄이고 래더 알고리즘은 기하급수적으로 홉을 증가시킵니다.2개의 알고리즘을 조합하면 O(1)시간 내에 쿼리에 응답할 수 있습니다.단일 점프 포인터는 트리 절반 이상에서 모든 쿼리를 수행하며, 그 이후에는 하나의 사다리만 올라가면 쿼리에 응답합니다.그 결과 O(n log n)의 전처리 시간과 O(1)의 쿼리 시간이 발생합니다.전처리는 Method of Four Russians의 적용으로 더욱 O(n)시간으로 단축할 수 있다.Method of Four Russians는 트리를 선형 전처리를 통해 작은 트리로 축소하고 모든 트리의 완전한 열거와 이들 트리의 전처리를 여전히 O(n)시간으로 할 수 있다.크기(log n)/4의 트리이면 충분합니다.

Berkman과 Vishkin의 솔루션

다른 해결책은 Berkman과 [2][4]Vishkin 덕분입니다.이 솔루션은 트리 처리를 위한 오일러 투어 기술에 기초하고 있습니다.주요 관찰은 LA(v,d)가 v의 마지막 출현 이후 오일러 투어에 나타나는 깊이 d의 첫 번째 노드라는 것이다.따라서, 오일러 투어와 깊이에 대한 관련 정보를 구성함으로써, 이 문제는 더 작은 검색(FS)이라는 이름의 배열에 대한 쿼리로 감소됩니다.어레이 A 및 유효한 인덱스 i에 대해 FS(i,x)는 A[i]<x(여기서 x=d+1을 사용한다)가 되도록 첫 번째 인덱스 j>i를 반환한다.FS 문제에 대한 효율적인 해법은 일반적으로 어렵지만, 오일러 투어에서 발생하는 특수한 경우에는 더 쉽다. 이 경우 인접 요소들은 ±1만큼 다르다.이 아이디어는 복잡도 O(n log n)의 전처리 알고리즘을 사용하여 O(1) 쿼리 시간을 산출합니다.전처리 시간은 Method of Four Russians의 적용에 의해 O(n)로 향상된다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c Bender, Michael A.; Farach-Colton, Martin (2004). "The Level Ancestor Problem Simplified". Theor. Comput. Sci. 321: 5–12. doi:10.1016/j.tcs.2003.05.002.
  2. ^ a b Berkman, Omer; Vishkin, Uzi (Apr 1994). "Finding level-ancestors in trees". J. Comput. Syst. Sci. 2. 48 (2): 214–230. doi:10.1016/S0022-0000(05)80002-9.
  3. ^ Kmett, Edward. "O(log n) persistent on-line lowest common ancestor calculation without preprocessing". Retrieved 8 May 2013.
  4. ^ Ben-Amram, Amir M. (2009). "The Euler Path to Static Level-Ancestors". arXiv:0909.1030v1 [cs.DS].