Programming/알고리즘
Splay Tree 기반 Euler Tour Tree: 최적의 Self-Balancing 동적 트리 구조 완전 정복
octo54
2025. 5. 28. 11:09
반응형
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개