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 log n)이다.

r(v) = log2 s(v)로 정의한다. 여기서 s(v)는 표현 트리에서 v의 서브트리 크기이며 s(v) ≥ 1이므로 0 ≤ r(v) ≤ log n이다. preferred/dashed 재분류는 s(v)에 영향을 주지 않으므로 선호 경로 전환은 포텐셜을 바꾸지 않는다.

포텐셜을 Φ = ∑v r(v)로 정의한다. 0 ≤ Φ ≤ n log 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

가중치 s(v)를 사용하는 보조 스플레이 트리에서 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) ≤ log n.

패스 3의 splay 전 루트를 t'라 하면 q(v) + ΔΦ ≤ 3(r(t') − r(v)) ≤ 3 log n이다.

j번째 access에 대해 두 부분을 더하면 q의 합 + ΔΦj ≤ 6 log n이다. m번 합산하면

M + Φm − Φ0 ≤ 6m log n.

Φ0 ≤ n log n, Φm ≥ 0이므로 M ≤ 6m log n + n log n이다.

j번째 access의 총 splay 수는 kj + 1이고 각 splay에 zig가 최대 1번이므로

∑j cost(accessj) ≤ M + ∑j (kj + 1) = M + ∑j kj + m.

패스 2 이후 v는 x1, ⋯, xkj를 조상으로 하는 경로의 오른쪽 맨 아래에 있으므로 패스 3의 실제 회전 수 ρj = kj이다. ρj ≤ q(vj) + 1이므로 ∑j kj = ∑j ρj ≤ M + m.

따라서 ∑j cost(accessj) ≤ 2M + 2m ≤ 12m log n + 2n log n + 2m = 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 1회와 O(1) 포인터 조작으로 구성된다. 포인터 연결로 u가 v의 서브트리에 편입되어 r(v)가 최대 log n 증가하므로 분할 상환 O(log n)이다.

void link(Node *u, Node *v) {
    access(u);
    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.