imeimi / Algorithm DB Link-Cut Tree
1정의
Link-Cut Tree는 rooted tree들의 포레스트를 동적으로 관리하는 자료구조다. 다음 연산을 분할 상환 O(log n)에 지원한다.
access(v): 내부 연산. v에서 루트까지의 경로를 단일 선호 경로로 정비한다.find_root(v): v가 속한 트리의 루트를 반환한다.link(u, v): u가 트리의 루트일 때, u를 v의 자식으로 연결한다.cut(v): v와 v의 부모 사이 간선을 제거한다.make_root(v): v를 v가 속한 트리의 루트로 만든다.
2자료구조
2.1선호 경로 분해
각 노드 v는 자식 중 최대 하나를 선호 자식(preferred child)으로 지정한다. 선호 간선들로 이루어진 최대 경로를 선호 경로(preferred path)라 한다. 모든 노드는 정확히 하나의 선호 경로에 속한다.
각 선호 경로는 보조 스플레이 트리(auxiliary splay tree)로 표현한다. 보조 트리 내에서 노드는 깊이(depth) 오름차순으로 정렬된다. 즉 왼쪽 서브트리가 더 얕고, 오른쪽 서브트리가 더 깊다.
2.2경로-부모 포인터
보조 트리의 루트 r은 표현 트리에서 r보다 한 단계 위 노드를 가리키는 경로-부모 포인터(path-parent pointer)를 가질 수 있다. 이 포인터는 r의 p 필드에 저장되지만, 가리키는 노드의 l, r 필드에는 r이 등록되지 않는다. 이를 통해 스플레이 트리의 부모-자식 관계와 구분한다.
노드 x가 보조 트리의 루트인지 여부는 다음으로 판별한다.
bool is_root(Node *x) {
return !x->p || (x->p->l != x && x->p->r != x);
}
3구현
노드 구조체는 스플레이 트리와 동일하다.
struct Node {
Node *p, *l, *r;
};
rotate(x)는 스플레이 트리와 거의 동일하다. 단, g가 경로-부모 포인터일 수 있으므로 g의 자식 포인터는 g->l 또는 g->r이 실제로 p인 경우에만 갱신한다.
bool is_right(Node *x) { return x->p->r == x; }
void rotate(Node *x) {
Node *p = x->p, *g = p->p;
bool right = is_right(x);
Node *inner = right ? x->l : x->r;
if (right) { x->l = p; p->r = inner; }
else { x->r = p; p->l = inner; }
if (inner) inner->p = p;
p->p = x; x->p = g;
if (g) {
if (g->l == p) g->l = x;
else if (g->r == p) g->r = x;
}
}
splay(x)는 x가 보조 트리의 루트(is_root(x))에 도달하면 멈춘다.
void splay(Node *x) {
while (!is_root(x)) {
Node *p = x->p;
if (!is_root(p)) {
if (is_right(x) == is_right(p)) rotate(p);
else rotate(x);
}
rotate(x);
}
}
access(v)는 세 패스로 동작한다.
패스 1: v에서 루트까지 경로-부모 포인터를 따라 올라가며 각 보조 트리를 스플레이하고, 오른쪽 자식(아래 방향 선호 경로)을 끊는다.
패스 2: 같은 경로를 다시 올라가며 각 노드의 오른쪽 자식을 아래 보조 트리로 연결한다.
패스 3: splay(v)로 v를 전체 보조 트리의 루트로 올린다.
void access(Node *v) {
for (Node *x = v; x; x = x->p) {
splay(x);
x->r = nullptr;
}
Node *last = nullptr;
for (Node *x = v; x; x = x->p) {
x->r = last;
last = x;
}
splay(v);
}
access(v) 후 v는 보조 트리 루트이고, v->l은 루트에서 v의 부모까지의 경로, v->r은 nullptr, v->p는 nullptr이다.
보조 트리에서 어떤 노드에 접근한 뒤에는 반드시 splay를 호출해 루트로 올려야 분할 상환 복잡도가 성립한다.
4시간 복잡도
n개의 노드로 이루어진 포레스트에서 m번의 access에 걸친 총 시간 복잡도는 O((m + n) log n)이다.
보조 트리들의 부모-자식 간선과 경로-부모 포인터를 합쳐 전체 포레스트를 하나의 트리로 본 것을 가상 트리(virtual tree)라 한다. r(v) = log2 s(v)로 정의한다. 여기서 s(v)는 가상 트리에서 v의 서브트리 크기이며 s(v) ≥ 1이므로 0 ≤ r(v) ≤ log2 n이다. access의 선호 자식 교체는 오른쪽 자식을 경로-부모 자식으로, 경로-부모 자식을 오른쪽 자식으로 바꿀 뿐 가상 트리의 포함 관계를 바꾸지 않으므로 s를 바꾸지 않는다. s가 변하는 것은 회전뿐이다.
w(v) = 1 + ∑ (v에 경로-부모 포인터로 매달린 서브트리들의 s)로 정의하면, 보조 트리에서 v의 왼쪽·오른쪽 서브트리를 A, B라 할 때 s(v) = s(A) + s(B) + w(v)이고 w(v) ≥ 1이다.
포텐셜을 Φ = ∑v r(v)로 정의한다. 0 ≤ Φ ≤ n log2 n이다.
4.1보조 정리 1
a, b ≥ 1이고 a + b ≤ c이면 log2 a + log2 b ≤ 2 log2 c − 2이다.
AM-GM에 의해 ab ≤ ((a+b)/2)2 ≤ (c/2)2. 양변에 log2를 취하면 성립한다. ■
4.2보조 정리 2
보조 스플레이 트리에서 z를 splay할 때, splay 전 트리의 루트를 t, zig를 제외한 회전 수를 q(z)라 하면
q(z) + ΔΦ ≤ 3(r(t) − r(z)).
각 단계의 분할 상환 비용 â = 실제 비용 + ΔΦ를 구한다. 이하에서 프라임(')은 단계 직후의 값이다.
zig: 회전 1회이지만 zig의 회전을 제외하므로 실제 비용 0. r이 변하는 노드는 z, p뿐이다. z가 p 자리를 차지하므로 r'(z) = r(p), r'(p) ≤ r'(z). 따라서 âzig ≤ 3[r'(z) − r(z)].
zig-zig: 회전 2회, 실제 비용 2. r'(z) = r(g)이다. WLOG z가 p의 왼쪽, p도 g의 왼쪽. zig-zig 전 z의 서브트리를 A, B, p의 오른쪽 서브트리를 C, g의 오른쪽 서브트리를 D라 하면
s(z) = s(A)+s(B)+w(z), s'(g) = s(C)+s(D)+w(g), s(g) = s(A)+s(B)+s(C)+s(D)+w(z)+w(p)+w(g).
따라서 s(z) + s'(g) = s(g) − w(p) < s(g) (w(p) > 0)이고, 보조 정리 1에 의해 r(z) + r'(g) ≤ 2r(g) − 2 = r(g) + r'(z) − 2. 따라서 [r'(g) − r(g)] ≤ [r'(z) − r(z)] − 2.
r'(p) ≤ r'(z)이고 r(p) ≥ r(z)이므로 [r'(p) − r(p)] ≤ [r'(z) − r(z)].
âzig-zig = 2 + [r'(z)−r(z)] + [r'(p)−r(p)] + [r'(g)−r(g)] ≤ 3[r'(z) − r(z)].
zig-zag: 회전 2회, 실제 비용 2. r'(z) = r(g)이다. WLOG z가 p의 오른쪽, p가 g의 왼쪽. zig-zag 전 z의 서브트리를 B, C, p의 왼쪽 서브트리를 A, g의 오른쪽 서브트리를 D라 하면
s'(p) = s(A)+s(B)+w(p), s'(g) = s(C)+s(D)+w(g), s(g) = s(A)+s(B)+s(C)+s(D)+w(z)+w(p)+w(g).
따라서 s'(p) + s'(g) = s(g) − w(z) < s(g) (w(z) > 0)이고, 보조 정리 1에 의해 r'(p) + r'(g) ≤ 2r(g) − 2 = r(g) + r'(z) − 2. 따라서 [r'(p) − r(p)] + [r'(g) − r(g)] ≤ [r'(z) − r(z)] − 2.
âzig-zag = 2 + [r'(z)−r(z)] + [r'(p)−r(p)] + [r'(g)−r(g)] ≤ 3[r'(z) − r(z)].
모두 더하면 â = q(z) + ΔΦ ≤ 3[r(t) − r(z)]가 성립한다. ■
splay 하나에 zig는 최대 한 번이므로 실제 회전 수 ≤ q(z) + 1이다.
4.3증명
m번의 access 전체에 걸친 모든 splay의 q 합을 M이라 하자. j번째 access에서 패스 1이 kj개의 보조 트리를 방문한다. i번째 보조 트리의 splay 전 루트를 ti, splay하는 노드를 xi라 하자. 보조 정리 2를 적용해 합산하면
∑i q(xi) + ΔΦ ≤ 3 ∑i (r(ti) − r(xi)).
Ti의 모든 노드는 표현 트리에서 xi+1의 서브트리에 속하므로 r(ti) < r(xi+1)이다.
∑i (r(ti) − r(xi)) ≤ r(tkj) − r(x1) ≤ log2 n.
패스 3의 splay 전 루트를 t'라 하면 q(v) + ΔΦ ≤ 3(r(t') − r(v)) ≤ 3 log2 n이다.
j번째 access에 대해 두 부분을 더하면 q의 합 + ΔΦj ≤ 6 log2 n이다. m번 합산하면
M + Φm − Φ0 ≤ 6m log2 n.
Φ0 ≤ n log2 n, Φm ≥ 0이므로 M ≤ 6m log2 n + n log2 n이다.
j번째 access의 총 splay 수는 kj + 1이고 각 splay에 zig가 최대 1번이므로
∑j cost(accessj) ≤ M + ∑j (kj + 1) = M + ∑j kj + m.
패스 2 이후 v는 x2, ⋯, xkj를 조상으로 하는 경로의 오른쪽 맨 아래에 있으므로 패스 3의 실제 회전 수 ρj = kj − 1이다. ρj ≤ q(vj) + 1이므로 ∑j kj = ∑j (ρj + 1) ≤ M + 2m.
따라서 ∑j cost(accessj) ≤ 2M + 3m ≤ 12m log2 n + 2n log2 n + 3m = O((m + n) log n).
access의 분할 상환 비용은 O(log n)이다. ■
5link와 cut의 시간 복잡도
5.1link
u가 트리의 루트일 때, link(u, v)는 u를 v의 자식으로 연결한다. u가 루트이면 access(u) 후 u->l과 u->p가 모두 nullptr이다. u->p에 경로-부모 포인터로 v를 저장하면 u가 v의 자식이 된다.
access(v)도 호출해 v를 자신의 가상 트리의 루트로 만든다. v가 가상 루트가 아니면 포인터 연결로 v의 모든 가상 조상의 s가 함께 커져 ΔΦ를 log2 n으로 막을 수 없다.
access 2회와 O(1) 포인터 조작으로 구성된다. 포인터 연결로 s가 커지는 노드는 가상 루트 v뿐이고 Δφ(v) ≤ log2 n이므로 분할 상환 O(log n)이다.
void link(Node *u, Node *v) {
access(u);
access(v);
u->p = v;
}
5.2cut
v가 루트가 아닐 때, cut(v)는 v와 v의 부모 사이 간선을 제거한다. access(v) 후 v->l은 v의 부모를 최상위로 포함하는 서브트리이고, v->l->p = v이다.
access 1회와 O(1) 포인터 조작으로 구성된다. 포인터 제거로 r(v)가 감소하므로 ΔΦ ≤ 0이고 분할 상환 O(log n)이다.
void cut(Node *v) {
access(v);
v->l->p = nullptr;
v->l = nullptr;
}
6참고 문헌
- Sleator, D. D., & Tarjan, R. E. (1983). A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3), 362–391.