Splay Tree 기반 Euler Tour Tree: 최적의 Self-Balancing 동적 트리 구조 완전 정복

이번 글에서는 Splay Tree 기반 Euler Tour Tree (ETT) 구현법을 소개합니다.
이는 간선 삽입/삭제, 노드 재배치, 서브트리 쿼리 등
모든 연산을 **Amortized O(log N)**으로 처리할 수 있는
최고 수준의 트리 기반 동적 연결 자료구조입니다.

Splay Tree는 Self-Adjusting 특성을 갖는 BST로,
최근에 접근한 노드를 루트로 끌어올려 캐시 효과를 극대화합니다.
이는 ETT와 결합될 때 LCT(Link/Cut Tree)의 핵심 구조로도 활용됩니다.

✅ 목표 기능

기능 시간 복잡도 (Amortized)

link(u, v)	O(log N)
cut(u, v)	O(log N)
connected(u, v)	O(log N)
subtree_sum(u)	O(log N)
evert(u)	O(log N)

🧠 구조 설계 개요

오일러 투어 순회를 Splay Tree의 중위 순서로 저장
각 노드에 대해 진입 노드(entry) 와 **이탈 노드(exit)**를 Splay Tree 노드로 생성
Treap 기반 ETT보다 성능 일관성이 좋고 메모리 활용이 예측 가능

🔧 핵심 연산: Splay, Rotate, Merge, Split

class SplayNode:
    def __init__(self, value):
        self.value = value
        self.parent = None
        self.left = None
        self.right = None
        self.size = 1
        self.sum = value

def update(node):
    if node:
        node.size = 1
        node.sum = node.value
        if node.left:
            node.left.parent = node
            node.size += node.left.size
            node.sum += node.left.sum
        if node.right:
            node.right.parent = node
            node.size += node.right.size
            node.sum += node.right.sum

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

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

🛠 ETT 동작 흐름

1. 오일러 투어 트리 구성

각 노드에 대해 entry[u], exit[u] 두 개의 SplayNode를 생성하여
Splay Tree 상에 삽입.
→ 중위 순회 순서가 오일러 투어 순서와 같게 구성

2. Link(u, v)

evert(u) → make_root(u)
link(u, v) → 두 트리의 루트를 merge

3. Cut(u, v)

evert(u)
expose(v)
cut → 두 트리로 분리(split)

✅ ETT Wrapper 구조

class SplayETT:
    def __init__(self, n):
        self.n = n
        self.entry = [SplayNode(1) for _ in range(n)]
        self.exit = [SplayNode(1) for _ in range(n)]
        # Tree 노드 연결 필요 (중위 순서)

    def make_root(self, u):
        # evert(u) = u를 루트로 만듦
        pass

    def link(self, u, v):
        self.make_root(u)
        self.make_root(v)
        # merge(entry[u], entry[v])

    def cut(self, u, v):
        self.make_root(u)
        # split and disconnect

    def connected(self, u, v):
        return self.find_root(u) == self.find_root(v)

    def find_root(self, u):
        node = self.entry[u]
        while node.parent:
            node = node.parent
        return node

📌 Splay Tree 기반 ETT의 장점

장점 설명

Self-adjusting 구조	최근 접근 노드를 루트로 끌어올려 캐시 최적화
메모리 균형	Treap보다 메모리 예측이 쉬움
Link/Cut Tree 기반 가능	Splay 기반으로 LCT 구현 가능 (다음 글 내용)

📘 실전 문제 예시

문제 설명

Codeforces 613E	Splay 기반 ETT 구현의 대표 문제
ARC 123E	동적 그래프에서의 연결성 유지 문제
Library Contest	LCT와 ETT를 비교하는 경우 자주 등장

✅ 결론 및 요약

Splay Tree 기반 ETT는 이론적으로 가장 강력한 동적 트리 자료구조 중 하나
**모든 연산을 O(log N)**으로 처리 가능하며,
LCT의 핵심 구성 요소로 활용 가능
트리 쿼리, 연결성 판단, 구조 변경까지 모두 고성능 처리

👉 다음 글에서는 **Splay Tree 기반 Link/Cut Tree(LCT)**의 전체 구현을 정리하고
경로 쿼리 / 간선 교체 / 최댓값 유지 등의 응용을 소개합니다.

📚 참고자료

Sleator & Tarjan (1983) – Self-adjusting BSTs (Splay Tree)
“Dynamic Tree Data Structures” by Tarjan
CP-Algorithms – Link/Cut Tree
Stanford CS166 – LCT via Splay

SplayTree, EulerTourTree, ETT, 동적트리, 트리연결성, 트리최적화, LinkCutTree, 파이썬알고리즘, FullyDynamicGraph, SEO 최적화 10개