Python으로 Link/Cut Tree 직접 구현하기 (기초 버전)

앞서 소개한 **Link/Cut Tree (LCT)**는 동적 트리를 위한 강력한 도구지만,
직접 구현해보려면 Splay Tree, Lazy Propagation, 경로 관리 등
복잡한 요소를 잘게 나누어 학습하고 구현해야 합니다.

이번 글에서는 기본 LCT의 핵심 기능인
access, make_root, link, cut, connected, find_root를
Python으로 최소한의 형태로 구현합니다.

🧱 기본 구조 설명

📌 전제: 각 트리 노드는 Splay Tree 노드로 동작

class Node:
    def __init__(self, id):
        self.id = id
        self.left = None
        self.right = None
        self.parent = None
        self.reversed = False

🔁 기본 연산 구현

🔄 1. is_root(x)

현재 노드가 Splay Tree의 루트인지 확인:

def is_root(x):
    return not x.parent or (x.parent.left != x and x.parent.right != x)

🔁 2. rotate(x)

Splay Tree에서 회전 연산:

def rotate(x):
    p = x.parent
    g = p.parent
    if p.left == x:
        p.left = x.right
        if x.right:
            x.right.parent = p
        x.right = p
    else:
        p.right = x.left
        if x.left:
            x.left.parent = p
        x.left = p
    p.parent = x
    x.parent = g
    if g:
        if g.left == p:
            g.left = x
        elif g.right == p:
            g.right = x

🔁 3. splay(x)

최상단으로 노드 이동:

def splay(x):
    while not is_root(x):
        p = x.parent
        g = p.parent
        if not is_root(p):
            if (p.left == x) == (g.left == p):
                rotate(p)
            else:
                rotate(x)
        rotate(x)

🔨 핵심 LCT 연산

1. access(x)

루트로부터 x까지 경로 노출:

def access(x):
    last = None
    y = x
    while y:
        splay(y)
        y.right = last
        last = y
        y = y.parent
    splay(x)

2. make_root(x)

x를 트리의 루트로 만듦:

def make_root(x):
    access(x)
    x.reversed ^= True

3. link(u, v)

두 노드를 연결:

def link(u, v):
    make_root(u)
    u.parent = v

4. cut(u, v)

u와 v 사이 간선을 자름:

def cut(u, v):
    make_root(u)
    access(v)
    if v.left == u:
        v.left.parent = None
        v.left = None

5. connected(u, v)

두 노드가 같은 트리에 속하는지 확인:

def connected(u, v):
    make_root(u)
    access(v)
    return find_root(u) == find_root(v)

6. find_root(x)

x가 속한 트리의 루트 찾기:

def find_root(x):
    access(x)
    while x.left:
        x = x.left
    splay(x)
    return x

✅ 예제 실행

# 노드 초기화
nodes = [Node(i) for i in range(5)]

link(nodes[0], nodes[1])
link(nodes[1], nodes[2])

print(connected(nodes[0], nodes[2]))  # True
cut(nodes[1], nodes[2])
print(connected(nodes[0], nodes[2]))  # False

✨ 마무리

이번 글에서는 LCT의 가장 기본적인 형태를 구현했습니다.
다음 글에서는 이 LCT 구조에 경로 합 / 최댓값 augmentation,
Lazy Propagation, 그리고 MST 유지 구조 등을 추가해 나갑니다.

LinkCutTree구현, PythonLCT, 동적트리, 트리간선제어, SplayTree기반, LCT최소코드, 알고리즘자료구조, 파이썬트리알고리즘, 경로압축, SEO 최적화 10개