[Link Cut Tree] 1. 개요와 구현

Link Cut Tree(LCT)는 Forest를 관리하는 자료구조이며, 각각의 트리는 루트를 가집니다.

LCT는 이름에도 있듯 트리 두개를 연결하고(Link), 끊는(Cut) 연산을 가지고 있습니다.

LCT에서는 마치 Heavy-Light Decomposition처럼 트리를 몇 개의 Path로 나누어 관리하는데, 각각의 Path를 관리할 때 주로 Splay Tree를 사용합니다.

왼쪽 트리가 실제 표현하고자 하는 트리의 모습이고, 오른쪽 트리는 왼쪽 트리를 Link Cut Tree로 구현한 모습입니다.

실선으로 연결된 경로가 하나의 Path이고, 점선은 Path의 루트가 Path의 부모를 가리키도록 한 선입니다.

왼쪽 트리에서 (1, 2, 5, 9), (3, 7), (6, 10), (4), (8) 5개의 경로로 나뉘었는데, 각각의 경로는 깊이 순서로 Binary Search Tree가 되었고, 각 BST의 루트의 Parent 포인터는 해당 Path의 부모 노드를 가리키고 있는데, 반대 방향으로는 가리키고 있지 않습니다.

Path를 나누는 것이 HLD와 조금 다른데, HLD에서는 Heavy Path가 고정되지만, LCT에서는 Path가 동적으로 변화합니다.

LCT는 이 Path들과 Splay Tree를 이용해서 트리를 동적으로 연결하고 끊으며 다양한 연산을 하는 자료구조입니다.

struct node {
    node *l, *r, *p;
    int cnt;
    node() : l(0), r(0), p(0), cnt(0) {}
};

Link Cut Tree에서 node는 기본적으로 Splay Tree와 같으며, 자식과 부모의 포인터만이 필요합니다.

이 글에서는 노드의 Depth를 구하기 위해 Subtree의 노드 개수를 저장하는 cnt 변수를 사용하였습니다.

bool isRoot(node * x) {
    return (x->p == 0 || (x->p->l != x && x->p->r != x));
}

LCT에서는 Splay Tree의 루트의 Parent가 NULL이 아닐 수 있기 때문에 해당 노드가 Splay Tree의 루트인지 확인하는 함수를 만듭니다.

x->p가 NULL이면 당연히 x가 루트입니다.

x->p가 NULL이 아닌데 x가 x->p의 자식이 아니라면 x와 x->p는 서로 다른 Splay Tree에 속해 있는 것이고, x가 해당 Splay Tree의 루트인 것이 됩니다. 기존 Splay Tree의 구현에서 x가 루트인지 확인하는 부분을 모두 isRoot로 바꿔줍니다.

Update, Rotate, Splay 구현

void update(node * x) {
    x->cnt = 1;
    if (x->l) x->cnt += x->l->cnt;
    if (x->r) x->cnt += x->r->cnt;
}

void rotate(node * x) {
    node * p = x->p;
    if (x == p->l) {
        p->l = x->r;
        x->r = p;
        if (p->l)
            p->l->p = p;
    }
    else {
        p->r = x->l;
        x->l = p;
        if (p->r)
            p->r->p = p;
    }
    x->p = p->p;
    p->p = x;
    if (x->p) {
        if (p == x->p->l) x->p->l = x;
        else if (p == x->p->r) x->p->r = x;
    }
    update(p); update(x);
}

void splay(node * x) {
    while (!isRoot(x)) {
        node * p = x->p;
        if (!isRoot(p)) {
            if ((x == p->l) == (p == p->p->l)) rotate(p);
            else rotate(x);
        }
        rotate(x);
    }
}

위 코드들은 Splay Tree에서 사용하는 것과 같으므로 설명하지 않습니다.

node * access(node * x) {
    splay(x);
    x->r = 0;
    update(x);

    node * ret = x;
    while (x->p) {
        node * y = x->p;
        ret = y;
        splay(y);
        y->r = x;
        update(y);
        splay(x);
    }
    return ret;
}

LCT의 하이라이트(?)인 Access 연산입니다. LCT에서 많은 연산들을 처리할 때 Access를 거칩니다.

이 연산이 amortized 시간복잡도를 가지기 때문에 Link, Cut 등의 연산들이 모두 amortized 의 시간복잡도를 가지게 됩니다.

Access 연산이 하는 일은 x와 트리의 루트 사이의 경로를 하나의 Path로 연결하고, 이 Path의 Splay Tree에서 x를 루트로 만드는 연산입니다. Splay Tree의 Splay와 비슷하다고 볼 수 있습니다.

코드를 자세히 보면, 시작할 때 x를 Splay하고, x의 오른쪽 자식을 모두 떼어냅니다.

떼어진 자식들은 x보다 깊이가 큰 노드들로, 트리에서 x의 자식들을 모두 떼어낸 것입니다.

그리고 x->p가 NULL이 아니라면, x를 포함하는 Path에 부모 노드 y가 존재한다는 것을 의미합니다.

따라서 y의 오른쪽에 x를 붙여서 x가 포함된 Path를 모두 y와 같은 Path로 연결시킵니다.

이것을 x->p가 NULL일 때까지 반복하면 x와 트리의 루트가 하나의 Path로 묶이게 됩니다.

참고로 Access가 끝난 후 반환하는 값은 Access 전에 ‘루트가 포함되던 Path’에서 x와 가장 가까이 있던 노드입니다.