트립 (자료 구조)

컴퓨터 과학에서 **트립**(Treap)과 **확률적 이진 탐색 트리**는 순서 있는 키의 동적 집합을 유지하고 키 간의 이진 검색 알고리즘을 허용하는 서로 밀접하게 관련된 두 가지 형태의 이진 탐색 트리 자료 구조이다. 어떤 키 삽입 및 삭제 시퀀스 후에도 트리의 모양은 무작위 이진 트리와 동일한 확률 분포를 가진 무작위 변수이다. 특히, 높은 확률로 높이는 키 수의 로그에 비례하므로 각 검색, 삽입 또는 삭제 작업은 로그 시간 안에 수행된다.

## 설명
섬네일|왼쪽|알파벳 키와 숫자 최대 힙 순서를 가진 트립
트립은 1989년 라이문트 자이델과 세실리아 R. 아라곤에 의해 처음 기술되었다. 그 이름은 혼성어로 트리와 힙을 합친 것이다.
이는 각 키에 (무작위로 선택된) 숫자 우선순위가 부여된 카르테시안 트리이다. 다른 이진 탐색 트리와 마찬가지로 노드의 중위 순회 순서는 키의 정렬된 순서와 같다. 트리의 구조는 힙 순서를 유지해야 한다는 요구 사항에 의해 결정된다. 즉, 모든 비리프 노드의 우선순위는 자식의 우선순위보다 크거나 같아야 한다. 따라서 일반적으로 카르테시안 트리와 마찬가지로 루트 노드는 최대 우선순위 노드이며, 왼쪽 및 오른쪽 서브트리는 해당 노드의 왼쪽과 오른쪽에 있는 정렬된 순서의 서브시퀀스에서 동일한 방식으로 형성된다.

트립을 설명하는 동등한 방법은 가장 높은 우선순위부터 노드를 이진 탐색 트리에 삽입하여 재조정 없이 형성될 수 있다는 것이다. 따라서 우선순위가 독립적인 무작위 숫자(두 노드가 동일한 우선순위를 가질 가능성이 거의 없도록 충분히 큰 우선순위 공간에서 분포된)라면 트립의 모양은 무작위 이진 탐색 트리의 모양과 동일한 확률 분포를 갖는다. 무작위 이진 탐색 트리는 무작위로 선택된 삽입 순서로 재조정 없이 노드를 삽입하여 형성된 탐색 트리이다. 무작위 이진 탐색 트리는 높은 확률로 로그 높이를 갖는 것으로 알려져 있으므로 트립도 마찬가지이다. 이는 퀵 정렬의 이진 탐색 트리 논증과 유사하며 퀵 정렬이 예상 O(n \log n) 시간에 실행된다. 이진 탐색 트리가 정렬의 동적 문제 버전의 해법이라면, 트립은 우선순위가 피벗 선택을 안내하는 동적 퀵 정렬에 특히 해당한다.

아라곤과 자이델은 또한 자주 접근되는 노드에 더 높은 우선순위를 부여하는 것을 제안한다. 예를 들어, 각 접근 시 무작위 숫자를 선택하고 이전 우선순위보다 높으면 해당 숫자로 노드의 우선순위를 대체하는 프로세스를 통해서이다. 이 수정은 트리가 무작위 형태를 잃게 할 것이다. 대신, 자주 접근되는 노드는 트리 루트 근처에 있을 가능성이 더 높아져 해당 노드에 대한 검색이 더 빨라질 것이다.

나오르와 니심은 공개 키 암호 시스템에서 인증 인증서를 유지하는 응용 분야를 설명한다.

## 연산

### 기본 연산
트립은 다음 기본 연산을 지원한다:

* 주어진 키 값을 검색하려면 우선순위를 무시하고 이진 탐색 트리에서 표준 이진 검색 알고리즘을 적용한다.
* 트립에 새 키 x를 삽입하려면 x에 대한 무작위 우선순위 y를 생성한다. 트리에서 x를 이진 검색하고 이진 검색이 x에 대한 노드가 존재해야 한다고 결정하는 리프 위치에 새 노드를 생성한다. 그런 다음 x가 트리의 루트가 아니고 해당 부모 z보다 큰 우선순위 번호를 갖는 한, x와 z 사이의 부모-자식 관계를 역전시키는 트리 회전을 수행한다.
* 트립에서 노드 x를 삭제하려면, x가 트리의 리프이면 단순히 제거한다. x가 단일 자식 z를 가지면 트리에서 x를 제거하고 z를 x의 부모의 자식으로 만든다 (또는 x가 부모가 없으면 z를 트리의 루트로 만든다). 마지막으로 x가 두 자식을 가지면 트리에서 해당 위치를 정렬된 순서에서 즉시 후속 z의 위치와 교환하여 이전 경우 중 하나를 발생시킨다. 이 마지막 경우, 교환은 z의 힙 순서 속성을 위반할 수 있으므로 이 속성을 복원하기 위해 추가 회전을 수행해야 할 수 있다.

### 트립 구축

* 트립을 구축하려면 트립에 n개의 값을 삽입할 수 있으며 각 값은 O(\log n) 시간이 걸린다. 따라서 트립은 값 목록에서 O(n \log n) 시간에 구축할 수 있다.

### 대량 연산
단일 요소 삽입, 삭제 및 조회 작업 외에도 트립에서 여러 빠른 "대량" 작업이 정의되었다: 합집합, 교집합 및 집합 차이. 이들은 두 가지 도우미 작업인 분할(split) 및 결합(join)에 의존한다.

* 트립을 두 개의 작은 트립으로 분할하려면, 키 x보다 작은 것과 키 x보다 큰 것으로 나누고, 트립의 어떤 노드의 우선순위보다도 큰 최대 우선순위를 가진 x를 트립에 삽입한다. 이 삽입 후 x는 트리의 루트 노드가 될 것이며, x보다 작은 모든 값은 왼쪽 서브트리에서, x보다 큰 모든 값은 오른쪽 서브트리에서 발견될 것이다. 이것은 트립에 단일 삽입하는 것과 동일한 비용이 든다.
* 이전 분할의 결과물인 두 트립을 결합할 때, 첫 번째 트립의 가장 큰 값이 두 번째 트립의 가장 작은 값보다 작다고 안전하게 가정할 수 있다. x 값을 가진 새 노드를 생성하고, x가 첫 번째 트립의 최대 값보다 크고 두 번째 트립의 최소 값보다 작도록 하며, 최소 우선순위를 할당한 다음 왼쪽 자식을 첫 번째 힙으로, 오른쪽 자식을 두 번째 힙으로 설정한다. 힙 순서를 수정하기 위해 필요에 따라 회전한다. 그 후, 이는 리프 노드가 될 것이며 쉽게 삭제할 수 있다. 결과는 두 원래 트립이 병합된 하나의 트립이다. 이는 효과적으로 분할을 "되돌리는" 것이며, 비용도 동일하다. 더 일반적으로, 결합 연산은 임의의 우선순위(즉, 가장 높을 필요는 없는)를 가진 키와 두 개의 트립에 대해 작동할 수 있다.
섬네일|트립 <math>T_1</math>과 <math>T_2</math>에 대해 수행된 결합. 결합 후 <math>T_1</math>의 오른쪽 자식은 이전 오른쪽 자식과 <math>T_2</math>의 결합으로 정의된다.
결합 알고리즘은 다음과 같다:

 **함수** join(L, k, R)
     **만약** prior(k, k(L)) 그리고 prior(k, k(R)) **이면 반환** Node(L, k, R)
     **만약** prior(k(L), k(R)) **이면 반환** Node(left(L), k(L), join(right(L), k, R))
     **반환** Node(join(L, k, left(R)), k(R), right(R))
섬네일|<math>T</math>를 <math>x</math>로 분할하려면, <math>T</math>의 왼쪽 또는 오른쪽 자식에 대해 재귀적인 분할 호출이 수행된다.
분할 알고리즘은 다음과 같다:

 **함수** split(T, k)
     **만약** (T = nil) **이면 반환** (nil, false, nil)
     (L, (m, c), R) = expose(T)
     **만약** (k = m) **이면 반환** (L, true, R)
     **만약** (k  m)
         (L', b, R') = split(R, k)
         **반환** (join(L, m, L'), b, R'))

집합 와 를 나타내는 두 트립 과 의 합집합은 를 나타내는 트립 이다. 다음 재귀 알고리즘은 합집합을 계산한다.

 **함수** union(t1, t2):
     **만약** t1 = nil:
         **반환** t2
     **만약** t2 = nil:
         **반환** t1
     **만약** priority(t1) 2):
         **교환** t1과 t2
     t, t> ← key(t1)에서 t2를 분할
     **반환** join(union(left(t1), t), key(t1),
                     union(right(t1), t>))

여기서 분할은 두 개의 트리를 반환하는 것으로 가정한다: 하나는 입력 키보다 작은 키를 포함하고, 다른 하나는 더 큰 키를 포함한다. (이 알고리즘은 비파괴적이지만, 제자리 파괴적 버전도 존재한다.)

교집합 알고리즘도 유사하지만, join 도우미 루틴이 필요하다. 합집합, 교집합, 차집합 각각의 복잡성은 크기 과 을 가진 트립의 경우 일 때 이다. 또한, 합집합에 대한 재귀 호출은 서로 독립적이므로 병렬로 실행될 수 있다.

Split과 Union은 Join을 호출하지만 트립의 균형 기준을 직접 다루지 않는다. 이러한 구현은 일반적으로 "join-based" 구현이라고 불린다.

키의 해시 값이 우선순위로 사용되고, 구조적으로 동일한 노드가 이미 생성 시 병합된다면, 각 병합된 노드는 키 집합의 고유한 표현이 될 것이다. 주어진 키 집합을 나타내는 동시 루트 노드가 하나만 있을 수 있다면, 두 집합은 포인터 비교를 통해 동일한지 테스트할 수 있으며, 이는 상수 시간이다.

이 기술은 두 집합 간의 차이가 작을 때에도 병합 알고리즘을 빠르게 수행하도록 향상시키는 데 사용될 수 있다. 입력 집합이 동일하다면, 합집합 및 교집합 함수는 즉시 입력 집합 중 하나를 결과로 반환하며 중단할 수 있고, 차집합 함수는 빈 집합을 반환해야 한다.

를 대칭 차이의 크기라고 하자. 수정된 병합 알고리즘은 로도 제한된다.

## 확률적 이진 탐색 트리
트립에 대한 아라곤과 자이델의 연구 이후 마르티네스와 로우라가 도입한 확률적 이진 탐색 트리는 동일한 노드를 동일한 무작위 트리 형태 분포로 저장하지만, 무작위 구조를 유지하기 위해 트리 노드 내에 다른 정보를 유지한다.

각 노드에 무작위 우선순위를 저장하는 대신, 확률적 이진 탐색 트리는 각 노드에 작은 정수(자신을 포함하여 자손의 수)를 저장한다. 이 숫자는 트리 회전 작업 중에 회전당 상수 추가 시간만으로 유지될 수 있다. n개의 노드를 이미 가진 트리에 키 x를 삽입해야 할 때, 삽입 알고리즘은 1/(n + 1)의 확률로 x를 트리의 새 루트로 배치하고, 그렇지 않으면 (키가 루트보다 작거나 큰지에 따라) x를 왼쪽 또는 오른쪽 서브트리에 삽입하기 위해 삽입 프로시저를 재귀적으로 호출한다. 자손의 수는 알고리즘에 의해 각 단계에서 무작위 선택에 필요한 확률을 계산하는 데 사용된다. 서브트리의 루트에 x를 배치하는 것은 트립에서와 같이 리프에 삽입한 다음 위로 회전시키거나, 마르티네스와 로우라가 설명한 대체 알고리즘으로 서브트리를 두 조각으로 분할하여 새 노드의 왼쪽 및 오른쪽 자식으로 사용하는 방식으로 수행할 수 있다.

확률적 이진 탐색 트리의 삭제 프로시저는 삽입 프로시저와 동일한 노드당 정보를 사용하지만, 삽입 프로시저와 달리 삭제된 노드의 왼쪽 및 오른쪽 자식에서 내려오는 두 서브트리를 하나의 트리로 결합하는 데 평균적으로 O(1) 무작위 결정만 필요하다. 이는 결합할 서브트리가 평균적으로 Θ(log n) 깊이에 있기 때문이다. 크기 n과 m의 두 트리를 결합하는 데는 평균적으로 Θ(log(n+m)) 무작위 결정이 필요하다. 삭제할 노드의 왼쪽 또는 오른쪽 서브트리가 비어 있으면 결합 작업은 사소하다. 그렇지 않으면 삭제된 노드의 왼쪽 또는 오른쪽 자식이 해당 자손 수에 비례하는 확률로 새 서브트리 루트로 선택되고, 결합은 재귀적으로 진행된다.

### 비교
확률적 이진 트리의 노드당 저장되는 정보는 트립보다 간단하지만(고정밀 난수 대신 작은 정수), 난수 생성기에 더 많은 호출을 한다(삽입당 한 번의 호출 대신 삽입 또는 삭제당 O(log n) 호출). 또한 삽입 프로시저는 노드당 자손 수를 업데이트해야 하므로 약간 더 복잡하다. 사소한 기술적 차이점은 트립에서 충돌(두 키가 동일한 우선순위를 얻는 것)의 작은 확률이 있고, 두 경우 모두 실제 난수 생성기와 디지털 컴퓨터에서 일반적으로 사용되는 유사 난수 생성기 사이에 통계적 차이가 있을 것이다. 그러나 어떤 경우에도 알고리즘 설계에 사용된 완벽한 무작위 선택의 이론적 모델과 실제 난수 생성기의 기능 사이의 차이는 미미하다.

트립과 무작위 이진 탐색 트리는 각 업데이트 후 트리의 형태가 동일한 무작위 분포를 가지지만, 일련의 삽입 및 삭제 작업에 의해 이 두 자료 구조가 수행한 트리의 수정 이력은 다를 수 있다. 예를 들어, 트립에서 숫자 1, 2, 3이 순서대로 1, 3, 2로 삽입된 다음 숫자 2가 삭제되면 남아 있는 두 노드는 중간 숫자가 삽입되기 전과 동일한 부모-자식 관계를 가질 것이다. 무작위 이진 탐색 트리에서는 삭제 후 트리는 두 노드에 대한 두 가지 가능한 트리 중 어느 하나가 될 가능성이 동일하며, 중간 숫자가 삽입되기 전 트리가 어떻게 생겼는지와는 독립적이다.

## 암시적 트립
암시적 트립은 일반 트립의 간단한 변형으로, O(\log n) 시간 내에 다음 연산을 지원하는 동적 배열로 볼 수 있다:

* 어떤 위치에든 요소 삽입
* 어떤 위치에서든 요소 제거
* 주어진 범위에서 합계, 최소 또는 최대 요소 찾기
* 주어진 범위에서 덧셈, 색칠
* 주어진 범위에서 요소 뒤집기

암시적 트립의 아이디어는 배열 인덱스를 키로 사용하지만 명시적으로 저장하지 않는 것이다. 그렇지 않으면 업데이트(삽입/삭제)로 인해 트리의 O(n) 노드에서 키가 변경될 수 있다.

노드 T의 키 값(**암시적 키**)은 해당 노드보다 작은 노드의 수에 1을 더한 값이다. 이러한 노드는 왼쪽 서브트리뿐만 아니라, T가 P의 오른쪽 서브트리에 있는 경우 P의 왼쪽 서브트리에도 존재할 수 있음을 유의하라.

따라서 트리를 내려가면서 모든 노드의 합을 누적하여 연산을 수행할 때 현재 노드의 암시적 키를 빠르게 계산할 수 있다. 이 합은 왼쪽 서브트리를 방문할 때는 변하지 않지만, 오른쪽 서브트리를 방문할 때는 cnt (T\rightarrow L)+1만큼 증가할 것임을 유의하라.

암시적 트립의 join 알고리즘은 다음과 같다:
```c
void join (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        join (l->r, l->r, r),  t = l;
    else
        join (r->l, l, r->l),  t = r;
    upd_cnt (t);
}
```


암시적 트립의 split 알고리즘은 다음과 같다:
```c
void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    int cur_key = add + cnt(t->l); //implicit key
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}
```


### 연산

#### 요소 삽입
요소를 pos 위치에 삽입하려면 **split** 함수를 호출하여 배열을 [0...pos-1]과 [pos..sz] 두 개의 하위 섹션으로 나누고 두 개의 트리 T1과 T2를 얻는다. 그런 다음 **join** 함수를 호출하여 T1을 새 노드와 병합한다. 마지막으로 **join** 함수를 호출하여 T1과 T2를 병합한다.

#### 요소 삭제
삭제할 요소를 찾고 해당 자식 L과 R에 대해 조인을 수행한다. 그런 다음 삭제할 요소를 조인 연산의 결과로 생성된 트리로 바꾼다.

#### 주어진 범위에서 합계, 최소 또는 최대 찾기
이 계산을 수행하려면 다음과 같이 진행한다:

* 먼저 추가 필드 F를 생성하여 해당 노드가 나타내는 범위에 대한 대상 함수의 값을 저장한다. 노드의 L 및 R 자식의 값을 기반으로 F 값을 계산하는 함수를 생성한다. 이 대상 함수는 트리를 수정하는 모든 함수(예: split 및 join)의 끝에서 호출할 것이다.
* 둘째, 주어진 범위 [A..B]에 대한 쿼리를 처리해야 한다: **split** 함수를 두 번 호출하여 트립을 \{1..A-1\}을 포함하는 T1, \{A..B\}를 포함하는 T2, 그리고 \{B+1..n\}를 포함하는 **<math>T3</math>**으로 분할할 것이다. 쿼리가 응답된 후 **join** 함수를 두 번 호출하여 원래 트립을 복원할 것이다.

#### 주어진 범위에서 덧셈/색칠
이 작업을 수행하려면 다음과 같이 진행한다:

* 서브트리에 추가된 값을 포함할 추가 필드 D를 생성한다. 이 변경 사항을 노드에서 자식으로 전파하는 데 사용될 **push** 함수를 생성한다. 이 함수는 트리를 수정하는 모든 함수(예: split 및 join)의 시작 부분에서 호출하여 트리 변경 후 정보가 손실되지 않도록 한다.

#### 주어진 범위에서 뒤집기
주어진 노드의 서브트리를 뒤집어야 함을 보여주기 위해 각 노드에 추가 부울 필드 R을 생성하고 값을 true로 설정한다. 이 변경 사항을 전파하려면 노드의 자식을 교환하고 모든 자식에 대해 R을 true로 설정한다.

## 같이 보기
* 핑거 검색
* 트립DB

## 각주

## 외부 링크

* 트립 참조 및 정보 모음 - 세실리아 아라곤
* 오픈 자료 구조 - 섹션 7.2 - 트립: 무작위 이진 탐색 트리, 팻 모린
* 애니메이션 트립
* 무작위 이진 탐색 트리. UIUC의 제프 에릭슨 강좌 노트. 제목에도 불구하고 주로 트립과 스킵 리스트에 대한 내용이며, 무작위 이진 탐색 트리는 간략하게만 언급된다.
* 트립 기반의 고성능 키-값 저장소 - Junyi Sun
* VB6 트립 구현. COM 개체로서의 VB6 트립 구현.
* 액션스크립트3 트립 구현
* 순수 파이썬 및 사이썬 인메모리 트립 및 듀플트립
* C#의 트립. 로이 클레먼스
* 순수 Go 언어 인메모리, 불변 트립
* 순수 Go 언어 영구 트립 키-값 저장 라이브러리

분류:이진 트리
분류:힙
분류:탐색 트리
분류:확률적 자료 구조