[고급편] Link/Cut Tree 완전 정복: 동적 트리 쿼리와 간선 연결/삭제 처리 기법

[고급편] Link/Cut Tree 완전 정복: 동적 트리 쿼리와 간선 연결/삭제 처리 기법

이제 우리는 정적인 트리(정해진 구조에서 쿼리만 수행하는 트리)를 넘어서,
동적으로 간선을 연결하거나 삭제하면서도 경로 쿼리를 빠르게 처리하는
**Link/Cut Tree (LCT)**라는 강력한 자료구조를 다룰 차례입니다.

---

🔍 Link/Cut Tree(LCT)란?

간선을 동적으로 삽입/삭제할 수 있는 트리 자료구조로
두 노드 사이의 경로 쿼리, 업데이트 등을 O(log N)에 처리할 수 있는 구조입니다.

📌 대표적으로 다음 기능을 지원합니다:

연산 설명

link(u, v)	u와 v를 간선으로 연결 (트리가 되도록)
cut(u, v)	u와 v 사이 간선을 제거
find_root(u)	u가 속한 트리의 루트 반환
lca(u, v)	u와 v의 최소 공통 조상 반환
path_query(u, v)	u–v 경로의 합/최댓값 등 쿼리
path_update(u, v, val)	u–v 경로의 값 업데이트

---

🧠 핵심 원리: Splay Tree 기반 동적 트리 구현

LCT는 Splay Tree라는 자가 균형 이진 탐색 트리를
트리 노드마다 유지함으로써, 연결 구조를 유연하게 관리합니다.

• 각 노드는 경로의 대표가 되며, **access(u)**를 통해 경로를 노출
• 경로 정보를 root-to-node 단위로 유지
• link, cut, make_root, access 등의 연산을 통해 트리 재구성 가능

---

🔧 주요 연산 구조

1. access(u)

• u에서 루트까지의 경로를 노출
• 경로 쿼리를 수행하기 전 필수 호출

2. make_root(u)

• u를 현재 트리의 루트로 변경
• 뒤집기(lazy reverse)를 통해 방향 전환

3. link(u, v)

• u와 v가 다른 트리에 있을 때 간선 연결

4. cut(u, v)

• u와 v 사이 간선을 제거
• 연결된 한 쪽이 반드시 부모여야 함

---

🛠 코드 프레임워크 (C++/Py 기반 구현 예고)

반응형

LCT는 구현 난이도가 높기 때문에 다음 글에서
Python 기반 LCT 최소구현 버전을 제공하고,
차후에 path_query, path_update, re-root 지원 버전으로 확장합니다.

---

🔍 사용 사례 및 실전 적용

✅ 동적 MST 유지

• 간선을 계속 추가/삭제하면서 MST를 유지해야 할 때
• 예시 문제: Codeforces 613E

✅ 실시간 경로 정보 변경

• 특정 노드에서 루트까지의 경로 합, 최댓값 관리
• 쿼리당 루트 변경 허용 시 HLD 불가 → LCT 필수

✅ 백업 및 롤백 가능한 트리 시스템

• 버전 관리, undo 기능을 갖춘 트리 구조

---

✅ LCT vs HLD vs ETT 요약

기능 LCT HLD ETT

정적 트리 지원	✅	✅	✅
동적 간선 삽입/삭제	✅	❌	❌
경로 질의/업데이트	✅	✅	❌ 직접불가
서브트리 쿼리	❌ 복잡	❌ 보완필요	✅ 뛰어남
구현 난이도	🔴 매우높음	🟡 중간	🟢 쉬움

---

🧠 다음 글 예고

👉 다음 글에서는
**"Python으로 Link/Cut Tree 최소 구현 버전"**을
단계별로 직접 구현하며,
access, make_root, link, cut, find_root 기능을 완성해보겠습니다.

---

 

LinkCutTree, 동적트리, 트리간선삽입삭제, pathQuery, 트리최적화, 트리알고리즘, LCT구현, 알고리즘강의, 경로업데이트, SEO 최적화 10개