범위 트리는 포인트 목록을 보유하는 정렬된 트리 데이터 구조로 정의됩니다. 주어진 범위 내의 모든 포인트를 효율적으로 검색할 수 있도록 하며 일반적으로 2차원 이상으로 구현됩니다. O(log d 의 쿼리 시간이 더 빠르다는 점을 제외하고는 kd-tree와 동일합니다. n + k) 그러나 O(n log d-1 의 더 나쁜 저장) n), d는 공간의 차원을 나타내고, n은 트리의 포인트 수를 나타내고, k는 주어진 쿼리에 대해 검색된 포인트 수를 나타냅니다. 범위 트리는 간격 트리로 구분할 수 있습니다. 포인트를 저장하고 주어진 범위의 포인트를 효율적으로 검색할 수 있도록 하는 대신, 간격 트리는 간격을 저장하고 주어진 포인트를 포함하는 간격이 효율적으로 검색되도록 합니다.
데이터 구조
1차원 범위 트리의 예. 리프가 아닌 각 노드는 왼쪽 하위 트리에 가장 높은 값을 저장합니다.
1차원 포인트 세트의 범위 트리는 해당 포인트에 대한 균형 이진 검색 트리로 처리됩니다. 트리에 저장된 포인트는 트리의 잎에 저장됩니다. 각 내부 노드는 왼쪽 하위 트리에 포함된 최대값을 저장합니다. d 차원의 점 집합에 대한 범위 트리는 재귀적으로 정의된 다단계 이진 검색 트리입니다. 데이터 구조의 각 수준은 d 차원 중 하나에서 이진 검색 트리로 처리됩니다. 첫 번째 수준은 첫 번째 d 좌표에 대한 이진 검색 트리입니다. 이 트리의 각 정점 v는 v의 하위 트리에 저장된 점의 마지막 (d−1) 좌표에 있는 (d−1) 차원 범위 트리인 관련 구조로 구성됩니다.
작업
건설
n개의 점 집합에 대한 1차원 범위 트리는 O(n log n) 시간에 구축할 수 있는 이진 탐색 트리입니다. 더 높은 차원의 범위 트리는 포인트의 첫 번째 좌표에 균형 이진 탐색 트리를 구성하여 재귀적으로 구축되며, 그 후 이 트리의 각 정점 v에 대해 포함된 포인트에 (d-1) 차원 범위 트리를 구축합니다. v의 하위 트리에서 이런 식으로 범위 트리를 구축하려면 O(n log d n) 시간.