범위 트리(Range Tree)란?
범위 트리는 점(point)들의 목록을 저장하기 위한 정렬된 트리 자료 구조입니다. 주어진 범위 내에 속한 모든 점을 효율적으로 검색할 수 있다는 것이 가장 큰 특징이며, 일반적으로 2차원 이상의 공간에서 구현됩니다.
범위 트리는 kd-트리와 유사하지만, 질의 시간이 O(logd n + k)로 더 빠른 대신 저장 공간이 O(n logd-1 n)으로 더 많이 필요합니다. 여기서 d는 공간의 차원, n은 트리에 저장된 점의 개수, k는 하나의 질의로 검색되는 점의 개수를 의미합니다.
범위 트리는 구간 트리(Interval Tree)와 혼동되기 쉽습니다. 범위 트리가 점을 저장하고 주어진 범위 안에 있는 점들을 효율적으로 찾아내는 반면, 구간 트리는 구간을 저장하고 주어진 점을 포함하는 구간들을 효율적으로 검색한다는 점에서 차이가 있습니다.
자료 구조
위 그림은 1차원 범위 트리의 예시입니다. 리프 노드를 제외한 모든 노드는 자신의 왼쪽 서브트리에 있는 최댓값을 저장합니다.
1차원 점 집합에 대한 범위 트리는 해당 점들에 대한 균형 이진 탐색 트리(Balanced Binary Search Tree)로 취급됩니다. 트리에 저장된 점들은 트리의 리프(leaf) 노드에 위치하며, 각 내부 노드는 왼쪽 서브트리에 포함된 값 중 최댓값을 저장합니다.
d차원 점 집합에 대한 범위 트리는 재귀적으로 정의된 다층(multi-level) 이진 탐색 트리입니다. 자료 구조의 각 층은 d개의 차원 중 하나에 대한 이진 탐색 트리로 구성됩니다. 첫 번째 층은 d개 좌표 중 첫 번째 좌표를 기준으로 한 이진 탐색 트리이며, 이 트리의 각 정점 v는 v의 서브트리에 저장된 점들의 마지막 (d−1)개 좌표에 대한 (d−1)차원 범위 트리를 연관 구조(associated structure)로 가집니다.
주요 연산
구축(Construction)
n개의 점으로 이루어진 집합에 대한 1차원 범위 트리는 이진 탐색 트리이므로, O(n log n) 시간 안에 구축할 수 있습니다.
고차원 범위 트리는 재귀적인 방식으로 구축됩니다. 먼저 점들의 첫 번째 좌표를 기준으로 균형 이진 탐색 트리를 만들고, 이어서 이 트리의 각 정점 v에 대해 v의 서브트리에 포함된 점들로 (d−1)차원 범위 트리를 구축합니다. 이러한 방식으로 범위 트리를 구축하는 데는 O(n logd n)의 시간이 필요합니다.
범위 질의(Range Query)
범위 질의는 주어진 직사각형(또는 초직사각형) 영역 안에 포함된 모든 점을 찾아내는 연산입니다. 1차원 범위 트리에서 범위 질의는 O(log n + k) 시간에 처리되며, d차원 범위 트리에서는 O(logd n + k) 시간에 처리됩니다. 이는 kd-트리의 최악의 경우 질의 시간보다 훨씬 안정적이고 효율적입니다.
활용 분야
범위 트리는 계산 기하학(Computational Geometry)에서 널리 사용되며, 데이터베이스의 다차원 범위 검색, 지리 정보 시스템(GIS)에서 특정 영역 내의 위치 검색, 컴퓨터 그래픽스 등 다양한 분야에서 활용됩니다.