데카르트 나무

컴퓨터 과학에서, 데카르트 트리는 숫자의 순서로부터 파생된 이진 트리이다; 그것은 그것이 힙 순서이고 트리의 대칭적인 (순서대로) 횡단이 원래의 순서를 반환한다는 특성으로부터 고유하게 정의될 수 있다.기하학적 범위 검색 데이터 구조의 맥락에서 Vuillemin(1980)에 의해 도입된 데카르트 트리는 이진 검색 문제에 대한 트리 및 무작위 이진 검색 트리 데이터 구조의 정의에도 사용되었다.시퀀스의 데카르트 트리는 시퀀스에서 가장 가까운 모든 작은 값을 찾기 위한 스택 기반 알고리즘을 사용하여 선형 시간으로 구성할 수 있습니다.

정의.

일련의 고유 번호에 대한 데카르트 트리는 다음 속성으로 고유하게 정의할 수 있습니다.

1. 시퀀스의 데카르트 트리에는 시퀀스의 각 번호에 대해 노드가 하나씩 있습니다.각 노드는 단일 시퀀스 값과 관련지어집니다.
2. 트리의 대칭(순서대로) 트래버스는 원래 시퀀스가 됩니다.즉, 왼쪽 서브트리는 시퀀스 순서에서 루트보다 앞의 값으로 구성되며 오른쪽 서브트리는 루트보다 뒤의 값으로 구성되며 트리의 각 하위 노드에서 유사한 순서 제약 조건이 유지됩니다.
3. 트리에는 히프 속성이 있습니다.루트가 아닌 노드의 부모 값은 노드 ^[1]자체보다 작습니다.

힙 속성에 따라 트리의 루트는 시퀀스에서 가장 작은 숫자여야 합니다.여기서부터 트리 자체를 재귀적으로 정의할 수도 있습니다.루트는 시퀀스의 최소값이며, 왼쪽과 오른쪽 서브트리는 루트 값의 왼쪽과 오른쪽의 후속에 대한 데카르트 트리입니다.따라서 위의 세 가지 특성은 데카르트 트리를 고유하게 정의합니다.

숫자의 시퀀스에 반복이 포함되어 있는 경우, 데카르트 트리는 위의 규칙을 적용하기 전에 일관된 연결 해제 규칙(예를 들어, 두 개의 동등한 요소 중 첫 번째 요소가 작은 것으로 취급되는 것을 결정하는 것)을 결정함으로써 정의될 수 있습니다.

데카르트 트리의 예를 위 그림에 나타냅니다.

범위 검색 및 최소 공통 상위 항목

데카르트 트리는 범위 최소 쿼리를 위한 효율적인 데이터 구조의 일부로 사용될 수 있습니다. 범위 최소 쿼리는 원래 ^[2]시퀀스의 연속적인 연속에서 최소값을 요구하는 쿼리를 수반합니다.데카르트 트리에서 이 최소값은 후속에서 가장 왼쪽 및 가장 오른쪽 값의 가장 낮은 공통 조상에서 찾을 수 있습니다.예를 들어 첫 번째 그림에 나타난 시퀀스의 후속(12,10,20,15)에서 후속(10)의 최소값은 최좌측 및 최우측 값(12,15)의 최소 공통 조상을 형성한다.최소 공통 상위 항목이 쿼리당 일정한 시간에 발견될 수 있으므로 선형 공간을 저장하고 선형 ^[3]시간으로 구성할 수 있는 데이터 구조를 사용하면 범위 최소화 문제에 대해 동일한 한계가 유지됩니다.

Bender & Farach-Colton(2000)은 입력 트리에서 가장 낮은 공통 조상을 비트리 기반 범위 최소화 기술을 적용하여 효율적으로 해결할 수 있음을 보여줌으로써 두 데이터 구조 문제 간의 관계를 뒤집었다.데이터 구조는 입력 트리를 시퀀스로 변환하고 결과 시퀀스에서 범위 최소값을 찾기 위해 오일러 투어 기술을 사용합니다.이 변환에 의해 발생하는 시퀀스는 데이터 구조에서 이용하는 특수한 형태(트리 내 인접 노드의 높이를 나타내는 인접 번호가 ±1)를 가진다.이 특별한 형태를 가지지 않는 시퀀스의 범위 최소화 문제를 해결하기 위해 데카르트 트리를 사용하여 범위 미니를 변환한다.mization 문제를 가장 낮은 공통 조상 문제로, 그리고 나서 이 특별한 형태를 가진 시퀀스에 대한 범위 최소화 중 하나로 문제를 다시 변환하기 위해 오일러 투어 기술을 적용한다.

동일한 범위 최소화 문제도 2차원 범위 검색의 관점에서 대체 해석을 제공할 수 있습니다.데카르트 평면의 최종 다수의 점 집합을 사용하여 점을 x 좌표로 정렬하고 이 트리가 형성되는 값의 시퀀스로 y 좌표를 이 순서로 사용함으로써 데카르트 트리를 형성할 수 있다.S가 부등식 L ≤ x r R에 의해 정의된 수직 슬래브 내의 입력점의 서브셋이고, p가 S의 최좌측점(최소 x 좌표를 가진 점)이고, q가 S의 최우측점(최대 x 좌표를 가진 점)이라면, 데카르트 트리의 p와 q의 가장 낮은 공통 조상점은 슬래브 내의 보텀 포인트이다.작업이 3개의 부등식 L δ x δ R 및 y δ T에 의해 경계된 영역 내의 모든 점을 나열하는 3면 범위 쿼리는 이 bottommost 지점 b를 찾아 T에 대한 y 좌표를 비교하고 (그 점이 p와 bw 사이에 경계된 2개의 슬래브에 연속적으로 재귀하는 경우) 응답할 수 있다.een b와 q.이렇게 슬래브에서 가장 왼쪽 및 가장 오른쪽 점이 식별되면 3면 영역 내의 모든 점이 ^[4]점당 일정한 시간에 나열될 수 있습니다.

데카르트 트리에서 가장 낮은 공통 조상의 동일한 구성을 통해 초변형 공간 내의 점 쌍 사이의 거리를 쿼리당 일정한 시간으로 쿼리할 수 있는 선형 공간을 가진 데이터 구조를 구성할 수 있습니다.울트라 파라미터 내의 거리는 ^[5]메트릭의 최소 스패닝트리의 최소 패스 무게와 동일합니다.최소 스패닝 트리에서 데카르트 트리를 구축할 수 있습니다.데카르트 트리의 루트 노드는 최소 스패닝 트리의 가장 무거운 에지를 나타냅니다.이 엣지를 삭제하면 최소 스패닝트리가 2개의 서브트리로 분할되며, 이 2개의 서브트리에 대해 재귀적으로 구성된 데카르트 트리가 데카르트 트리의 루트 노드의 자식을 형성합니다.데카르트 트리의 잎은 미터법 공간의 점을 나타내며, 데카르트 트리의 두 잎의 가장 낮은 공통 조상은 최소 스패닝 트리의 두 점 사이의 가장 무거운 가장자리이며, 두 점 사이의 거리와 같은 무게를 가집니다.최소 스패닝 트리가 발견되고 가장자리 무게가 정렬되면 데카르트 트리를 ^[6]선형 시간으로 구성할 수 있습니다.

나무들

데카르트 트리는 이진 트리이기 때문에 값의 순서가 정렬된 시퀀스에 대한 이진 검색 트리로 사용하는 것이 당연합니다.단, 2진수 검색 트리의 검색 키를 구성하는 값과 동일한 값을 기반으로 데카르트 트리를 정의하는 것은 잘 작동하지 않습니다. 정렬된 시퀀스의 데카르트 트리는 경로일 뿐이며, 이 트리의 2진수 검색은 경로의 순차적 검색으로 감소합니다.그러나 키 자체와 다른 각 검색 키에 대해 우선 순위 값을 생성하고, 키 값에 따라 입력을 정렬하고, 대응하는 우선 순위 시퀀스를 사용하여 데카르트 트리를 생성함으로써 보다 균형 잡힌 검색 트리를 생성할 수 있습니다.이 구성은 위에서 설명한 기하학적 프레임워크에서 동일하게 볼 수 있으며, 여기서 점 집합의 x 좌표가 검색 키이고 y 좌표가 우선 순위이다.

이 아이디어는 난수 사용을 우선순위로 제시한 세이델 & 아라곤(1996)에 의해 적용되었다.이 랜덤 선택에서 발생하는 데이터 구조는 바이너리 검색 트리와 바이너리 힙 기능의 조합으로 인해 treap이라고 불립니다.새로운 키를 기존 트리의 리프로서 삽입하고 우선순위를 선택한 후 노드에서 트리의 루트까지의 경로를 따라 트리 회전 조작을 실행하여 이 삽입으로 인한 히프 속성의 위반을 복구할 수 있습니다.또한 삭제도 마찬가지로 일정한 AM에 의해 실행될 수 있습니다.트리에 변경을 가한 후 트리의 단일 경로를 따라 일련의 회전을 수행합니다.

키가 트리에 삽입될 때마다 각 키의 우선순위가 무작위로 그리고 독립적으로 선택되면, 결과 데카르트 트리는 빈 트리에서 시작하여 무작위로 선택된 순열로 키를 삽입하여 계산되는 트리인 랜덤 이진 검색 트리와 동일한 속성을 가집니다.ree 구조는 변경되지 않고 새 노드를 트리의 리프로 삽입합니다.랜덤 바이너리 검색 트리는 훨씬 더 오랫동안 연구되어 왔고 검색 트리와 같이 잘 동작하는 것으로 알려져 있다(그들은 높은 확률로 로그 깊이를 가지고 있다). 같은 좋은 동작이 treaps로 전달됩니다.아라곤과 세이델이 제안한 것처럼 자주 액세스하는 노드의 우선순위를 재설정하여 트립의 뿌리 쪽으로 이동하여 동일한 키에 대한 향후 액세스 속도를 높일 수도 있습니다.

효율적인 구조

데카르트 트리는 입력 시퀀스로부터 선형 시간으로 구성될 수 있다.한 가지 방법은 지금까지 처리된 노드의 데카르트 트리를 유지한 상태에서 트리의 위쪽과 아래쪽을 모두 통과할 수 있는 구조로 시퀀스 값을 왼쪽에서 오른쪽으로 간단하게 처리하는 것입니다.각 새로운 값 x를 처리하려면 시퀀스에서 x보다 앞의 값을 나타내는 노드에서 시작하여 이 노드에서 트리의 루트까지의 경로를 따라 x보다 작은 y 값을 찾습니다.노드 x는 y의 오른쪽 자식이 되고 y의 오른쪽 자식은 x의 왼쪽 자식이 됩니다.각 새로운 노드x 의 부모 y 를 검색하는 데 걸리는 시간은 트리내의 ^[4]오른쪽 끝에서 삭제되는 노드의 수에 따라 과금될 수 있기 때문에, 이 순서의 합계 시간은 선형적입니다.

대체 선형 시간 구성 알고리즘은 가장 가까운 모든 작은 값 문제에 기초합니다.입력 시퀀스에서는 값 x의 왼쪽 인접을 x보다 앞에 발생하고, x보다 작으며, 다른 어떤 작은 값보다 x에 가까운 값으로 정의할 수 있다.오른쪽 네이버는 대칭적으로 정의됩니다.왼쪽 네이버 시퀀스는 입력의 후속 스택을 유지하는 알고리즘에 의해 검출될 수 있습니다.새로운 시퀀스 값 x마다 스택이 비거나 최상위 요소가 x보다 작을 때까지 팝된 후 x가 스택에 푸시됩니다.x의 왼쪽 인접 라우터는 x가 눌렸을 때의 상위 요소입니다.시퀀스의 역방향에 동일한 스택알고리즘을 적용하면 올바른 네이버를 찾을 수 있습니다.데카르트 트리에서 x의 부모는 x의 왼쪽 인접 라우터 또는 x의 오른쪽 인접 라우터 중 하나이며 값이 더 큽니다.왼쪽과 오른쪽 이웃은 병렬 알고리즘에 의해 효율적으로 구성될 수 있으므로, 이 공식은 데카르트 트리 ^[7]구성을 위한 효율적인 병렬 알고리즘을 개발하기 위해 사용될 수 있다.

데카르트 트리 구성을 위한 또 다른 선형 시간 알고리즘은 분할 및 정복에 기초한다.특히 알고리즘은 입력의 각 절반에 트리를 재귀적으로 구축한 후 오른쪽 트리의 왼쪽 척추와 왼쪽 척추(둘 다 루트-리프 순서가 가장 작은 것부터 가장 큰 것까지 값을 정렬하는 경로)를 취함으로써 두 트리를 병합하고 이러한 t를 대체하여 표준 병합 연산을 수행합니다.동일한 노드를 포함하는 단일 경로를 기준으로 2개의 트리로 경로를 설정합니다.결합경로에서는 왼쪽 트리에서 각 노드의 정렬순서의 후계자가 오른쪽 자녀에 배치되고 오른쪽 트리에서 각 노드의 후계자가 왼쪽 자녀에 배치되며, 이는 척추 내의 후계자에게 사용되었던 것과 동일한 위치이다.왼쪽 트리의 노드 왼쪽 자식과 오른쪽 트리의 노드 오른쪽 자식은 변경되지 않은 상태로 유지됩니다.알고리즘은 또한 각 재귀 수준에서 두 하위 문제 각각을 병렬로 계산할 수 있고 병합 연산도 효율적으로 병렬화할 수 있기 때문에 병렬화할 수 있습니다.^[8]

정렬 응용 프로그램

Levcopoulos & Peterson(1989)은 데카르트 나무를 기반으로 한 정렬 알고리즘을 설명한다.이들은 루트에 최대값이 있는 트리를 기반으로 알고리즘을 기술하지만 최소값이 루트에 있다는 규칙을 사용하여 데카르트 트리를 지원하도록 쉽게 수정할 수 있습니다.일관성을 유지하기 위해 아래에 설명된 알고리즘의 이 수정 버전입니다.

레브코풀로스 가족Peterson 알고리즘은 후보 minima의 priority 큐를 유지하고 각 단계에서 이 큐의 최소값을 찾아 삭제하고 이 값을 출력 시퀀스의 끝으로 이동하는 선택 정렬 또는 힙 정렬 버전으로 볼 수 있습니다.알고리즘에서 priority 큐는 데카르트 트리의 부모가 이미 발견되어 삭제된 요소만으로 구성됩니다.따라서 알고리즘은 다음 단계로 구성됩니다.

1. 입력 시퀀스에 대한 데카르트 트리 구성
2. 처음에는 트리 루트만 포함하는 priority 큐를 초기화합니다.
3. priority 큐가 비어 있지 않은 경우:
   • priority 큐에서 최소값 x를 찾아 삭제합니다.
   • 출력 시퀀스에 x 추가
   • 우선 순위 큐에 x의 데카르트 트리 하위 항목 추가

Levcopoulos 및 Peterson에서 알 수 있듯이 이미 정렬된 입력 시퀀스에 대해서는 priority 큐의 크기가 작아지기 때문에 이 메서드는 정렬된 입력의 이점을 활용하여 보다 빠르게 실행할 수 있습니다.구체적으로는 이 알고리즘의 최악의 실행시간은 O(n log k)입니다.여기서 k는 시퀀스 내의 모든 값 x에 대한 연속되는 시퀀스 값의 쌍의 평균입니다.이들은 또한 임의의 n과 k = ((1)에 대해 비교 기반 정렬 알고리즘이 일부 입력에 대해 ω(n log k) 비교를 사용해야 한다는 하한을 증명한다.

역사

데카르트 나무는 Vuillemin(1980)에 의해 도입되고 명명되었다.이름은 평면에 대한 데카르트 좌표계에서 유래했다: 위에서 논의한 2차원 범위 검색 어플리케이션에서와 같이, 점 집합을 위한 데카르트 트리는 대칭 횡단 순서로서 x 좌표에 의해 점의 정렬 순서를 가지며, 그에 따른 힙 속성을 가진다.점의 y좌표로 이동합니다.Gabow, Bentley & Tarjan(1984)과 그 이후의 저자들은 여기서 데카르트 트리가 수열로부터 정의되는 정의를 따랐다. 이 변화는 x좌표의 정렬된 순서 이외의 순서를 허용하도록 Vuillemin의 기하학적 설정을 일반화하며, 데카르트 트리를 비기하학적 문제에도 적용할 수 있게 한다.

메모들

레퍼런스