Self-Adjusting Top Tree 구현하기

(이 글은 독자가 Splay tree, link/cut tree를 이해하고 있다고 가정하고 설명한다.)

 

Top tree는 동적 트리 (간선의 추가, 제거가 일어나는 트리)를 관리하는 자료구조이다. Top tree는 path 쿼리와 subtree 쿼리를 모두 지원하며, 트리의 diameter, center, median과 같은 일반적인 자료구조에서 관리하기 힘든 값들을 관리할 수 있다. 이 글은 Self-Adjusting Top Tree 논문에 기반하여 Top Tree의 구현에 대해 설명한다.

(이 논문에 대해서 구사과님이 쓰신 글도 있다.)

 

Top tree

직선형 구조를 관리하는 자료구조인 세그먼트 트리는 전체 배열을 여러 구간으로 분리하고, 이 구간들을 합치는 과정을 트리로 관리한다. Top tree는 이 방식을 트리로 확장한다.

배열의 '구간'과 같은 개념을 트리에도 적용하기 위해, 비슷한 개념인 클러스터를 생각한다. 트리에서 다음 조건을 만족하는 서브트리를 클러스터라고 정의한다. 

 

• 서브트리 외부의 정점과 연결된 정점의 개수가 2개 이하이다.

주의할 점은 클러스터는 정점이 아닌 간선의 집합으로 본다. 이제 클러스터를 통해 세그먼트 트리를 트리로 확장해 보자.

세그먼트 트리는 다음과 같은 두 종류의 노드로 이루어진 트리이다.

 

• 배열의 한 값만을 나타내는 리프 노드
• 두 자식 구간을 합친 구간을 나타내는 리프가 아닌 노드

클러스터에 기반한 Top tree에서도 비슷하게 정의할 수 있다.

 

• 하나의 간선만을 나타내는 리프 노드 (base cluster)
• 두 자식 클러스터를 합친 클러스터를 나타내는 리프가 아닌 노드

합쳐진 두 클러스터

이는 트리에서 분할 정복을 하는 것으로 볼 수 있으므로, 매우 일반화된 형태이다. 하지만 이를 효율적으로 관리하는 것은 쉽지 않다. 효율적이고 간단한 구현을 위해, Top tree를 조금 다르게 정의해보자.

 

 

먼저 트리의 각 정점에 대해 연결되어있는 간선들이 어떤 circular order를 가지고 있다고 생각한다. (circular order를 부여하는 이유는 나중에 설명할 Top tree의 연산들에 순서가 필요하기 때문이다.)

그리고 이 트리에서 두 연산 Compress와 Rake를 정의한다.

 

• Compress(v) : 차수가 $2$인 정점 $v$에 인접한 두 정점 $u,w$에 대해, 두 간선 $(u,v)$와 $(v,w)$를 합쳐서 한 간선 $(u,w)$로 대체한다. 
• Rake(v) : 차수가 $1$인 정점 $v$에 인접한 정점 $u$에 대해, 간선 $(u,v)$와 circular order 상에서 인접한 다른 간선 $(u,w)$를 합쳐서 한 간선 $(u,w)$로 대체한다. (이를 $(u,v)$가 $(u,w)$에 Rake되었다고 말할 것이다.)

이 연산들을 계속 반복하면 마지막에는 하나의 간선만이 남을 것이다. 이 과정에서 나타나는 간선들은 클러스터를 나타내고, Compress/Rake 연산은 두 클러스터를 합치는 연산을 나타낸다고 생각할 수 있다.

이제 Top Tree를 다음 세 가지 종류의 노드를 가진 이진 트리로 정의한다.

 

• 하나의 간선만을 나타내는 리프 노드 (base cluster)
• 두 자식 노드를 Compress한 간선을 나타내는 Compress 노드
• 두 자식 노드를 Rake한 간선을 나타내는 Rake 노드

Top tree의 구성

전체 트리를 Top tree로 표현하기 위해서는 Compress/Rake를 통해 전체 트리를 표현하는 클러스터를 만들어야 한다.

 

이를 위해 리프 정점 하나를 선택하여 루트로 만들고, 전체 트리를 리프에서 시작해서 루트 방향으로 가는 경로들로 나눈다. 각 경로는 루트 정점에서 끝나거나 다른 경로에서 끝나는데, 루트 정점에서 끝나는 경로를 루트 경로라고 하자.

위 그림과 같이 루트 경로는 $k$개의 간선과 $2k-2$개의 바깥 클러스터들로 이루어져 있다. 이 루트 경로를 하나의 간선으로 압축해야 한다.

 

만약 바깥 클러스터가 없다면, 리프가 아닌 $k-1$개의 정점들을 각각 Compress하면 된다. 바깥 클러스터들을 처리하기 위해서는 바깥 클러스터들을 루트 경로에 Rake시켜줘야 한다. 이는 단순히 어떤 정점을 Compress하기 전에 그 정점에 붙은 2개의 바깥 클러스터를 양 옆 간선에 Rake해주기만 하면 처리할 수 있다.

 

실제 자료구조에서는, 편의를 위해 따로 Rake 노드를 만들지 않고 Rake한 두 클러스터를 직접 Compress 노드에 연결한다. 즉, Compress 노드는 4개의 자식을 가지게 된다. (이 때 Compress 노드의 원래의 자식을 proper child, Rake 연산으로 온 자식을 foster child라 부른다.)

 

4개의 자식을 가지는 Compress node

왼쪽의 foster child가 왼쪽의 proper child에 Rake되고, 오른쪽의 foster child가 오른쪽의 proper child에 Rake된다. 그리고 compress된 정점을 기준으로 [왼쪽 foster child] - [왼쪽 proper child] - [오른쪽 foster child] - [오른쪽 proper child] 순으로 circular order를 가지게 된다. 물론, foster child가 없을 수도 있다.

위 트리로 구성한 Top tree

루트 경로가 아닌 경로에 대해서도 동일한 방법으로 경로를 한 클러스터로 압축할 수 있다. 한 정점의 바깥 클러스터에서 여러 개의 경로가 들어올 경우에는 이 경로들을 전부 Rake해서 하나로 묶어주면 된다.

Rake tree의 구성 ($N_a$, $N_b$의 자식은 생략함)

여기까지의 Top tree의 구성 방법을 정리하면 다음과 같다.

 

• 루트 경로를 선택하고 루트 경로에 인접한 경로들을 재귀적으로 계산하여 하나의 클러스터로 묶는다.
• Rake tree를 통해 한 정점에 들어오는 여러 개의 경로들을 하나의 클러스터로 묶는다.
• Compress tree를 통해 루트 경로를 하나의 클러스터로 묶는다.

구성 과정을 보았을 때, Compress tree는 하나의 경로를 압축하고${}^1$ Rake tree는 여러 개의 경로를 하나의 클러스터로 만든다. 즉, HLD의 관점에서 Compress tree는 heavy path, Rake tree는 한 정점에 연결된 light edge들을 관리한다고 볼 수 있다. 그러므로 link/cut tree의 구조와도 유사하다고 볼 수 있다. 하지만 Top tree의 경우에는 light edge들도 Rake를 통해 트리로 관리한다는 차이점이 있다.

 

한 가지 주의할 점은 Rake tree 안에서도 circular order를 유지해야 한다. 또한 Compress tree가 관리하는 경로의 순서도 유지할 수 있다. 위 그림들의 Compress tree를 보면 오른쪽으로 갈수록 루트 노드에 가까워진다. 하지만 항상 Compress tree의 순서를 유지하면서 구현하는 것은 쉽지 않다. 그러므로 구현할 때 Compress tree가 경로의 순서를 유지하지 않을 수 있다고 생각한다. (왼쪽 서브트리와 오른쪽 서브트리가 자유롭게 바뀔 수 있다.) 두 서브트리를 바꾸더라도 circular order는 유지된다.

 

1. 앞으로 '노드/클러스터의 끝점' 이라는 표현을 사용할 것인데, 이는 그 클러스터를 루트로 하는 Compress tree가 압축한 경로의 끝점을 의미한다.

 

Handle

Top tree는 간선을 관리하는 자료이기 때문에, 정점 표현을 지원하지 않는다. 하지만 Top tree의 연산들(Expose, Link, Cut)은 정점에 대한 연산이기 때문에 정점 표현이 가능해야 한다.

 

정점 표현을 지원하기 위해서 정점 $v$를 대신할 노드인 Handle $N_v$를 정의한다. $v$가 리프 노드가 아니라면 $N_v$는 $Compress(v)$를 나타내는 노드로 정의하면 된다. $v$가 리프일 경우에는 $v$를 직접적으로 표현할 노드가 없다. 대신에, $v$를 끝점으로 가지는 가장 높은 non-rake 노드로 Handle을 정의한다. ($N_v$는 Compress tree의 루트이거나 base cluster일 것이다.) 연결된 간선이 없는 노드는 Handle이 없다.

 

Splay

Top tree의 효율성을 보장하기 위해 Top tree의 높이를 최대한 낮게 유지해야 한다. 이 글에서는 Splay를 통해 트리의 높이를 $AmortizedO(logN)$로 보장하는 방법을 설명한다. (증명은 하지 않는다.) 여기서의 Splay는 노드를 전체 Top tree의 루트로 만드는 것이 아니라, 그 노드가 포함된 Compress/Rake tree의 루트로 만드는 연산이다. 이를 Compress/Rake tree의 루트의 부모를 guard로 하는 guarded splay라고 한다.

Splay에서의 Rotate 연산

기본적으로 Splay tree에서 하는 일반적인 Splay와 큰 차이는 없다. Compress 노드를 Rotate할 때 foster child를 어떻게 바꿔야 할 지 헷갈릴 수 있는데, 사실 바꿀 필요가 없다. 원래 트리의 구조가 바뀌지 않기 때문에 각 노드의 foster child는 바뀌지 않는다.

 

Splay 연산을 올바르게 적용하기 위해서는 Top tree가 '올바른 순서'를 가지고 있어야 한다. Compress tree가 경로의 순서를 유지하지 않으므로 Splay를 하기 전에 이 순서를 조정해줄(rectify) 필요가 있다.

 

오른쪽으로 갈수록 루트 정점에 가까워지도록 Compress tree의 순서를 조정하는 방법을 생각하자. (왼쪽이여도 상관없다.) 노드 $v$를 splay할 때, 순서의 조정은 $v$가 포함된 Compress tree의 루트부터 시작하여 $v$까지 Top-down 방식으로 진행된다. 현재 탐색하는 노드를 $N_x$라 하면, $N_x$의 두 자식의 순서가 올바르지 않을 경우 두 자식을 바꾼다. (proper child와 foster child 모두 바꿔야 한다.) 순서가 올바름을 판별하는 방법은 다음과 같다.

 

• $N_x$가 Compress tree의 루트가 아닐 경우 : $N_x$의 부모를 $N_y$, $N_x$의 오른쪽 proper child을 $R$이라 하자. $R$의 양 끝 정점이 $x$, $y$일 경우 순서가 올바르다.
• $N_x$가 Compress tree의 루트일 경우 : $N_x$의 오른쪽 proper child을 $R$이라 하자. $R$의 $x$가 아닌 끝 정점이 리프가 아닐 경우 순서가 올바르다.
• $N_x$가 전체 Top tree의 루트일 경우 : 두 자식을 바꿔도, 바꾸지 않아도 된다. 두 자식을 바꾼다면 루트 정점이 바뀌게 된다.

위 방법을 사용하기 위해서는 Compress 노드가 관리하는 경로의 양 끝 정점을 알아야 한다. 이는 두 proper child의 정보를 통해 쉽게 알 수 있다.

 

Splice

link/cut tree에서는 access 연산을 통해 어떤 정점이 포함된 경로를 루트 경로로 만든다. Top tree에서는 splice 연산을 통해 이를 수행한다.

$y$를 splice하여 루트에 가까운 경로와 연결한다.

splice 연산은 트리의 경로 파티션을 바꾼다. $y$가 포함된 경로를 $P_y$라고 하자. 위 그림에서 $splice(y)$를 수행하면 경로를 $x\dots v$와 $v\dots z$로 나누어 둘 중 루트와 가까운 경로를 $P_y$와 연결한다. 이 연산을 $y$가 루트 정점과 이어질 때까지 반복해서 수행하여 $P_y$를 루트 경로로 만들 수 있다.

실제 Top Tree에서 $splice(y)$를 수행하는 방법을 생각하자. splice 연산을 수행할 때 $N_v$는 compress tree의 루트이며, $N_v$와 $vy$ 사이에는 최대 2개의 rake 노드가 있어야 한다. (이에 대해서는 나중에 설명한다.) $vx$가 $vy$로 대체되어야 하므로 $N_v$의 왼쪽 proper child가 $vy$로 대체되어야 한다. 중요한 점은 정점 $v$의 circular order는 유지되어야 한다. 즉, $vx$가 $vy$로 대체되어도 $A-vx-B-vy-C-vz$의 순서가 지켜져야 한다. 이 순서를 지키면서 rake tree를 잘 수정하면 된다.

 

이 그림은 splice의 가능한 case중 하나일 뿐이다. 모든 case에서 $N_v$의 왼쪽 proper child를 대체하는 것은 동일하지만(rectify 과정에서 오른쪽 자식을 루트에 가까운 정점으로 했을 경우), $N_v$와 $vy$ 사이의 노드의 개수와 방향에 따라 rake tree의 구성 방법이 달라진다. case가 꽤 많으므로 실수하지 않도록 주의하자.

splice의 예 [1]

splice의 예 [2]

 

Soft Expose

Expose는 Top tree에서 특정 경로 $v\dots w$를 추출하는 연산이다. $soft\mathrm{\_}expose(v,w)$는 경로 $v\dots w$가 Top tree의 루트에 최대한 가까이 있게 만든다. 이 연산은 $N_w$를 Top tree의 루트로 만들고, $N_v$를 루트에 최대한 가깝게 올리는 방식으로 진행된다.

처음으로 $N_w$를 Top tree의 루트로 만들어야 한다. 루트로 만드는 과정은 다음 3단계로 진행된다.

 

1. Local Splay : $N_w$부터 루트까지의 Compress/Rake tree들을 splay한다.
2. Splice : $N_w$부터 루트까지의 경로에 여러번의 splice 연산을 수행하여 $N_w$가 가장 위의 Compress tree에 포함되게 만든다. (루트 경로에 포함되게 만든다.)
3. Global Splay : $N_w$를 splay해 전체 Top tree의 루트로 만든다.

1번 과정을 더 자세히 설명하면 다음과 같다.

 

• 현재 탐색하고 있는 Top tree의 노드를 $N$이라 하자. (초기에는 $N=N_w$)
• $N$을 splay하여 $N$이 포함된 Compress tree의 루트로 만든다.
• $N$이 Top tree의 루트라면 과정이 종료되고, 아니라면 $N$은 어떤 Rake tree의 리프가 된다.
• $N$의 부모가 Rake 노드일 경우 :
  • $N$의 부모를 $P$를 splay한다.
  • splay 후 $N$의 부모가 $P$가 아니라면, $P$를 guard로 하여 $N$의 새 부모 $P\prime$을 splay한다.
• $N$을 $N$에 가장 가까운 조상 Compress 노드로 바꾸고 과정을 반복한다.

이 과정 이후 $N_w$부터 루트까지의 Compress 노드들은 모두 Compress tree의 루트가 되며, Rake 노드들은 연속으로 3번 이상 등장하지 않는다.${}^2$ 따라서 $N_w$가 루트 경로에 연결될 때까지 splice 연산을 반복적으로 적용해 줄 수 있다. 그리고 모든 과정에서 올바른 순서가 필요하므로 루트부터 $N_w$까지 순서를 맞춰주고 시작하자.

 

이제 $N_v$를 $N_w$ 근처로 옮겨야 한다. 이 과정은 몇가지 case로 나뉜다.

 

• $N_v=N_w$ : $N_v$가 $N_w$이므로 해야 할 것이 없다.
• $N_v\ne N_w$ :
  • $w$가 리프 : $N_v$에 $N_w$에 했던 것과 동일한 루팅 과정을 수행한다. 이 때 $w$가 루트 정점이여야 한다. 이 경우 $N_v$가 루트가 된다.
  • $w$가 리프가 아님 : $N_v$에 $N_w$에 했던 것과 동일한 루팅 과정을 수행하지만, 모든 splay 과정을 $N_w$를 guard로 하는 guarded splay로 수행한다.

마지막으로, 구현의 단순화를 위해 경로 $v\dots w$를 나타내는 클러스터가 오른쪽에 위치하도록 조정한다. $N_v$와 $N_w$가 다르다면 $N_v$가 $N_w$의 오른쪽 자식($N_v$가 루트라면 반대)이여야 한다. $v\dots w$를 나타내는 클러스터가 $N_v$도 $N_w$도 아니라면, 그 클러스터는 $N_v$(또는 $N_w$)의 오른쪽 자식이여야 한다.

 

 

2. $N$은 BST의 순서 상 $P$ 바로 옆에 위치한다. 따라서 $P$를 splay 하면, $N$은 $P\to left\to right\to right\dots$ 또는 $P\to right\to left\to left\dots$ 에 위치한다. 두 경우 모두 $P\prime$을 splay 하더라도 $N$의 부모는 $P\prime$으로 유지된다. 그러므로 $N$의 Rake tree 안의 조상은 $P,P\prime$ 2개 뿐이다.

 

Cut

Cut 연산은 원래 트리에서 간선 하나를 제거하는 연산이다. 제거할 간선을 $(v,w)$라 하자.

먼저 $soft\mathrm{\_}expose(v,w)$를 호출하면 간선 $(v,w)$를 추출할 수 있다.

위 그림은 가장 일반적인 경우($vw$의 조부모가 루트)를 보여준다. 위 경우 $N_w$와 $N_v$의 연결을 끊고 $vw$를 삭제해야 한다. 삭제 후에 $N_v$와 $N_w$의 오른쪽 proper child가 없어지게 된다. 이를 circular order 상에서 인접한 클러스터 (왼쪽 rake tree에서 가장 왼쪽 클러스터, 오른쪽 rake tree에서 가장 오른쪽 클러스터)로 대체하면 된다. 만약 두 foster child가 모두 비어 있어 대체할 클러스터가 없는 경우, 그 노드는 삭제되고 왼쪽 proper child가 새 루트가 된다.

 

$vw$의 부모가 루트이거나 $vw$ 자체가 루트인 경우도 있을 수 있지만, 위의 방법을 이해했다면 어렵지 않게 처리할 수 있다.

Link

Link 연산은 포레스트에 간선 하나을 추가하는 연산이다. 추가할 간선을 $(v,w)$라 하자. 기본적으로 Link 연산은 Cut 연산의 진행 과정을 반대로 적용한다.

$v$와 $w$의 차수가 모두 2 이상일 경우를 보자. 먼저 $N_v$와 $N_w$를 각각 Top tree의 루트로 만든다. 그 다음 $N_v$의 오른쪽 proper child를 $vw$로 대체하고, $N_w$의 오른쪽 proper child를 $N_v$로 대체한다. 이 때 원래의 proper child는 circular order를 유지하며 한 쪽의 rake tree로 들어간다.

 

$v$, $w$의 차수가 0, 1일 때도 비슷한 과정을 수행한다. 단, 차수가 1일 경우 그 handle의 오른쪽 proper child를 그냥 대체할 수 없다. 예를 들어, $v$의 차수가 1이고 $vw$를 $N_v$에 추가하는 경우를 생각하자. 이 경우 $N_v$와 $vw$를 proper child으로 가지는 새 Compress 노드를 만들면 된다. 그러면 이 노드는 $Compress(v)$를 나타내는 노드가 된다. 당연히, $w$의 차수가 1일 때도 새 Compress 노드를 만들어서 처리하면 된다.

 

Lazy Propagation

Top tree에서도 Lazy Propagation이 가능하다. Compress tree가 경로를 관리하고, Rake tree가 나머지 서브트리를 관리한다. 따라서 경로에 Lazy를 전파하고 싶을 때는 proper child에만 전파하고, 서브트리에 Lazy를 전파하고 싶을 때는 proper child와 foster child에 모두 전파하면 된다. 어떤 노드에 접근할 때 조상들의 Lazy가 모두 전파되었는지 확인하자. 

 

 

응용

여기까지 Top tree의 모든 기본 연산들을 살펴보았다. 이제 실제로 Top tree를 사용하여 풀 수 있는 문제들을 살펴보자. 아래 문제들은 모두 간선의 추가, 제거 쿼리가 있는 포레스트에서 해결한다고 생각한다.

 

 

문제. 두 정점 $u,v$가 주어질 때, 경로 $u\dots v$에 있는 간선들의 가중치 합을 출력하라.

 

각 노드마다 경로의 합 $S(N)$을 관리한다. $S(N)$은 두 proper child의 $S$값에서 계산할 수 있다. 쿼리를 처리할 때는 $u\dots v$를 expose해서 그 노드의 $S$값을 출력하면 된다. 

 

 

문제. 두 정점 $u,v$가 주어질 때, 경로 $u\dots v$에 있는 정점들의 가중치 합을 출력하라.

 

Top tree는 간선을 관리하기 때문에, 정점 쿼리를 지원하기 위해서는 따로 처리를 해주어야 한다. 이는 구현에 따라 다양한 방법이 있을 수 있다. 여기서는 정점 쿼리를 위한 두 가지 방법을 소개한다.

 

방법 1.

모든 정점에 더미 정점 하나를 연결해 준다. 이러면 원래 있던 정점의 Handle은 모두 Compress 노드가 된다. 그 Compress 노드에 정점 정보를 저장해 주면 된다. 경로 쿼리가 들어올 때는 $u$와 $v$에 붙어 있는 더미 정점들을 expose해주자.

 

방법 2.

각 노드마다 경로에 있는 정점의 가중치 합 $S(N)$을 관리한다. $N_v$의 값을 update할 때, $S(N_v)=S(N_v\to LeftProper)+S(N_v\to RightProper)-Weight(v)$ 와 같은 방식으로 계산해주면 된다. 쿼리의 처리는 간선 쿼리때와 동일하게 $u\dots v$를 expose해서 그 노드의 $S$값을 출력하면 된다. $u=v$일 때는 그냥 $Weight(u)$를 출력하자.

 

2번째 방법이 더 효율적이긴 하나, 문제에 따라 적용하기 어려울 수 있다. 물론 이 두 방법만 있는 것은 아니므로 문제에 따라 잘 생각해서 처리하자.

 

 

문제. 쿼리마다 포레스트의 간선 $(v,p)$가 주어진다. $p$가 $v$의 부모라고 가정했을 때, $v$의 서브트리의 정점에 특정 값 $x$를 더하는 연산 또는 $v$의 서브트리의 정점 가중치 합 쿼리를 수행하라. 

(Dynamic Tree Subtree Add Subtree Sum)

 

이 문제를 해결하기 위해서는 특정 서브트리를 추출해야 한다. 먼저 $expose(v,p)$를 호출하여 $N_p$가 $N_v$의 오른쪽 proper child가 되게 하자. 이러면 $v$의 서브트리가 아닌 정점들이 Top tree에서 $N_p$의 서브트리에 모이게 된다. ($N_v$가 리프일 때에는 예외처리 해주자.) 따라서 $N_p$를 제외하고 $N_v$에서 쿼리를 처리해 주면 된다.

 

서브트리에 특정 값을 더하는 연산의 경우 Lazy Propagation이 필요해진다. 위에서 설명했듯이 proper child와 foster child에 모두 Lazy를 전파해주자.

 

 

문제. 트리의 지름의 길이를 출력하라.

 

각 노드마다 경로의 길이, 지름의 길이, 양 끝점에서 가장 먼 정점과의 거리를 관리한다. Rake 노드의 경우, 가장 가까운 조상 Compress 노드를 $N_v$라 할 때 $v$에서 가장 먼 정점까지의 거리를 관리한다.

 

Rake와 Compress 노드 모두 자식 클러스터가 공유하는 정점이 딱 하나 존재하므로 자식 노드에서 고려되지 않은 경로는 이 정점을 지나는 경로밖에 없다. 이 정점을 지나는 가장 긴 경로는 자식들의 값들을 통해 계산할 수 있다. 이제 각 클러스터의 지름을 구할 수 있으므로, 루트 노드의 지름을 출력하면 된다. 자세한 상태전이 식은 생략한다.

 

 

문제. 트리의 1-median을 구하라.

(트리와 쿼리 20)

 

트리의 1-median이란, $\sum _{v\in V}weight(v)\times dist(v,w)$를 최소화하는 정점 $w$를 말한다. 1-median은 단순히 자식 노드의 값들에서 계산할 수 없다. 이런 Non-local 한 값을 계산하기 위해서는 Top tree를 직접 탐색해야 한다. 먼저, 다음과 같은 Lemma가 성립한다.

 

Lemma. 트리 $T$의 1-median을 $m$, 루트 클러스터의 두 자식 클러스터를 $A,B$, 클러스터 $N$의 정점들의 가중치 합을 $W(N)$이라 하자. 이 때 $W(A)\ge W(B)\to m\in A$ 가 성립한다.

 

이 Lemma를 이용해서, 루트 노드의 두 자식 클러스터중에 어느 쪽에 1-median이 있는지 알 수 있다. 그러므로 Top tree에서 이분 탐색을 하듯이 탐색해나갈 수 있다. 하지만 이 Lemma는 루트 클러스터에서만 적용되므로, 루트 노드 이외의 노드에서는 두 자식만 봐서는 Lemma를 적용할 수 없다. 클러스터는 외부와 연결된 정점이 2개 이하이므로, 그 정점들과 연결된 외부 서브트리의 $W$ 값을 계산하며 트리를 탐색하면 전체 트리에 대해서 두 자식을 비교할 수 있다.

탐색 방법의 설명. 빨간색으로 둘러싸인 부분이 현재 탐색하는 클러스터이다.

트리와 쿼리 20 에서는 $\sum _{v\in V}weight(v)\times dist(v,w)$의 값까지 구해야 한다. 지름을 구할 때와 비슷하게 경로의 양 끝점을 $w$로 할 때의 식의 값을 관리하면 된다.

 

(wikipedia랑 구사과님의 블로그에는 Top tree를 직접 수정하는 방식으로 Non-local search가 설명되어 있는데, 사실 수정하는 방법을 잘 모르겠다..)

 

참고 자료

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9754&rep=rep1&type=pdf 

http://www.secmem.org/blog/2021/03/21/toptree/

https://di.ku.dk/forskning/Publikationer/tekniske_rapporter/tekniske-rapporter-1998/98-17.pdf

https://en.wikipedia.org/wiki/Top_tree