트레프

트레프
트레프
유형	랜덤화된 이진 검색 트리
큰 O 표기법에서의 시간 복잡성
알고리즘.
알고리즘.
공간
검색
삽입하다
삭제

컴퓨터 과학에서 traap과 임의의 바이너리 검색 트리는 순서의 동적 키 집합을 유지하고 키들 사이에서 이진 검색을 허용하는 이진 검색 트리 데이터 구조의 두 가지 밀접하게 관련된 형태다.키 삽입과 삭제의 순서가 모두 끝난 후, 트리의 모양은 임의의 이항 트리와 동일한 확률 분포를 갖는 랜덤 변수로서, 특히 높은 확률을 가진 트리의 높이는 키 수의 로그에 비례하므로, 각각의 검색, 삽입 또는 삭제 연산에 로그 시간이 소요된다.형체를 이루다

설명

영문자 키 및 숫자 최대 힙 순서가 있는 트리프

나무 꼭대기는 라이문트 세이델과 세실리아 R에 의해 처음 묘사되었다. 1989년 아라곤;^[1]^[2] 그것의 이름은 나무와 진흙으로 된 포트만테우 입니다.각 키에 (임의로 선택한) 숫자 우선 순위가 부여되는 데카르트 트리다.모든 이진 검색 트리와 마찬가지로 노드의 inorder traversal 순서는 키의 정렬 순서와 동일하다.트리 구조는 힙 순서 지정 요건에 의해 결정된다. 즉, 잎이 아닌 노드의 우선순위 번호가 하위 노드의 우선순위보다 크거나 같아야 한다.따라서 보다 일반적으로 카르테시아 나무와 마찬가지로 루트 노드는 최대 우선순위 노드로서, 그 노드의 왼쪽과 오른쪽으로 정렬된 순서의 하위 부분부터 동일한 방식으로 왼쪽과 오른쪽 하위 트리가 형성된다.

traap을 설명하는 동등한 방법은 리밸런싱을 하지 않고 가장 우선순위가 높은 노드를 바이너리 검색 트리에 삽입하여 구성할 수 있다는 것이다.따라서 우선순위가 독립된 무작위 숫자(두 노드의 우선순위가 동일하지 않을 가능성이 충분히 큰 우선 순위 공간에 대한 분포로부터)인 경우, 트레프의 모양은 무작위 이진 검색 트리의 모양과 동일한 확률 분포를 가지는데, 이 트리는 no를 삽입하여 형성된 검색 트리다.임의로 선택한 삽입 순서에 따라 재조정하지 않고 배치.랜덤 바이너리 검색 트리는 로그 높이에 확률이 높은 것으로 알려져 있기 때문에 트레프도 마찬가지다.이는 퀵소트가 $O(n\log n)$ O $O(n\log n)$ $O(n\log n)$ $){\displaystyle O(n\log n)}$ 시간 $O(n\log n)$ 내에 실행되는 이진 검색 트리 인수를 반영한다.바이너리 검색 트리가 정렬의 동적 문제 버전에 대한 해결책이라면, Treaps는 특히 우선순위가 피벗 선택을 안내하는 동적 퀵 소트에 대응한다.

아라곤과 세이델은 또한 자주 액세스하는 노드에 더 높은 우선순위를 할당하는 것을 제안한다. 예를 들어, 각 액세스에서 무작위 번호를 선택하고 이전 우선순위보다 높은 경우 노드의 우선순위를 그 번호로 대체하는 프로세스에 의해서 말이다.이러한 수정은 트리의 임의 모양을 잃게 할 것이다. 대신 자주 액세스하는 노드는 트리의 루트 근처에 있을 가능성이 높기 때문에 검색 속도가 더 빠를 것이다.

Naor와 Nisim은^[3] 공개키 암호 시스템의 승인 인증서 유지에 있어 응용 프로그램을 설명한다.

운영

기본 연산

Treaps는 다음과 같은 기본 작업을 지원한다.

지정된 키 값을 검색하려면 우선 순위를 무시하고 이진 검색 트리에서 표준 이진 검색 알고리즘을 적용하십시오.
새 키 x를 트레이에 삽입하려면 x에 대한 임의 우선 순위 y를 생성하십시오. 이진 검색은 트리에서 x를 검색하고 이진 검색이 x에 대한 노드가 있어야 한다고 결정하는 리프 위치에 새 노드를 생성하십시오.그런 다음 x가 트리의 루트가 아니고 상위 z보다 우선 순위가 큰 경우 x와 z 사이의 부모-자녀 관계를 반대로 하는 트리 회전을 수행한다.
traap에서 노드 x를 삭제하려면 x가 트리의 리프인 경우 간단히 제거하십시오.x에 하나의 자식 z가 있는 경우, 나무에서 x를 제거하고 x의 부모 자식(또는 x가 부모가 없는 경우 z를 나무의 루트)으로 만드십시오.마지막으로, x가 두 아이를 가진 경우, 정렬된 순서에서 바로 후계자 z의 위치와 트리에서의 위치를 교환하여 이전 사례 중 하나가 된다.이 마지막 경우 스왑이 z에 대한 힙 순서 지정 속성을 위반할 수 있으므로 이 속성을 복원하려면 추가 회전을 수행해야 할 수 있다.

나무 꼭대기 쌓기

traap을 구축하려면 각 값이 $O(\log n)$ $){\displaystyle$ O $(\log n)}$ 시간 $O(\log n)$ 걸리는 traap에 n개의 값을 삽입하면 된다.따라서 트레이는 목록 $O(n\log n)$ 에서 $O(n\log n)$ ( $O(n\log n)$ log $O(n\log n)$ $){\displaystyle O(n\log$ n $)}$ 시간 $O(n\log n)$ 내에 빌드될 수 있다.

대량 작업

단일 요소 삽입, 삭제 및 조회 작업 외에도 조합, 교차로 및 설정 차이와 같은 여러 가지 빠른 "대량" 작업이 트레프에서 정의되었다.이들은 분할 및 결합이라는 두 가지 도우미 작업에 의존한다.

trap을 키 x보다 작은 trap과 키 x보다 큰 trap 두 개로 분할하려면 trap에 있는 노드의 우선순위보다 큰 x를 최대 우선순위로 삽입하십시오.이 삽입 후 x는 treap의 루트 노드가 되며, x 미만의 모든 값은 왼쪽 하위 맵에서, x보다 큰 모든 값은 오른쪽 하위 맵에서 찾을 수 있다.이것은 나무 꼭대기에 한 번 삽입하는 것만큼의 비용이 든다.
이전의 스플릿의 산물인 두 개의 트랩에 결합하면, 첫 번째 트레프의 가장 큰 값이 두 번째 트레프의 가장 작은 값보다 작다고 안전하게 가정할 수 있다.x 값이 첫 번째 traap에서 이 최대값보다 크고 두 번째 traap에서 최소값보다 작도록 x 값을 가진 새 노드를 생성하고 최소 우선 순위를 지정한 다음 왼쪽 자식을 첫 번째 힙에, 오른쪽 자식을 두 번째 힙에 설정하십시오.필요에 따라 회전하여 힙 순서를 수정하십시오.그 후에는 리프 노드가 되어 쉽게 삭제할 수 있다.그 결과 두 개의 원래 트레프에서 하나의 트레프가 합병되었다.이것은 사실상 분할을 "해제"하는 것이며, 비용은 동일하다.보다 일반적으로 조인 작업은 임의의 우선 순위를 가진 두 개의 트레이와 키(즉, 가장 높을 필요는 없음)에서 작동할 수 있다.

T_{1}

T_{1}

T_{1}

{\

및

T_{2}

T_{2}

{\

조인 후

T_{1}

T_{1}

1

{\

}의 오른쪽 하위 항목 이전의 오른쪽 하위 항목과

T_{2}

T_{2}

{\

조인 알고리즘은 다음과 같다.

function join(L, k, R)     if prior(k, k(L)) and prior(k, k(R)) return Node(L, k, R)     if prior(k(L), k(R)) return Node(left(L), k(L), join(right(L), k, R))     return Node(join(L, k, left(R)), k(R), right(R))

T

T

을(를)

x

{\displaystyle x

으)로

T

분할하려면

T {\

displaystyle

T}의 왼쪽 또는 오른쪽 하위 중 하나에 재귀 분할 호출이 수행된다

T

분할 알고리즘은 다음과 같다.

function split(T, k)     if (T = nil) return (nil, false, nil)     (L, (m, c), R) = expose(T)     if (k = m) return (L, true, R)     if (k < m)          (L', b, R') = split(L, k)         return (L', b, join(R', m, R))     if (k > m)          (L', b, R') = split(R, k)         return (join(L, m, L'), b, R))

$두$ 개의 $triaps 1$ t와 $t$ 의₂ 조합으로, $a$ 와 b를 나타내는 triap $t$ 는 $a$ ∪ $B$ 를 나타낸다.다음의 재귀 알고리즘은 결합을 계산한다.

함수₁ 유니언(t₁₂, t): t = nil: t₂ = nil이면 t 반환₂₁: 우선순위(t₁) < 우선순위(t₂): swap t₁ 및_< t₂, 키_>(t₁₁_<), 키(t₁), 유니언(오른쪽(t₁), t) 반환 조인_>(t₂)

여기서, 분할은 입력키보다 키를 적게 쥐고 있는 나무와 더 큰 키를 쥐고 있는 나무 두 그루를 반환하는 것으로 추정된다.(알고리즘은 비파괴적이지만, 내부 파괴 버전도 존재한다.)

교차로 알고리즘은 유사하지만 조인 도우미 루틴이 필요하다.각 노조와 차이의 복잡성은 O(나 통나무 .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:0.크기 m와 엔의 m≤ n. 게다가와 treaps한 이후 조합에 재귀 호출은 서로 독립적이다, 그들은 병렬로 실행될 수 있0.1em}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}n/m cm이다.[4]

스플릿과 유니언은 조인(Join)을 부르지만 트레프의 균형 기준을 직접 다루지는 않으며, 이러한 구현을 보통 "조인 기반" 구현이라고 부른다.

키의 해시 값을 우선순위로 사용하고 구조적으로 동등한 노드가 이미 구성 중에 병합된 경우, 각 병합된 노드는 키 집합의 고유한 표현일 것이다.주어진 키 집합을 나타내는 동시 루트 노드가 하나만 있을 수 있다면, 두 세트는 시간에 따라 일정하게 포인터 비교에 의해 동일성을 시험할 수 있다.

이 기법은 병합 알고리즘을 강화하여 두 세트의 차이가 작을 때에도 빠르게 수행할 수 있다.입력 세트가 같을 경우 유니언과 교차로 기능은 결과적으로 입력 세트 중 하나를 즉시 반환하는 것을 중단할 수 있으며, 차이 함수는 빈 세트를 반환해야 한다.

$d$ 를 대칭 차이의 크기가 되게 하라.수정된 병합 알고리즘도 $O (d$ $log$ $n / d$ )로 제한된다 $.$ ^[5]^[6]

랜덤화된 이진 검색 트리

마르티네스와 루라가 트레프스의 아라곤과 세이델의 작업에 이어 선보인 무작위 바이너리 검색 트리는 트리 모양의 동일한 무작위 분포로 동일한 노드를 저장하지만, 무작위화된 구조를 유지하기 위해 나무의 노드 내에서 서로 다른 정보를 유지한다.^[7]

무작위화된 이진 검색 트리는 각 노드에 무작위 우선 순위를 저장하기 보다는 각 노드에 작은 정수, 즉 그 하위 노드의 수(자체를 하나로 계산함)를 저장하며, 이러한 숫자는 회전당 일정한 추가 시간만으로 트리 회전 작업 중에 유지될 수 있다.키 x를 이미 n개의 노드가 있는 트리에 삽입하려고 할 때 삽입 알고리즘은 확률 1/(n + 1)로 선택해서 x를 트리의 새 루트로 배치하고, 그 이외의 경우 삽입 절차를 재귀적으로 호출하여 왼쪽 또는 오른쪽 하위 트리 내에 x를 삽입한다(키 루트보다 작거나 큰지 여부에 따라 다름).알고리즘은 각 단계에서 무작위 선택에 필요한 확률을 계산하기 위해 후손 수를 사용한다.하위 트리의 뿌리에 x를 배치하는 것은 트랩에서와 같이 잎에 삽입한 다음 위쪽으로 회전시키거나, 또는 새로운 노드의 좌우 자식으로 사용하기 위해 하위 트리를 두 조각으로 분할하는 마르티네스와 루라가 설명한 대체 알고리즘에 의해 수행될 수 있다.

무작위화된 이진 검색 트리의 삭제 절차는 삽입 절차와 동일한 노드당 정보를 사용하지만, 삽입 절차와 달리 삭제된 노드의 왼쪽과 오른쪽 하위 트리에서 내려오는 두 하위 트리를 하나의 트리로 결합하기 위해서는 평균 O(1) 무작위 결정만 하면 된다.그 이유는 결합할 하위 트리는 평균 깊이 ((log n)에 속하기 때문이다. n과 m의 두 트리를 결합하면 평균 θ(log(n+m) 랜덤 선택이 필요하다.삭제할 노드의 왼쪽 또는 오른쪽 하위 트리가 비어 있으면 가입 연산은 사소한 것이고, 그렇지 않으면 삭제된 노드의 왼쪽 또는 오른쪽 하위 트리가 하위 트리에 비례하는 확률로 새로운 하위 트리 루트로 선택되어 재귀적으로 결합이 진행된다.

비교

무작위화된 이진수 트리에서 노드당 저장된 정보는 traap(정밀도가 높은 난수보다는 작은 정수)보다 단순하지만, 무작위 번호 생성기(O(log n) 호출은 삽입당 한 호출이 아니라 삽입 또는 삭제당 더 많이 발생하며, 삽입 절차는 약간 더 준수된다.노드당 하위 항목 수를 업데이트해야 하기 때문에 cate됨.사소한 기술적 차이점은, 한 번에 충돌할 가능성이 작다는 것(두 개의 키가 동일한 우선순위를 갖는 것)이며, 두 경우 모두 참 난수 발생기와 디지털 컴퓨터에서 일반적으로 사용되는 유사 난수 발생기 사이에 통계적 차이가 있을 것이다.그러나 어떤 경우에도 알고리즘 설계에 사용된 완벽한 무작위 선택의 이론적 모델과 실제 무작위 숫자 생성기의 성능 사이의 차이는 사라질 정도로 작다.

treap과 임의의 바이너리 검색 트리는 모두 업데이트 후 트리 모양의 랜덤 분포를 가지고 있지만, 이 두 데이터 구조에서 일련의 삽입 및 삭제 작업에서 수행한 트리의 수정 내역은 다를 수 있다.예를 들어 traap에서 숫자 1, 2, 3을 1, 3, 2의 순서로 삽입한 다음 숫자 2를 삭제하면 나머지 두 노드는 중간 번호를 삽입하기 전에 했던 것과 동일한 부모-자식 관계를 갖게 된다.임의의 바이너리 검색 트리에서 삭제 후 트리는 중간 숫자를 삽입하기 전에 트리가 어떻게 생겼는지와 독립적으로 두 노드에 있는 두 개의 가능한 트리 중 하나가 될 가능성이 동등하다.

암묵적 트레프

암묵적 traap은 일반적인 traap의 단순한 변화로, 다음과 같은 작업을 $O(\log n)$ 하는 동적 배열로 볼 수 있는 O ( $){\displaystyle O(\log$ n $O(\log n)$

원하는 위치에 요소 삽입
임의 위치에서 요소 제거
지정된 범위에서 합, 최소 또는 최대 요소 찾기
추가, 주어진 범위의 그림 그리기
지정된 범위의 후진 요소

암묵적인 traap 뒤에 있는 아이디어는 traap에 배열 요소의 지수를 저장하는 것이다.요소의 실제 값은 traap에 명시적으로 저장되지 않는다. 그렇지 않으면 업데이트(삽입/삭제)로 인해 $O(n)$ 의 O $O(n)$ ) ${\displaystyle$ O $(n)}$ 노드에서 $O(n)$ 키가 변경될 수 있으며 이는 매우 느리다.

노드 T의 키 값(임피셜 키)은 노드 + 1보다 적은 노드 수입니다.T가 P의 오른쪽 하위 트리에 있는 경우, 그러한 노드는 왼쪽 하위 트리뿐만 아니라 조상 P의 왼쪽 하위 트리에도 존재할 수 있다는 점에 유의하십시오.

따라서 우리는 트리를 내려오면서 모든 노드의 합계를 축적하여 연산을 수행하면서 현재 노드의 암묵적 키를 빠르게 계산할 수 있다.이 합계는 왼쪽 하위 트리를 방문할 때 변경되지 않지만 오른쪽 하위 트리를 방문할 $cnt(T\rightarrow L)+1$ 때 $cnt(T\rightarrow L)+1$ $cnt(T\rightarrow L)+1$ → $cnt(T\rightarrow L)+1$ ) $cnt(T\rightarrow L)+1$ + $cnt(T\rightarrow L)+1$ ${\displaystyle cnt(T\rightarrow$ L $)+1}$ 만큼 증가한다는 점에 유의하십시오.

암묵적 treap에 대한 조인 알고리즘은 다음과 같다.

공허하게 하다 합류하다 (핏템 & t, 핏템 l, 핏템 r) {     만일 (!l    !r)         t = l ? l : r;     다른 만일 (l->이전의 > r->이전의)         합류하다 (l->r, l->r, r),  t = l;     다른         합류하다 (r->l, l, r->l),  t = r;     upd_bufft (t); }

^[8] 암묵적 treap에 대한 분할 알고리즘은 다음과 같다.

공허하게 하다 갈라지다 (핏템 t, 핏템 & l, 핏템 & r, 인트로 핵심을, 인트로 덧셈을 = 0) {     만일 (!t)         돌아오다 공허하게 하다( l = r = 0 );     인트로 cur_key = 덧셈을 + 씨앤트(t->l); //키 설정     만일 (핵심을 <= cur_key)         갈라지다 (t->l, l, t->l, 핵심을, 덧셈을),  r = t;     다른         갈라지다 (t->r, t->r, r, 핵심을, 덧셈을 + 1 + 씨앤트(t->l)),  l = t;     upd_bufft (t); }

^[8]

운영

요소 삽입

위치 위치에 요소를 삽입하기 위해 분할 함수를 호출하여 어레이를 [0...pos-1]과 [pos..sz] 두 개의 하위 섹션으로 나누고 T $T1$ $T1$ 및 $T1$ T $T2$ ${\displaystyle T2$ }을 얻는다 $.$ 그런 다음 $T2$ 조인 함수를 호출하여 T $T1$ $T1$ 을 $T1$ 새 노드와 병합한다.마지막으로 조인 함수를 $T1$ 하여 T $T1$ 1 {\ $displaystyle T1$ }과 $T1$ T $T2$ ${\displaystyle$ T2}을(를 $)$ 병합하십시오 $T2$

요소 삭제

우리는 삭제될 원소를 찾고 그것의 자녀 L과 R에게 조인을 행한다.그런 다음 삭제될 요소를 결합 작업에서 발생한 트리로 교체한다.

지정된 범위에서 최소값 또는 최대값 합계 찾기

이 계산을 수행하기 위해 다음과 같이 진행한다.

먼저 우리는 그 노드로 대표되는 범위에 대한 목표함수의 값을 저장하기 위해 추가 필드 F를 만들 것이다.우리는 노드의 L과 R 하위들의 값에 기초하여 F 값을 계산하는 함수를 만들 것이다.우리는 트리를 수정하는 모든 기능, 즉 분할과 결합의 끝에서 이 목표함수를 부를 것이다.
둘째, 주어진 범위에 대한 쿼리를 처리해야 한다. [A..B]: 분할 함수를 두 번 호출하여 T $T1$ {\ $displaystyle T1$ $\{1..A-1\}$ $\{1..A-1\}$ 이 들어 있는 T $T1$ 1 ${\$ displaystyle T1 $})$ 으로 분할할 것이다 $\{1..A-1\}$ ${\displaystyle \{1..$ $A-1\},$ T $T2$ ${\displaystyle T2},$ $\{A..B\}$ { $\{A..B\}$ . $\{A..B\}$ $\{A$ 가 들어 $T2$ 있다. $B\},$ 및 $\{B+1..n\}$ { $\{B+1..n\}$ + $\{B+1..n\}$ 을 포함하는 $T3$ $T3$ 3 ${\displaystyle T3$ $\{B+1..n\}$ ${\displaystyle \{B+1..$ $n$ 조회가 응답된 후 조인 기능을 두 번 호출하여 원래 트레이를 복원한다.

주어진 범위의 추가/도장

이 작업을 수행하려면 다음과 같이 진행하십시오.

우리는 하위 트리에 대한 부가가치를 포함하는 추가 필드 D를 만들 것이다.우리는 이 변화를 노드에서 자식들에게 전파하는 데 사용될 기능 푸시를 만들 것이다.트리를 수정하는 모든 기능의 시작, 즉 트리 변경 후 정보가 손실되지 않도록 분할 및 결합하는 기능을 이 기능이라고 한다.

지정된 범위에서 역회전

주어진 노드의 하위 트리를 각 노드에 대해 되돌릴 필요가 있다는 것을 보여주기 위해 우리는 여분의 부울 필드 R을 생성하고 그 값을 true로 설정한다.이 변화를 전파하기 위해 우리는 노드의 자식들을 교환하고 그들 모두의 R을 true로 설정할 것이다.

참고 항목

핑거 검색

참조

^ Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees" (PDF), Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, pp. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1
^ Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees", Algorithmica, 16 (4/5): 464–497, doi:10.1007/s004539900061
^ Naor, M.; Nissim, K. (April 2000), "Certificate revocation and certificate update" (PDF), IEEE Journal on Selected Areas in Communications, 18 (4): 561–570, doi:10.1109/49.839932^{[permanent dead link]}.
^ Blelloch, Guy E.; Reid-Miller, Margaret (1998), "Fast set operations using treaps", Proc. 10th ACM Symp. Parallel Algorithms and Architectures (SPAA 1998), New York, NY, USA: ACM, pp. 16–26, doi:10.1145/277651.277660, ISBN 0-89791-989-0.
^ Liljenzin, Olle (2013). "Confluently Persistent Sets and Maps". arXiv:1301.3388. Bibcode:2013arXiv1301.3388L. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
^ GitHub의 혼합물 세트 및 지도
^ Martínez, Conrado; Roura, Salvador (1997), "Randomized binary search trees", Journal of the ACM, 45 (2): 288–323, doi:10.1145/274787.274812
^ ^a ^b ^c "Treap - Competitive Programming Algorithms". cp-algorithms.com. Retrieved 2021-11-21.

외부 링크

Cecilia Aragon의 Treap 참조 및 정보 수집
개방형 데이터 구조 - 섹션 7.2 - Treap: 임의의 바이너리 검색 트리, Pat Morin
애니메이션 트레프
임의 이진 검색 트리.UIUC의 Jeff Erickson의 강의 노트.제목에도 불구하고, 이것은 주로 트레프와 스킵 리스트에 관한 것이다; 임의의 바이너리 검색 트리는 단지 잠깐 언급될 뿐이다.
준이선 트랩을 기반으로 한 고성능 키밸류 스토어
VB6의 트리프 구현.Treaps를 COM 개체로 구현하는 시각적 기본 6
ActionScript3 traap 구현
Pure Python 및 Cython in-memory traap 및 duptreap
C#에 트레프스.By Roy Clemmons
Pure Go 인메모리, 불변의 트리플
Pure Go 영구 traap 키 가치 스토리지 라이브러리

[paper89-1] Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees" (PDF), Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, pp. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1

[paper96-2] Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees", Algorithmica, 16 (4/5): 464–497, doi:10.1007/s004539900061

[3] Naor, M.; Nissim, K. (April 2000), "Certificate revocation and certificate update" (PDF), IEEE Journal on Selected Areas in Communications, 18 (4): 561–570, doi:10.1109/49.839932^{[permanent dead link]}.

[4] Blelloch, Guy E.; Reid-Miller, Margaret (1998), "Fast set operations using treaps", Proc. 10th ACM Symp. Parallel Algorithms and Architectures (SPAA 1998), New York, NY, USA: ACM, pp. 16–26, doi:10.1145/277651.277660, ISBN 0-89791-989-0.

[5] Liljenzin, Olle (2013). "Confluently Persistent Sets and Maps". arXiv:1301.3388. Bibcode:2013arXiv1301.3388L. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

[Confluent_Sets_and_Maps-6] GitHub의 혼합물 세트 및 지도

[7] Martínez, Conrado; Roura, Salvador (1997), "Randomized binary search trees", Journal of the ACM, 45 (2): 288–323, doi:10.1145/274787.274812

[:0-8] "Treap - Competitive Programming Algorithms". cp-algorithms.com. Retrieved 2021-11-21.

[1]

[2]

[3]

[5]

[6]

[7]

[8]

v t 트리 데이터 구조
나무 검색 (이중 세트/관련 배열)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (최적) 이진 검색 춤 HTree 간격 오더통계 (좌편향) 빨강-검은색 희생양 스플레이 T 트레프 UB 무게균형
힙스	이진수 이항체 브로달 피보나치 좌익 페어링 스큐 판 엠드 보아스 약한
시도하다	씨트리 C-트리(압축 ADT) 해시 라딕스 접미사 3차 검색 X-fast Y-fast
공간 데이터 분할 트리	볼 BK BSP 카르테시안 힐베르트 R k-d(일반적으로 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 세그먼트 부사장 X
다른 나무들	커버 지수적 펜윅 손가락 프랙탈 트리 지수 퓨전 해시 캘린더 아이 디스턴스 케이애리 왼손잡이 우시블링 링크/컷 로그 구조 병합 머클 p q. 범위 SPQR 톱

Search

트레프

네임스페이스

더

목차

설명

운영