[Link Cut Tree] 1. 개요와 구현
먼저 알아야 할 것 : Splay Tree Link Cut Tree(LCT)는 Forest를 관리하는 자료구조이며, 각각의 트리는 루트를 가집니다.LCT는 이름에도 있듯 트리 두개를 연결하고(Link), 끊는(Cut) 연산을 가지고 있습니다.LCT에서는 마치 Heavy-Light Decomposition처럼 트리를 몇 개의 Path로 나누어 관리하는데, 각각의 Path를 관리할 때 주로 Splay Tree를 사용합니다. 왼쪽 트리가 실제 표현하고자 하는 트리의 모습이고, 오른쪽 트리는 왼쪽 트리를 Link Cut Tree로 구현한 모습입니다.실선으로 연결된 경로가 하나의 Path이고, 점선은 Path의 루트가 Path의 부모를 가리키도록 한 선입니다.왼쪽 트리에서 (1, 2, 5, 9), (3, 7), ..
더보기
