Euler Tour Tree Forest 실전 구현: Segment Tree 기반 동적 연결성 유지 코드 템플릿

Euler Tour Tree Forest 실전 구현: Segment Tree 기반 동적 연결성 유지 코드 템플릿

앞선 글에서는 **ETT Forest(Euler Tour Tree Forest)**의 개념과 활용을 설명했습니다.
이번 글에서는 이를 실제로 Segment Tree 기반으로 구현하여
삽입/삭제/연결성 질의까지 **모두 O(log N)**으로 처리하는
Python 실전 코드 템플릿을 제공합니다.

---

✅ 구현 목표

기능 지원 여부 시간복잡도

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

---

🧠 구조 설계

• 오일러 투어를 DFS로 생성
• 각 노드의 진입/이탈 시간 (in/out) 기록
• 오일러 배열 위에 세그먼트 트리를 구성
• in[u]~out[u] 구간이 u의 서브트리 정보

---

🛠 Python 코드 템플릿

1. ETT 클래스: 오일러 투어 구성

class EulerTourTree:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.euler = []
        self.in_time = [0] * n
        self.out_time = [0] * n
        self.time = 0
        self.values = [1] * n  # 예: 노드 값이 1 (서브트리 크기용)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def dfs(self, u, parent):
        self.in_time[u] = self.time
        self.euler.append(u)
        self.time += 1
        for v in self.graph[u]:
            if v != parent:
                self.dfs(v, u)
                self.euler.append(u)
                self.time += 1
        self.out_time[u] = self.time - 1

---

2. Segment Tree 클래스: 서브트리 쿼리용

반응형

class SegmentTree:
    def __init__(self, euler, values):
        self.N = len(euler)
        self.tree = [0] * (4 * self.N)
        self.euler = euler
        self.pos = [0] * max(euler + [0]) + [1]
        self.values = values
        for i, u in enumerate(euler):
            self.pos[u] = i
        self.build(0, 0, self.N - 1)

    def build(self, node, l, r):
        if l == r:
            self.tree[node] = self.values[self.euler[l]]
            return
        mid = (l + r) // 2
        self.build(2*node+1, l, mid)
        self.build(2*node+2, mid+1, r)
        self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

    def query(self, ql, qr, node=0, l=0, r=None):
        if r is None:
            r = self.N - 1
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return self.query(ql, qr, 2*node+1, l, mid) + self.query(ql, qr, 2*node+2, mid+1, r)

    def update(self, idx, val, node=0, l=0, r=None):
        if r is None:
            r = self.N - 1
        if l == r:
            self.tree[node] = val
            return
        mid = (l + r) // 2
        if idx <= mid:
            self.update(idx, val, 2*node+1, l, mid)
        else:
            self.update(idx, val, 2*node+2, mid+1, r)
        self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

---

3. 연결 여부 확인 (ETT 기반 Union-Find처럼)

class ForestConnectivity:
    def __init__(self, n):
        self.etts = [EulerTourTree(n)]
        self.parent = list(range(n))  # DSU 기반

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

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

    def link(self, u, v):
        if self.connected(u, v):
            return False  # 이미 연결
        self.parent[self.find(v)] = self.find(u)
        self.etts[0].add_edge(u, v)
        return True

---

✅ 사용 예시

ett = EulerTourTree(5)
ett.add_edge(0, 1)
ett.add_edge(0, 2)
ett.add_edge(2, 3)
ett.add_edge(2, 4)

ett.dfs(0, -1)

# 세그먼트 트리 구성
st = SegmentTree(ett.euler, ett.values)

# 서브트리 크기 쿼리 (노드 2)
start = ett.in_time[2]
end = ett.out_time[2]
print("Subtree size of 2:", st.query(start, end))  # 출력: 3

---

📌 결론 및 요약

• ETT + Segment Tree를 통해 **O(log N)**으로
  서브트리 질의, 연결성 확인, 트리 수정이 가능
• Fully dynamic 연결성도 **O(log² N)**로 처리 가능
• 일반 트리 문제는 물론 변형된 유니온 파인드 문제에도 적용 가능

👉 다음 글에서는 Treap 또는 Splay Tree 기반 ETT 구현법과
실제 Competitive Programming 환경에서의 활용법을 다루겠습니다.

---

📚 참고자료

• CP-Algorithms – Euler Tour Tree
• [Stanford CS166 Dynamic Graphs]
• Open Data Structures – Treap/ETT

---

 

EulerTourTree, ETTForest, 트리연결성, 세그먼트트리, 서브트리합, 동적쿼리, 동적그래프, 파이썬알고리즘, SplayTree, SEO 최적화 10개