Top Tree | Notion

배경지식

이는 배경지식이 필요한 알고리즘으로 학습하기 전에 다음 알고리즘들에 대한 사전 지식이 필요하다.

내용은 다음 논문을 기반으로 한다.

대게 동적 그래프(dynamic graph) 문제에서는 간선의 삽입이나 삭제와 같은 변화가 발생할 때 데이터 구조를 처음부터 다시 계산하지 않고 동적으로 간선을 관리하여 특정 쿼리를 효율적으로 처리하고자 한다.

예를 들어, 중계기지국을 노드로 통신 회선을 간선으로 표현하는 통신 네트워크 그래프에서 다음과 같은 질문들을 해결할 수 있다:

회선이 끊기거나 복구되었을 때 모든 기지국이 여전히 연결되어 있는가?
회선이 끊어졌을 때 기존 회선을 수리하는 것보다 새 회선을 건설하는 것이 더 비용 효율적인가?
1. 만약 새 회선을 건설해야 한다면 어느 회선을 건설해야 하는가?
어떤 회선이 끊어지더라도 모든 기지국이 연결된 상태를 유지하려면 어떤 회선을 추가로 건설해야 하는가?
기지국 하나가 작동을 멈추었을 때 나머지 기지국들이 서로 연결되어 있는가?

동적 그래프 알고리즘은 동적 트리 데이터 구조를 기반으로 작동한다. 토폴로지 트리가 대표적인 예시이나 이는 최대 차수가 3인 삼진트리에만 적용되고 일반 트리에는 적용할 수 없다는 한계가 있었다. 이러한 한계를 극복하기 위해 탑트리(Top-tree)가 개발되었다.

탑-트리는 루트가 없는 동적 트리를 위한 자료구조이며 분할 정복 알고리즘으로 구현된다. 핵심 개념은 원본 트리 T를 '클러스터'라는 서브 트리들로 재귀적으로 분해하고 이 클러스터들을 높이가 O(logn)인 이진트리 형태로 유지하는 것이다.