목록2026/03/24 (1)
Elevation
트리 (4) - 센트로이드
본래 무게중심이라는 뜻의 단어인 센트로이드(centroid)는, 트리에서 하나의 정점을 제거했을 때 나눠지는 서브 트리의 정점의 개수가 원래 정점의 개수의 절반 이하가 되도록 하는 정점으로 정의된다. 따라서 센트로이드를 찾으면 트리를 균형 있게 분할하는 것이 가능하다. 몇 가지 센트로이드에 대한 직관적이고도 중요한 성질들이 있다. 트리에는 센트로이드가 항상 존재한다.센트로이드는 1개 혹은 2개 존재한다.센트로이드가 2개 존재하는 경우, 두 센트로이드는 서로 인접해 있다. 트리에서 분할 정복을 수행하려는 경우, 고른 root에 따라 최악에는 트리의 깊이가 정점 수 $N$까지 늘어날 수 있어 시간이 오래 걸릴 우려가 있다. 이럴 때 전체 트리의 센트로이드 $u$를 찾은 뒤, $u$에 대해 처리를 완료한 후 ..
ps/tree
2026. 3. 24. 00:05