알고리즘 대회에서 흔히 사용하는 기본적인 이진 탐색 트리나 세그먼트 트리만으로는 해결하기 어려운 문제들이 존재한다. 구간의 반전이 빈번하게 일어나거나, 다차원 공간에서 최근접 을 찾아야 하며, 트리의 간선이 동적으로 연결되고 끊어지는 상황을 다루어야 할 때가 그렇다. 이번 글에서는 이러한 고난이도 문제를 해결하는 세 가지 핵심 자료구조인 Splay 트리, K-D 트리, 그리고 LCT(Link-Cut Tree)를 심도 있게 다룬다.

Splay 트리: 회전을 통한 자기 조정형 트리

Splay 트리는 AVL 트리나 Treap과 달리 명시적인 균형 인자나 우선순위를 사용하지 않는다. 대신 최근에 접근한 노드를 루트로 이동시키는 방식으로 트리의 형태를 동적으로 조정한다. 이는 데이터 접근의 지역성을 활용한 설계 철학에 기반한다.

이중 회전 메커니즘

단순히 부모와의 회전을 반복하면 체인 형태의 트리에서 성능이 저하될 수 있다. Splay 트리는 이중 회전을 통해 이 문제를 해결한다. 현재 노드를 cur, 부모를 par, 조상을 anc라 할 때:

• 직선 회전 (Zig-Zig): cur, par, anc가 한 방향으로 정렬된 경우. 부모를 먼저 회전한 후 현재 노드를 회전한다.
• 꺾인 회전 (Zig-Zag): cur가 par의 왼쪽 자식이고 par가 anc의 오른쪽 자식인 등 방향이 다른 경우. 현재 노드를 연속으로 두 번 회전한다.

구간 조작의 핵심

Splay 트리의 강점은 물리적인 구간 분리와 병합이다. [L, R] 구간을 조작하려면:

1. 순위가 L-1인 노드를 루트로 Splay
2. 순위가 R+1인 노드를 루트의 오른쪽 자식으로 Splay
3. 이때 루트의 오른쪽 자식의 왼쪽 서브트리가 정확히 [L, R] 구간을 구성한다

이 서브트리를 직접 분리하거나 게으른 전파 태그를 적용할 수 있다.

void adjust(int node, int targetParent) {
    if (targetParent == 0) root = node;
    while (true) {
        int par = tree[node].parent;
        int grand = tree[par].parent;
        if (par == targetParent) break;
        if (grand != targetParent) {
            if (getDirection(node) == getDirection(par))
                rotateNode(par);
            else
                rotateNode(node);
        }
        rotateNode(node);
    }
    refresh(node);
}

K-D 트리: 다차원 공간의 효율적 탐색

평면 상의 수십만 개의 점이 주어지고, 임의의 점에 대해 가장 가까운 점을 반복적으로 질의할 때, K-D 트리는 필수적인 도구다.

공간 분할 전

K-D 트리는 차원을 순환하며 중앙값을 기준으로 공간을 분할한다:

• 깊이 0: x좌표 중앙값으로 수직 분할
• 깊이 1: y좌표 중앙값으로 수평 분할
• 깊이 2: 다시 x좌표로 분할...

각 노드는 점 정보와 함께 해당 서브트리가 차지하는 축 정렬 직사각형 영역을 표현한다.

최근접 이웃 탐색과 가지치기

쿼리 점 q에 대한 최근접 이웃 탐색 과정:

1. 현재까지 찾은 최소 거리 best를 유지
2. 재귀적으로 더 가까워질 가능성이 있는 자식을 우선 탐색
3. 다른 자식의 영역이 q를 중심으로 best 반경의 원과 교차하지 않으면 해당 서브트리 전체를 제외

이 가지치기는 평균적으로 O(log n)의 탐색 복잡도를 가능하게 한다. 동적 삽입/삭제가 빈번하면 재구축 기법(Scapegoat Tree 방식)을 적용하여 균형을 유지한다.

LCT: 동적 연결성을 다루는 최종 도구

Link-Cut Tree는 트리의 구조가 실행 중에 변하는 상황—간선의 추가(link)와 제거(cut)—를 처리하며 경로 쿼리를 지원한다.

이중 표현: 원본 트리와 보조 트리

LCT는 두 개의 계층으로 트리를 관리한다:

• 원본 트리: 문제에서 정의된 실제 트리 구조
• 보조 트리들: 각각이 Splay 트리로, 원본의 "실체인 경로"를 표현

원본의 간선은 두 종류로 분류된다:

• 실체인 간선: 각 노드는 최대 하나의 실체인 자식과 연결. 실체인 간선들로 형성된 경로를 실체인이라 한다.
• 가상 간선: 나머지 모든 간선. 자식은 부모를 인식하나 부모의 자식 포인터에는 존재하지 않는 일방향 관계.

보조 트리의 중위 순회 순서는 원본 트리에서의 깊이 순서와 정확히 일치한다.

핵심 연산: access

access(v)는 루트에서 v까지의 경로를 단일 실체인으로 변환한다:

1. v에서 시작해 가상 부모를 따라 상승
2. 방문하는 각 노드를 해당 보조 트리의 루트로 Splay
3. 오른쪽 자식을 이전 단계의 실체인으로 대체 (가상→실체 전환)
4. 정보 갱신

동적 루트 변경: makeRoot

문제에 고정된 루트가 없을 때 makeRoot(v)로 임의의 노드를 루트로 지정할 수 있다:

1. access(v) 실행: v는 현재 실체인의 최하위(최대 깊이) 위치
2. splay(v): v를 보조 트리의 트로, 오른쪽 자식은 없음
3. reverse(v): 뒤집기 태그 적용. 깊이 관계가 역전되어 v가 최상위(루트)가 됨

동적 연결 조작

void connect(int a, int b) {
    makeRoot(a);
    if (findRoot(b) != a)
        tree[a].parent = b;
}

void disconnect(int a, int b) {
    makeRoot(a);
    access(b);
    splay(b);
    if (tree[b].left == a && !tree[a].right) {
        tree[b].left = tree[a].parent = 0;
        pullUp(b);
    }
}

여기서 findRoot는 access 후 왼쪽으로 계속 이동하며 가장 깊은 노드를 찾는 방식으로 구현된다.

세 자료구조의 적용 범위

자료구조	핵심 메커니즘	대표적 활용
Splay	회전 기반 자기 조정	동적 구간 반전, 텍스트 에디터
K-D 트리	공간 분할 + 기하학적 가지치기	최근접 이웃, 범위 검색
LCT	실체인/가상 간선 분리 + Splay 복합	동적 그래프 연결성, 네트워크 플로우

이 세 자료구조를 자유자재로 구현할 수 있다면, 복잡한 동적 집합 문제와 기하학적 질의, 변화하는 토폴로지를 다루는 능력이 크게 향상될 것이다.