범위 트리

범위 트리
유형	나무
발명된	1979
발명된 사람	존 루이스 벤틀리
큰 O 표기법에서의 시간 복잡성
알고리즘. 평균 최악의 경우 공간 ${\displaystyle O(n\log ^{d-1}n)}$ ${\displaystyle O(n\log ^{d-1}n)}$ 검색 ${\displaystyle O(\log ^{d}n+k)}$ ${\displaystyle O(\log ^{d}n+k)}$

컴퓨터 과학에서 레인지 트리는 점의 목록을 보유하기 위해 정렬된 트리 데이터 구조다.주어진 범위 내의 모든 점을 효율적으로 보고할 수 있도록 하며, 일반적으로 2차원 이상에서 사용된다.레인지 트리는 1979년 존 루이스 벤틀리에 의해 소개되었다.^[1]비슷한 데이터 구조는 루케르,^[2] 리, 웡,^[3] 윌러드에 의해 독자적으로 발견되었다.^[4]레인지 트리는 k-d 트리의 대안이다.Compared to k-d trees, range trees offer faster query times of (in Big O notation) ${\displaystyle O(\log ^{d}n+k)}$ but worse storage of ${\displaystyle O(n\log ^{d-1}n)}$, where n is the number of points stored in the tree, d is the dimension of each point and k is the number of point지정된 쿼리에 의해 보고된 s.

Bernard Chazelle improved this to query time ${\displaystyle O(\log ^{d-1}n+k)}$ and space complexity ${\displaystyle O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)}$.^[5][6]

데이터 구조

1차원 점 집합의 범위 트리는 해당 점의 균형 잡힌 이진 검색 트리다.트리에 저장된 점은 트리의 잎에 저장되며, 각 내부 노드는 왼쪽 하위 트리의 가장 큰 값을 저장한다.d-dimension의 점 집합에 있는 범위 트리는 재귀적으로 정의된 다단계 이진 검색 트리다.데이터 구조의 각 레벨은 d-dimens 중 하나에 있는 이진 검색 트리 입니다.첫 번째 레벨은 d 좌표 중 첫 번째 레벨에 있는 이진 검색 트리 입니다.이 트리의 각 꼭지점 v는 v의 하위 트리에 저장된 포인트의 마지막 (d-1) 좌표에 있는 (d-1)차원 범위 트리인 관련 구조를 포함한다.

운영

건설

n개의 점 집합에 있는 1차원 범위 트리는 이진 검색 트리로, $O{\displaystyle }$(${\displaystyle n}$ log${\displaystyle \mathrm{nn}}$)$${\$displaystyle O(n\log$ n$)}$번으로$$ 구성할 수 있다.더 높은 차원의 범위 트리는 점의 첫 번째 좌표에 균형 잡힌 이진 검색 트리를 구성한 다음 이 트리의 각 꼭지점 v에 대해 v의 하위 트리에 포함된 점에 (d-1)차원 범위 트리를 구성하여 반복적으로 생성된다. 이러한 방식으로 범위 트리를 구성하려면 $O{\displaystyle (n^{}}$ log d${\displaystyle {}^{}{d}^{}}$ n)가 필요하다.${\displaystyle )}$ ${\displaystyle O(n\log ^{d}n)}$시간$$.

이 시공 시간은 2차원 범위 트리에 $대해{\displaystyle }$ O${\displaystyle (n}$ ${\displaystyle \log }$ $){\displaystyle$ O$(n\log$ n$)}$로 개선할 수 있다$.$^[7] S는 n 2차원 점의 집합이다.S에 점이 하나만 포함된 경우 해당 점이 포함된 잎을 반환하십시오.그렇지 않으면 S에 있는 점의 y 좌표에 1차원 범위 트리인 S의 관련 구조를 생성한다.x는_m 점의 중위수 x 좌표가 되도록 한다.S는_L x보다_m 작거나 같은 x 좌표를 가진 점들의 집합이 되고 S는_R x보다_m 큰 x 좌표를 가진 점들의 집합이 되게 한다. S의_L 2차원 범위 트리인 v와_L S의_R 2차원 범위 트리인 v를_R 재귀적으로 구성한다.왼쪽-자녀 v와_L 오른쪽-자녀 v로_R 정점 v를 만든다. 알고리즘을 시작할 때 y 좌표로 점을 정렬하고, x 좌표로 점을 분할할 때 이 순서를 유지하면 각 하위 트리의 관련 구조를 선형 시간 내에 구성할 수 있다.이렇게 하면 2차원 범위 트리를 $O{\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle O(n\log$ n$)\}($으)로 구성하는 시간이 단축되고, d차원 범위 트리를 $O{\displaystyle (n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle d^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}n}$) ${\dplaystyle O(n\log ^{d-1}n)$로 구성하는 시간도 단축된다$.$

범위 쿼리

범위 트리의 범위 쿼리는 지정된 간격 내에 있는 점 집합을 보고한다.간격[x₁, x₂]에 있는 점을 보고하려면 x와₁ x를₂ 검색하는 것으로 시작한다.나무의 어떤 꼭대기에서는 x와₁ x의₂ 검색 경로가 갈릴 것이다.v를_split 이 두 검색 경로의 공통점이 되는 마지막 꼭지점이 되도록 하자.v에서_split x까지의₁ 검색 경로에 있는 모든 꼭지점 v에 대해, v에 저장된 값이 x보다₁ 크면 v의 오른쪽 하위 트리에 있는 모든 점을 보고하고, v가 리프인 경우 v에 저장된 값이 쿼리 간격 내에 있으면 v에 저장된 값을 보고한다.마찬가지로 v에서_split x까지의 검색₂ 경로를 따라 x 미만의₂ 값을 가진 정점의 왼쪽 하위 트리에 저장된 모든 점을 보고하고, 이 경로가 쿼리 간격 내에 있으면 이 경로의 리프를 보고한다.

범위 트리는 균형 잡힌 이진수이기 때문에 x와₁ x에₂ 대한 검색 경로는 $길이$가 O${\displaystyle (\log }$ $){\displaystyle$ O$(\log n)}$이며$,$ 정점의 하위 트리에 저장된 모든 점을 트리 통과 알고리즘을 사용하여 선형 시간에 보고할 수 있다.이후 범위 조회를 수행하는 시간은 $O{\displaystyle (\log }$ ${\displaystyle n}$+ ${\displaystyle k}$) ${\displaystyle O(\log n+k)}$이며$,$ 여기서 k는 조회 간격의 포인트 수입니다.

d-dimens의 범위 쿼리는 유사하다.검색 경로의 하위 트리에 저장된 모든 점을 보고하는 대신 각 하위 트리의 관련 구조에 대해 (d-1) 차원 범위 쿼리를 수행하십시오.결국 1차원 범위 질의가 수행되고 정확한 지점이 보고된다.d차원 쿼리는 $O{\displaystyle (\log \mathrm{logn}}$) ${\displaystyle$ O$(\log n)}($d-1) 차원 범위 쿼리로 구성되므로, d차원 범위 쿼리를 수행하는 데 필요한 시간은 $O{\displaystyle ({\log }^{}}$ ${\displaystyle d}$ ${\displaystyle {}^{}}$ n${\displaystyle }$+ ${\displaystyle k}$) ${\displaystyle$ O$(\log ^{d}n+k$이며 여기서 k는 쿼리 간격의 포인트 수입니다.이는 부분 계단식 계단식 변형을 사용하여$$ $O{\displaystyle ({\log }^{}}$ ${\displaystyle d^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}n}$+ k${\displaystyle }$) ${\displaystyle$ O$(\log ^{d-1n+k)$로 줄일 수 있다.^[2][4][7]

참고 항목

• k-d 트리
• 세그먼트 트리
• 레인지 검색

참조

외부 링크

• 계산 기하 알고리즘 라이브러리인 CGAL의 범위 및 세그먼트 트리.
• 제8강: 레인지 트리즈, 마크 반 크렐드.
• 병렬 증강 맵 라이브러리인 PAM을 사용하여 트리 범위를 조정하십시오.