[Link Cut Tree] 3. 연산 (2)

이번 글에서는 트리에서 루트나 부모를 구하는 방법, 노드의 깊이를 구하는 방법을 알아보겠습니다.

node * findRoot(node * x) {
    access(x);
    while (x->l) x = x->l;
    splay(x);
    return x;
}

FindRoot 연산은 x가 포함된 트리의 루트를 반환하는 연산입니다.

일단 x에 access하고, Splay Tree에서 가장 깊이가 작은 노드가 루트가 됩니다.

따라서 x에서 왼쪽으로 계속 이동할 수 없을 때까지 이동해주면 루트를 찾을 수 있습니다.

amortized log n 시간복잡도를 보장하기 위해서 찾은 루트를 splay해줍니다.

node * parent(node * x) {
    access(x);
    x = x->l;
    if (!x) return 0;
    while (x->r) x = x->r;
    splay(x);
    return x;
}

Parent 연산은 노드의 부모 노드를 찾습니다.

x에 access하고, Splay Tree에서 x의 왼쪽 자식들 중에 가장 오른쪽에 있는 노드가 x의 부모 노드가 됩니다.

x에게 왼쪽 자식이 없다면 x가 트리의 루트인 것으로, NULL을 반환합니다.

x에세 왼쪽 자식이 있다면 왼쪽으로 이동한 뒤, 오른쪽으로 이동할 수 없을 때까지 오른쪽으로 이동하면 x의 부모 노드가 됩니다.

FindRoot 연산에서처럼 시간복잡도를 보장하기 위해 찾은 노드를 splay해준 후 반환합니다.

int depth(node * x) {
    access(x);
    if (x->l) return x->l->cnt;
    return 0;
}

Depth 연산은 노드의 깊이를 구하는 연산입니다. (루트의 깊이를 0으로 정의)

x의 조상 노드의 개수가 x의 깊이와 같으므로, x에 access한 뒤 x의 왼쪽 자식들의 개수를 세어 주면 됩니다.