hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
트립 (자료 구조) 확률적 이진 탐색 트리
확률적 이진 탐색 트리의 삭제 프로시저는 삽입 프로시저와 동일한 노드당 정보를 사용하지만, 삽입 프로시저와 달리 삭제된 노드의 왼쪽 및 오른쪽 자식에서 내려오는 두 서브트리를 하나의 트리로 결합하는 데 평균적으로 O(1) 무작위 결정만 필요하다. 이는 결합할 서브트리가 평균적으로 Θ(log n) 깊이에 있기 때문이다. 크기 n과 m의 두 트리를 결합하는 데는 평균적으로 Θ(log(n+m)) 무작위 결정이 필요하다. 삭제할 노드의 왼쪽 또는 오른쪽 서브트리가 비어 있으면 결합 작업은 사소하다. 그렇지 않으면 삭제된 노드의 왼쪽 또는 오른쪽 자식이 해당 자손 수에 비례하는 확률로 새 서브트리 루트로 선택되고, 결합은 재귀적으로 진행된다.
트립 (자료 구조) 확률적 이진 탐색 트리
확률적 이진 트리의 노드당 저장되는 정보는 트립보다 간단하지만(고정밀 난수 대신 작은 정수), 난수 생성기에 더 많은 호출을 한다(삽입당 한 번의 호출 대신 삽입 또는 삭제당 O(log n) 호출). 또한 삽입 프로시저는 노드당 자손 수를 업데이트해야 하므로 약간 더 복잡하다. 사소한 기술적 차이점은 트립에서 충돌(두 키가 동일한 우선순위를 얻는 것)의 작은 확률이 있고, 두 경우 모두 실제 난수 생성기와 디지털 컴퓨터에서 일반적으로 사용되는 유사 난수 생성기 사이에 통계적 차이가 있을 것이다. 그러나 어떤 경우에도 알고리즘 설계에 사용된 완벽한 무작위 선택의 이론적 모델과 실제 난수 생성기의 기능 사이의 차이는 미미하다.
트립과 무작위 이진 탐색 트리는 각 업데이트 후 트리의 형태가 동일한 무작위 분포를 가지지만, 일련의 삽입 및 삭제 작업에 의해 이 두 자료 구조가 수행한 트리의 수정 이력은 다를 수 있다. 예를 들어, 트립에서 숫자 1, 2, 3이 순서대로 1, 3, 2로 삽입된 다음 숫자 2가 삭제되면 남아 있는 두 노드는 중간 숫자가 삽입되기 전과 동일한 부모-자식 관계를 가질 것이다. 무작위 이진 탐색 트리에서는 삭제 후 트리는 두 노드에 대한 두 가지 가능한 트리 중 어느 하나가 될 가능성이 동일하며, 중간 숫자가 삽입되기 전 트리가 어떻게 생겼는지와는 독립적이다.
트립 (자료 구조) 암시적 트립
암시적 트립은 일반 트립의 간단한 변형으로,  시간 내에 다음 연산을 지원하는 동적 배열로 볼 수 있다:
암시적 트립의 아이디어는 배열 인덱스를 키로 사용하지만 명시적으로 저장하지 않는 것이다. 그렇지 않으면 업데이트(삽입/삭제)로 인해 트리의  노드에서 키가 변경될 수 있다.
노드 T의 키 값(암시적 키)은 해당 노드보다 작은 노드의 수에 1을 더한 값이다. 이러한 노드는 왼쪽 서브트리뿐만 아니라, T가 P의 오른쪽 서브트리에 있는 경우 P의 왼쪽 서브트리에도 존재할 수 있음을 유의하라.
따라서 트리를 내려가면서 모든 노드의 합을 누적하여 연산을 수행할 때 현재 노드의 암시적 키를 빠르게 계산할 수 있다. 이 합은 왼쪽 서브트리를 방문할 때는 변하지 않지만, 오른쪽 서브트리를 방문할 때는 만큼 증가할 것임을 유의하라.
암시적 트립의 join 알고리즘은 다음과 같다:
트립 (자료 구조) 암시적 트립
암시적 트립의 split 알고리즘은 다음과 같다:
요소를 pos 위치에 삽입하려면 split 함수를 호출하여 배열을 [0...pos-1]과 [pos..sz] 두 개의 하위 섹션으로 나누고 두 개의 트리 과 를 얻는다. 그런 다음 join 함수를 호출하여 을 새 노드와 병합한다. 마지막으로 join 함수를 호출하여 과 를 병합한다.
삭제할 요소를 찾고 해당 자식 L과 R에 대해 조인을 수행한다. 그런 다음 삭제할 요소를 조인 연산의 결과로 생성된 트리로 바꾼다.
이 계산을 수행하려면 다음과 같이 진행한다:
이 작업을 수행하려면 다음과 같이 진행한다:
주어진 노드의 서브트리를 뒤집어야 함을 보여주기 위해 각 노드에 추가 부울 필드 R을 생성하고 값을 true로 설정한다. 이 변경 사항을 전파하려면 노드의 자식을 교환하고 모든 자식에 대해 R을 true로 설정한다.
판 엠데 보아스 트리
판 엠데 보아스 트리(van Emde Boas tree, nl), vEB 트리 또는 판 엠데 보아스 우선순위 큐라고도 알려진 이 자료 구조는 m-비트 정수 키를 사용하는 연관 배열을 구현하는 트리 자료 구조이다. 이 자료 구조는 네덜란드 컴퓨터 과학자 피터 판 엠데 보아스가 이끄는 팀에 의해 1975년에 발명되었다. 모든 연산은 O(log m) 시간(m 비트 연산이 상수 시간에 수행될 수 있다고 가정) 또는 동등하게  시간 안에 수행되며, 여기서 은 트리에 저장될 수 있는 가장 큰 원소이다. 매개변수 은 트리에 저장된 실제 원소의 수와 혼동되어서는 안 된다. 다른 트리 자료 구조의 성능은 종종 이 매개변수로 측정되기 때문이다.
표준 vEB 트리는 의 비효율적인 공간 효율성을 가진다. 예를 들어, 32비트 정수를 저장할 때(즉, 일 때)  비트의 저장 공간이 필요하다. 이를 해결하기 위해 vEB 트리를 수정하여  공간을 달성하거나, 동등한 점근 시간 효율성과  공간 효율성(여기서 은 저장된 원소의 수)을 가진 유사한 자료 구조를 사용할 수 있다.
판 엠데 보아스 트리 지원되는 연산
vEB는 일반적인 연관 배열 연산과 FindNext 및 FindPrevious라는 두 가지 추가 순서 연산을 포함하는 정렬된 연관 배열의 연산을 지원한다:
vEB 트리는 또한 Minimum 및 Maximum 연산을 지원하며, 이는 각각 트리에 저장된 최소 및 최대 원소를 반환한다. 최소 및 최대 원소는 각 트리에 속성으로 저장되므로 이 둘 모두  시간에 실행된다.
판 엠데 보아스 트리 기능
어떤 정수 에 대해 라고 하자. 으로 정의하자. 유니버스 에 걸친 vEB 트리 T는 길이 의 배열 T.children을 저장하는 루트 노드를 가진다. T.children[i]는 값 을 담당하는 vEB 트리 포인터이다. 또한 T는 두 값 T.min 및 T.max와 보조 vEB 트리 T.aux를 저장한다.
데이터는 vEB 트리에 다음과 같이 저장된다: 현재 트리에 있는 가장 작은 값은 T.min에 저장되고 가장 큰 값은 T.max에 저장된다. T.min은 vEB 트리의 다른 곳에 저장되지 않는 반면 T.max는 저장된다는 점에 유의한다. T가 비어 있다면 T.max=−1 및 T.min=M으로 간주한다. 다른 값 는 인 서브트리 T.children[i]에 저장된다. 보조 트리 T.aux는 어떤 자식이 비어 있지 않은지 추적하므로, T.children[j]가 비어 있지 않은 경우에만 T.aux는 값 를 포함한다.
판 엠데 보아스 트리 기능
vEB 트리에서 원소 x의 후속자를 검색하는 연산 FindNext(T, x)는 다음과 같이 진행된다: 만약 x<T.min이면 검색이 완료되고, 답은 T.min이다. 만약 x≥T.max이면 다음 원소가 존재하지 않으므로 M을 반환한다. 그렇지 않으면 라고 하자. 만약 x < T.children[i].max이면, 검색 중인 값은 T.children[i]에 포함되어 있으므로 검색은 T.children[i]에서 재귀적으로 진행된다. 그렇지 않으면, T.aux에서 값 i의 후속자를 검색한다. 이것은 x보다 큰 원소를 포함하는 첫 번째 서브트리의 인덱스 j를 제공한다. 그런 다음 알고리즘은 T.children[j].min을 반환한다. 자식 레벨에서 발견된 원소는 전체 다음 원소를 형성하기 위해 상위 비트와 결합되어야 한다.
어떤 경우에도 알고리즘은  작업을 수행한 다음 크기  (m/2 비트 유니버스)의 유니버스에 걸친 서브트리에서 재귀를 수행할 수 있다는 점에 유의한다. 이는 실행 시간에 대해 의 재귀 관계를 제공하며, 이는 으로 해결된다.
vEB 트리 T에 값 x를 삽입하는 호출 insert(T, x)는 다음과 같이 작동한다:
판 엠데 보아스 트리 기능
코드:
이 절차의 효율성에 대한 핵심은 빈 vEB 트리에 원소를 삽입하는 데 O(1) 시간이 걸린다는 것이다. 따라서 알고리즘이 때로는 두 번의 재귀 호출을 하더라도, 이는 첫 번째 재귀 호출이 빈 서브트리에 있었을 때만 발생한다. 이는 이전과 동일한 실행 시간 재귀 관계인 을 제공한다.
vEB 트리에서 삭제는 가장 까다로운 연산 중 하나이다. vEB 트리 T에서 값 x를 삭제하는 호출 Delete(T, x)는 다음과 같이 작동한다:
코드:
다시 한번, 이 절차의 효율성은 단 하나의 원소만 포함하는 vEB 트리에서 삭제하는 데 상수 시간만 걸린다는 사실에 달려 있다. 특히, 두 번째 Delete 호출은 삭제 이전에 x가 T.children[i]에 유일한 원소였을 때만 실행된다.
log m이 정수라는 가정은 불필요하다.  및  연산은 각각 x의 상위 ⌈m/2⌉ 비트와 하위 ⌊m/2⌋ 비트를 취함으로써 대체될 수 있다. 기존의 어떤 기계에서든 이것은 나눗셈 또는 나머지 계산보다 더 효율적이다.
판 엠데 보아스 트리 기능
실제 구현에서, 특히 k 시프트 및 첫 번째 0 찾기 명령을 가진 기계에서는 m이 워드 크기(또는 그 작은 배수)와 같아질 때 비트 배열로 전환함으로써 성능을 더욱 향상시킬 수 있다. 단일 워드에 대한 모든 연산은 상수 시간이므로 이는 점근적 성능에 영향을 미치지 않지만, 대부분의 포인터 저장 및 여러 포인터 역참조를 피하여 이 트릭으로 시간 및 공간에서 상당한 실질적인 절약을 달성한다.
vEB 트리의 최적화는 빈 서브트리를 폐기하는 것이다. 이는 vEB 트리가 많은 원소를 포함할 때 매우 컴팩트하게 만든다. 왜냐하면 어떤 것이 추가될 필요가 있을 때까지 서브트리가 생성되지 않기 때문이다. 초기에는 추가되는 각 원소가 약 log(m)개의 새로운 트리를 생성하며, 이들은 모두 합쳐서 약 m/2개의 포인터를 포함한다. 트리가 성장함에 따라 더 많은 서브트리가 재사용되며, 특히 큰 서브트리가 그렇다.
위에서 설명한 구현은 포인터를 사용하며, 키 유니버스의 크기에 비례하는 총 O(M) = O(2m) 공간을 차지한다. 이는 다음과 같이 볼 수 있다. 재귀 관계는 이다.
귀납법으로 S(M) = O(M)임을 보일 수 있다.
판 엠데 보아스 트리 유사한 구조
vEB 트리의 O(M) 공간 사용량은 키 유니버스의 큰 부분이 저장되지 않는 한 엄청난 오버헤드이다. 이것이 vEB 트리가 실제로 인기가 없는 이유 중 하나이다. 이 제한은 자식을 저장하는 데 사용되는 배열을 다른 자료 구조로 변경함으로써 해결될 수 있다. 한 가지 가능성은 각 레벨당 고정된 수의 비트만 사용하는 것으로, 이는 트라이 (컴퓨팅)로 이어진다. 또는 각 배열을 해시 테이블로 대체하여 공간을 O(n log log M)로 줄일 수 있다(여기서 n은 자료 구조에 저장된 원소의 수) 이 경우 자료 구조는 무작위화된다.
x-고속 트라이와 더 복잡한 y-고속 트라이는 vEB 트리와 유사한 업데이트 및 쿼리 시간을 가지며, 무작위 해시 테이블을 사용하여 사용되는 공간을 줄인다. x-고속 트라이는 O(n log M) 공간을 사용하는 반면, y-고속 트라이는 O(n) 공간을 사용한다.
판 엠데 보아스 트리 유사한 구조
융합 트리는 유한 유니버스에서 w-비트 정수에 대한 연관 배열을 구현하는 또 다른 유형의 트리 자료 구조이다. 이들은 워드 수준 병렬 처리 및 비트 조작 기술을 사용하여 선행자/후속자 쿼리 및 업데이트에 대해 O(logw n) 시간을 달성한다. 여기서 w는 워드 크기이다. 융합 트리는 O(n) 공간을 사용하며 해싱 또는 지수 트리를 사용하여 동적으로 만들 수 있다.
판 엠데 보아스 트리 구현
이사벨 (증명 보조기)에 검증된 구현이 있다. 기능적 정확성과 시간 경계 모두 증명되었다.
효율적인 명령형 표준 ML 코드를 생성할 수 있다.
기수 트리
컴퓨터 과학에서 기수 트리, 래딕스 트리(radix tree) 또는 기수 트라이(radix trie) 또는 압축 접두사 트리(compact prefix tree) 또는 압축 트라이(compressed trie)는 유일한 자식인 각 노드가 부모와 병합되는 공간 최적화된 트라이 (접두사 트리)를 나타내는 자료 구조이다. 그 결과 모든 내부 노드의 자식 수는 기수 트리의 기수 r 이하이며, 여기서 r = 2x (일부 정수 x ≥ 1). 일반 트리와 달리 엣지는 단일 요소뿐만 아니라 요소 시퀀스로도 레이블을 지정할 수 있다. 이로 인해 기수 트리는 작은 집합 (특히 문자열이 긴 경우) 및 긴 접두사를 공유하는 문자열 집합에 훨씬 더 효율적이다.
기수 트리
일반 트리(전체 키가 불일치 지점까지 시작부터 한꺼번에 비교됨)와 달리, 각 노드의 키는 비트 덩어리별로 비교되며, 해당 노드의 해당 덩어리에 있는 비트의 양은 기수 트라이의 기수 r이다. r이 2일 때, 기수 트라이는 이진(즉, 해당 노드의 키의 1비트 부분을 비교)이며, 이는 트라이 깊이를 최대화하는 대신 희소성을 최소화한다. 즉, 키에서 분기하지 않는 비트 문자열의 혼동까지 최대화한다. r ≥ 4가 2의 거듭제곱일 때, 기수 트라이는 r-진 트라이이며, 이는 잠재적 희소성을 희생하여 기수 트라이의 깊이를 줄인다.
최적화로서, 엣지 레이블은 문자열에 대한 두 개의 포인터(첫 번째 및 마지막 요소용)를 사용하여 상수 크기로 저장할 수 있다.
이 문서의 예시에서는 문자열을 문자 시퀀스로 보여주지만, 문자열 요소의 유형은 임의로 선택할 수 있다. 예를 들어, 멀티바이트 문자 인코딩 또는 유니코드를 사용할 때 문자열 표현의 비트 또는 바이트로 선택할 수 있다.
기수 트리 응용 분야
기수 트리는 문자열로 표현할 수 있는 키를 가진 연관 배열을 구성하는 데 유용하다. 이들은 IP 라우팅 영역에서 특히 응용된다. 여기서 몇 가지 예외를 제외하고 광범위한 값을 포함할 수 있는 능력은 IP 주소의 계층적 구성에 특히 적합하다. 또한 정보 검색에서 텍스트 문서의 역색인에도 사용된다.
기수 트리 연산
기수 트리는 삽입, 삭제 및 검색 연산을 지원한다. 삽입은 트리에 새 문자열을 추가하면서 저장되는 데이터 양을 최소화하려고 시도한다. 삭제는 트리에서 문자열을 제거한다. 검색 연산에는 (반드시 제한되지는 않지만) 정확한 조회, 선행 요소 찾기, 후행 요소 찾기 및 접두사가 있는 모든 문자열 찾기가 포함된다. 이 모든 연산은 O(k)이며, 여기서 k는 집합의 모든 문자열의 최대 길이이고, 길이는 기수 트라이의 기수와 동일한 비트 수로 측정된다.
조회 연산은 트라이에 문자열이 존재하는지 확인한다. 대부분의 연산은 특정 작업을 처리하기 위해 이 접근 방식을 어떤 식으로든 수정한다. 예를 들어, 문자열이 끝나는 노드가 중요할 수 있다. 이 연산은 일부 엣지가 여러 요소를 소비한다는 점을 제외하고 트라이와 유사하다.
다음 의사 코드는 이러한 메서드와 멤버가 존재한다고 가정한다.
엣지
노드
기수 트리 연산
문자열을 삽입하려면 더 이상 진행할 수 없을 때까지 트리를 검색한다. 이 시점에서 우리는 입력 문자열의 나머지 모든 요소로 레이블이 지정된 새 나가는 엣지를 추가하거나, 나머지 입력 문자열과 접두사를 공유하는 나가는 엣지가 이미 있는 경우, 이를 두 개의 엣지(처음 것은 공통 접두사로 레이블 지정됨)로 분할하고 진행한다. 이 분할 단계는 어떤 노드도 가능한 문자열 요소보다 많은 자식을 갖지 않도록 보장한다.
삽입의 여러 경우가 아래에 나와 있다. r은 단순히 루트를 나타낸다. 엣지는 필요한 경우 문자열을 종료하기 위해 빈 문자열로 레이블을 지정할 수 있으며 루트에는 들어오는 엣지가 없다고 가정한다. (위에서 설명한 조회 알고리즘은 빈 문자열 엣지를 사용할 때 작동하지 않는다.)
트리에서 문자열 x를 삭제하려면 먼저 x를 나타내는 리프를 찾는다. 그런 다음 x가 존재한다고 가정하고 해당 리프 노드를 제거한다. 리프 노드의 부모에게 다른 자식이 하나만 있는 경우 해당 자식의 들어오는 레이블이 부모의 들어오는 레이블에 추가되고 자식이 제거된다.
기수 트리 역사
이 자료 구조는 1968년 도널드 모리슨과 게르노트 그베헨베르거가 발명했으며, 주로 모리슨과 관련이 있다.
도널드 커누스는 《컴퓨터 프로그래밍의 예술》 3권 498-500페이지에서 이들을 "패트리샤의 트리"라고 불렀는데, 이는 모리슨 논문의 제목에 있는 약어("PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric")에서 따온 것으로 추정된다. 오늘날 패트리샤 트리는 기수가 2인 기수 트리로 간주된다. 즉, 키의 각 비트가 개별적으로 비교되고 각 노드는 양방향(즉, 왼쪽 대 오른쪽) 분기이다.
기수 트리 다른 자료 구조와의 비교
(다음 비교에서는 키의 길이가 k이고 자료 구조에 n개의 멤버가 있다고 가정한다.)
균형 트리와 달리 기수 트리는 O(log n) 시간 대신 O(k) 시간에 조회, 삽입 및 삭제를 허용한다. 이는 일반적으로 k ≥ log n이므로 장점처럼 보이지 않지만, 균형 트리에서는 모든 비교가 O(k) 최악의 시간 복잡도를 요구하는 문자열 비교이며, 이 중 많은 부분이 긴 공통 접두사(비교가 문자열의 시작 부분에서 시작하는 경우) 때문에 실제로는 느리다. 트라이에서는 모든 비교가 상수 시간을 요구하지만, 길이가 m인 문자열을 조회하는 데 m번의 비교가 필요하다. 기수 트리는 더 적은 비교로 이러한 연산을 수행할 수 있으며, 훨씬 더 적은 노드를 요구한다.
기수 트리 다른 자료 구조와의 비교
그러나 기수 트리는 트라이의 단점도 공유한다. 요소 문자열 또는 문자열로 효율적으로 가역적으로 매핑되는 요소에만 적용될 수 있으므로, 전순서를 가진 모든 데이터 형식에 적용되는 균형 탐색 트리의 완전한 일반성이 부족하다. 문자열로의 가역 매핑은 균형 탐색 트리에 필요한 전순서를 생성하는 데 사용될 수 있지만, 그 반대는 불가능하다. 이는 데이터 형식이 비교 연산만 제공하고 (역)직렬화 연산은 제공하지 않는 경우에도 문제가 될 수 있다.
해시 테이블은 일반적으로 예상 O(1) 삽입 및 삭제 시간을 갖는다고 하지만, 이는 키의 해시 계산을 상수 시간 연산으로 간주할 때만 해당된다. 키 해싱을 고려하면 해시 테이블은 예상 O(k) 삽입 및 삭제 시간을 가지지만, 충돌 처리 방식에 따라 최악의 경우 더 오래 걸릴 수 있다. 기수 트리는 최악의 경우 O(k) 삽입 및 삭제를 갖는다. 기수 트리의 후행/선행 연산은 해시 테이블에서 구현되지 않는다.
기수 트리 변형
기수 트리의 일반적인 확장은 "검정"과 "흰색"의 두 가지 노드 색상을 사용한다. 주어진 문자열이 트리에 저장되어 있는지 확인하려면 맨 위에서부터 검색을 시작하여 더 이상 진행할 수 없을 때까지 입력 문자열의 엣지를 따라간다. 검색 문자열이 소모되고 최종 노드가 검정 노드이면 검색이 실패한 것이다. 흰색이면 검색이 성공한 것이다. 이를 통해 공통 접두사를 가진 광범위한 문자열을 흰색 노드를 사용하여 트리에 추가한 다음, 검정 노드를 사용하여 작은 예외 집합을 공간 효율적인 방식으로 제거할 수 있다.
HAT-트라이는 기수 트리를 기반으로 하는 캐시 인식 자료 구조로, 효율적인 문자열 저장 및 검색, 그리고 순서 있는 반복을 제공한다. 시간과 공간 모두에서 성능은 캐시 인식 해시 테이블과 비교할 만하다.
기수 트리 변형
PATRICIA 트라이는 기수 2(이진) 트라이의 특수 변형으로, 모든 키의 모든 비트를 명시적으로 저장하는 대신, 노드는 두 하위 트리를 구별하는 첫 번째 비트의 위치만 저장한다. 순회 동안 알고리즘은 검색 키의 인덱싱된 비트를 검사하고 적절하게 왼쪽 또는 오른쪽 하위 트리를 선택한다. PATRICIA 트라이의 주목할 만한 특징은 저장된 고유 키마다 하나의 노드만 삽입하면 되므로 PATRICIA가 표준 이진 트라이보다 훨씬 더 간결하다는 것이다. 또한 실제 키가 더 이상 명시적으로 저장되지 않으므로 일치 여부를 확인하기 위해 인덱싱된 레코드에 대해 전체 키 비교를 한 번 수행해야 한다. 이러한 점에서 PATRICIA는 해시 테이블을 사용한 인덱싱과 특정 유사성을 가진다.
적응형 기수 트리는 기수 트리에 적응형 노드 크기를 통합한 기수 트리 변형이다. 일반적인 기수 트리의 주요 단점 중 하나는 모든 레벨에서 일정한 노드 크기를 사용하기 때문에 공간 사용이다. 기수 트리와 적응형 기수 트리의 주요 차이점은 자식 요소의 수에 따라 각 노드의 크기가 가변적이며, 새 항목을 추가할 때 크기가 증가한다는 것이다. 따라서 적응형 기수 트리는 속도를 줄이지 않고 공간을 더 효율적으로 사용한다.
일반적인 관행은 부모가 데이터 집합에서 유효한 키를 나타내는 상황에서 자식이 하나만 있는 부모를 허용하지 않는 기준을 완화하는 것이다. 이 변형 기수 트리는 적어도 두 개 이상의 자식을 가진 내부 노드만 허용하는 것보다 더 높은 공간 효율성을 달성한다.
접미사 트리
컴퓨터 과학에서 접미사 트리, 서픽스 트리(suffix tree), PAT 트리 또는 이전 형태로는 위치 트리(position tree)는 주어진 텍스트의 모든 접미사를 키로, 텍스트 내 위치를 값으로 포함하는 압축된 트라이이다. 접미사 트리는 많은 중요한 문자열 연산을 특히 빠르게 구현할 수 있게 한다.
문자열 에 대한 이러한 트리의 구성은 의 길이에 비례하는 시간과 공간을 차지한다. 일단 구성되면, 에서 서브스트링을 찾거나, 특정 수의 오류가 허용될 경우 서브스트링을 찾거나, 정규 표현식 패턴에 대한 일치를 찾는 것과 같은 여러 연산을 빠르게 수행할 수 있다. 접미사 트리는 또한 최장 공통 부분 문자열 문제에 대한 최초의 선형 시간 솔루션 중 하나를 제공했다. 이러한 속도 향상은 비용을 수반한다. 문자열의 접미사 트리를 저장하는 것은 일반적으로 문자열 자체를 저장하는 것보다 훨씬 더 많은 공간을 필요로 한다.
접미사 트리 역사
이 개념은 Weiner (1973)에 의해 처음 소개되었다.
위너는 접미사  대신, 그의 트라이에 각 위치에 대한 접두사 식별자를 저장했다. 즉, 에서 시작하여 에 한 번만 나타나는 가장 짧은 문자열이다. 그의 알고리즘 D는 에 대한 비압축 트라이를 받아 에 대한 트라이로 확장한다. 이러한 방식으로, 에 대한 자명한 트라이에서 시작하여, 번의 알고리즘 D의 연속적인 호출로 에 대한 트라이를 구축할 수 있다. 그러나 전체 실행 시간은 이다. 위너의 알고리즘 B는 구성된 트라이의 크기에 비례하는 전체 실행 시간을 달성하기 위해 여러 보조 데이터 구조를 유지한다. 후자는 의 경우처럼 여전히  노드가 될 수 있다. 위너의 알고리즘 C는 최종적으로 압축된 트라이를 사용하여 선형 전체 저장 공간 및 실행 시간을 달성한다.
도널드 커누스는 나중에 후자를 그의 학생인 본 프랫에 따르면 "1973년의 알고리즘"으로 특징지었다.
Aho, Hopcroft & Ullman (1974, Sect.9.5) 교과서는 위너의 결과를 단순하고 더 우아한 형태로 재현하며, 위치 트리(position tree)라는 용어를 도입했다.
접미사 트리 역사
McCreight (1976)는 의 모든 접미사에 대한 (압축된) 트라이를 구축한 최초의 인물이었다. 에서 시작하는 접미사는 일반적으로 접두사 식별자보다 길지만, 압축된 트라이에서 이들의 경로 표현은 크기가 다르지 않다. 반면에 McCreight는 위너의 보조 데이터 구조 대부분을 없앨 수 있었고, 접미사 링크만 남았다.
Ukkonen (1995)는 구성을 더욱 단순화했다. 그는 현재 우코넨 알고리즘으로 알려진, 당시 가장 빠른 알고리즘과 실행 시간이 일치하는 접미사 트리의 최초 온라인 구성을 제공했다.
이러한 알고리즘은 모두 상수 크기 알파벳에 대해 선형 시간이며, 일반적으로 최악의 경우 의 실행 시간을 가진다.
Farach (1997)는 모든 알파벳에 대해 최적의 접미사 트리 구성 알고리즘을 제시했다. 특히, 이는 다항 범위의 정수 알파벳에서 파생된 문자열에 대한 최초의 선형 시간 알고리즘이다. Farach의 알고리즘은 외부 메모리, 압축, 간결한 접미사 트리 및 접미사 배열을 구성하기 위한 새로운 알고리즘의 기반이 되었다.
접미사 트리 정의
길이 인 문자열 에 대한 접미사 트리는 다음과 같은 트리로 정의된다.
의 한 접미사가 다른 접미사의 접두사이기도 한 경우, 해당 문자열에 대한 이러한 트리는 존재하지 않는다. 예를 들어, 문자열 abcbc에서 접미사 bc는 접미사 bcbc의 접두사이기도 하다. 이러한 경우, bc를 나타내는 경로는 리프에서 끝나지 않아 다섯 번째 규칙을 위반한다. 이 문제를 해결하기 위해 는 문자열에 나타나지 않는 터미널 기호(일반적으로 $로 표시됨)로 채워진다. 이렇게 하면 어떤 접미사도 다른 접미사의 접두사가 되지 않으며, 의 개 접미사 각각에 대해 개의 리프 노드가 존재한다. 모든 내부 비루트 노드는 분기하므로, 이러한 노드는 최대 개가 있을 수 있으며, 총 개의 노드(개의 리프, 개의 내부 비루트 노드, 1개의 루트)가 있다.
접미사 트리 정의
접미사 링크는 이전의 선형 시간 구성 알고리즘의 핵심 기능이지만, Farach's algorithm을 기반으로 하는 대부분의 새로운 알고리즘은 접미사 링크를 사용하지 않는다. 완전한 접미사 트리에서 모든 내부 비루트 노드는 다른 내부 노드로의 접미사 링크를 가진다. 루트에서 노드까지의 경로가 문자열 를 나타내고, 여기서 는 단일 문자이고 는 문자열(비어 있을 수 있음)인 경우, 해당 노드는 를 나타내는 내부 노드로의 접미사 링크를 가진다. 예를 들어, 위 그림에서 ANA 노드에서 NA 노드로의 접미사 링크를 참조하라. 접미사 링크는 트리에서 실행되는 일부 알고리즘에서도 사용된다.
일반화된 접미사 트리는 단일 문자열 대신 문자열 집합을 위해 만들어진 접미사 트리이다. 이는 이 문자열 집합의 모든 접미사를 나타낸다. 각 문자열은 다른 종료 기호로 끝나야 한다.
접미사 트리 기능
길이 인 문자열 에 대한 접미사 트리는 문자가 다항 범위의 정수 알파벳에서 오는 경우  시간에 구축할 수 있다(특히 상수 크기 알파벳의 경우).
더 큰 알파벳의 경우, 실행 시간은 문자를  크기 범위로 가져오기 위해 먼저 정렬하는 데 지배된다. 일반적으로 이는  시간이 걸린다.
아래 비용은 알파벳이 상수라는 가정하에 주어진다.
길이 인 문자열 에 대한 접미사 트리가 구축되었거나, 총 길이 인 문자열 집합 에 대한 일반화된 접미사 트리가 구축되었다고 가정하자.
다음 작업을 수행할 수 있다:
문자열 검색:
길이 인 문자열 가  시간 내에 부분 문자열인지 확인한다.
총 길이 인 패턴 의 첫 번째 발생을  시간 내에 부분 문자열로 찾는다.
총 길이 인 패턴 의 모든 개 발생을  시간 내에 부분 문자열로 찾는다.

정규 표현식 P를 에 대해 하위 선형으로 예상되는 시간 내에 검색한다.
패턴 의 각 접미사에 대해 의 접두사와 의 부분 문자열 간의 가장 긴 일치 길이를  시간 내에 찾는다. 이를 에 대한 매칭 통계라고 한다.
접미사 트리 기능
문자열의 속성 찾기:
문자열 와 의 최장 공통 부분 문자열을  시간 내에 찾는다.
모든 maximal pairs, 최대 반복 또는 슈퍼최대 반복을  시간 내에 찾는다.
렘펠-지프 분해를  시간 내에 찾는다.
최장 반복 부분 문자열을  시간 내에 찾는다.
최소 길이의 가장 자주 나타나는 부분 문자열을  시간 내에 찾는다.
에서 에 나타나지 않는 가장 짧은 문자열을 개의 문자열이 있는 경우  시간 내에 찾는다.
한 번만 나타나는 가장 짧은 부분 문자열을  시간 내에 찾는다.
각 에 대해 의 다른 에 나타나지 않는 가장 짧은 부분 문자열을  시간 내에 찾는다.
접미사 트리는 노드 간의 상수 시간 최소 공통 조상 검색을 위해  시간 내에 준비될 수 있다. 그러면 다음 작업도 수행할 수 있다.
접미사 트리 응용 분야
접미사 트리는 텍스트 편집, 자유 텍스트 검색, 계산생물학 및 기타 응용 분야에서 발생하는 많은 문자열 문제를 해결하는 데 사용될 수 있다. 주요 응용 분야는 다음과 같다.
접미사 트리는 생물정보학 응용 분야에서 DNA 또는 단백질 서열(긴 문자열로 간주될 수 있음)에서 패턴을 검색하는 데 자주 사용된다. 불일치를 효율적으로 검색하는 능력은 가장 큰 강점으로 간주될 수 있다. 접미사 트리는 데이터 압축에도 사용된다. 반복되는 데이터를 찾는 데 사용될 수 있으며, 버로우즈-휠러 변환의 정렬 단계에 사용될 수 있다. LZW 압축 방식의 변형은 접미사 트리를 사용한다(LZSS). 접미사 트리는 또한 일부 검색 엔진에서 사용되는 데이터 클러스터링 알고리즘인 접미사 트리 클러스터링에도 사용된다.
접미사 트리 구현
각 노드와 엣지를  공간으로 표현할 수 있다면, 전체 트리는  공간으로 표현될 수 있다. 트리 내 모든 엣지의 모든 문자열 길이의 총합은 이지만, 각 엣지는 S의 부분 문자열의 위치와 길이로 저장될 수 있어 총 공간 사용량은  컴퓨터 워드가 된다. 접미사 트리의 최악의 공간 사용량은 피보나치 워드에서 볼 수 있으며, 전체  노드를 제공한다.
접미사 트리를 구현할 때 중요한 선택은 노드 간의 부모-자식 관계이다. 가장 일반적인 방법은 형제 리스트라고 불리는 연결 리스트를 사용하는 것이다. 각 노드는 첫 번째 자식에 대한 포인터와 자신이 속한 자식 리스트의 다음 노드에 대한 포인터를 가진다. 효율적인 실행 시간 속성을 가진 다른 구현은 해시 맵, 정렬되거나 정렬되지 않은 배열 (배열 두 배 확장과 함께), 또는 균형 탐색 트리를 사용한다. 우리는 다음에 관심이 있다.
접미사 트리 구현
σ를 알파벳의 크기라고 하자. 그러면 다음과 같은 비용이 발생한다.
삽입 비용은 상각되며, 해싱 비용은 완전 해싱에 대해 주어진다.
각 엣지와 노드의 방대한 정보로 인해 접미사 트리는 매우 비싸며, 좋은 구현에서는 원본 텍스트 메모리 크기의 약 10~20배를 소비한다. 접미사 배열은 이 요구 사항을 8배로 줄인다(32비트 주소 공간과 8비트 문자로 구축된 LCP 값을 포함하는 배열의 경우). 이 인자는 속성에 따라 다르며 32비트 시스템에서 4바이트 너비의 문자(일부 유닉스 계열 시스템에서 모든 기호를 포함하는 데 필요하며, wchar_t 참조)를 사용할 경우 2에 도달할 수 있다. 연구자들은 더 작은 인덱싱 구조를 계속 찾아왔다.
접미사 트리 병렬 구성
접미사 트리 구성 속도를 높이기 위한 다양한 병렬 알고리즘이 제안되었다.
최근에는  작업 (순차 시간)과  스팬을 가진 접미사 트리 구성을 위한 실용적인 병렬 알고리즘이 개발되었다. 이 알고리즘은 공유 메모리 멀티코어 머신에서 좋은 병렬 확장성을 달성하며, 40코어 머신을 사용하여 인간 유전체 – 약 3GB –를 3분 이내에 인덱싱할 수 있다.
접미사 트리 외부 구성
접미사 트리의 메모리 사용량은 선형적이지만 실제 시퀀스 컬렉션의 크기보다 상당히 크다. 큰 텍스트의 경우 구성에 외부 메모리 접근 방식이 필요할 수 있다.
외부 메모리에서 접미사 트리를 구성하는 이론적 결과가 있다.
Farach-Colton, Ferragina & Muthukrishnan (2000)의 알고리즘은 정렬과 동일한 I/O 복잡도를 가지므로 이론적으로 최적이다.
그러나 이 알고리즘의 전체적인 복잡성으로 인해 지금까지 실용적인 구현이 이루어지지 못했다.
반면에, (몇) GB/시간으로 확장 가능한 디스크 기반 접미사 트리를 구성하기 위한 실제 작업이 있었다.
최신 방법은 TDD,
TRELLIS,
DiGeST,
및
B2ST이다.
TDD와 TRELLIS는 전체 인간 유전체까지 확장되어 수십 기가바이트 크기의 디스크 기반 접미사 트리를 생성한다. 그러나 이러한 방법은 3GB를 초과하는 시퀀스 컬렉션을 효율적으로 처리할 수 없다. DiGeST는 훨씬 더 나은 성능을 보이며 약 6시간 내에 약 6GB 크기의 시퀀스 컬렉션을 처리할 수 있다.
접미사 트리 외부 구성
이러한 모든 방법은 트리가 주 메모리에 맞지 않지만 입력은 맞는 경우에 접미사 트리를 효율적으로 구축할 수 있다.
가장 최근의 방법인 B2ST는 주 메모리에 맞지 않는 입력을 처리할 수 있도록 확장된다. ERA는 훨씬 빠른 최근 병렬 접미사 트리 구성 방법이다. ERA는 16GB RAM이 장착된 8코어 데스크톱 컴퓨터에서 19분 만에 전체 인간 유전체를 인덱싱할 수 있다. 16개 노드(노드당 4GB RAM)가 있는 단순한 Linux 클러스터에서 ERA는 9분 이내에 전체 인간 유전체를 인덱싱할 수 있다.
접미사 트리 각주
Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), 《The Design and Analysis of Computer Algorithms》, Reading/MA: Addison-Wesley, Bibcode:1974daca.book.....A, ISBN 0-201-00029-6 .
Apostolico, A.; Iliopoulos, C.; Landau, G. M.; Schieber, B.; Vishkin, U. (1988), “Parallel construction of a suffix tree with applications”, 《Algorithmica》 3 (1–4): 347–365, doi:10.1007/bf01762122, S2CID 5024136 .
접미사 트리 각주
Baeza-Yates, Ricardo A.; Gonnet, Gaston H. (1996), “Fast text searching for regular expressions or automaton searching on tries”, 《Journal of the ACM》 43 (6): 915–936, doi:10.1145/235809.235810, S2CID 1420298 .
Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2008), 〈A new method for indexing genomes using on-disk suffix trees〉, 《CIKM '08: Proceedings of the 17th ACM Conference on Information and Knowledge Management》 (PDF), New York, NY, USA: ACM, 649–658쪽 .
접미사 트리 각주
Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2009), 〈Suffix trees for very large genomic sequences〉, 《CIKM '09: Proceedings of the 18th ACM Conference on Information and Knowledge Management》 (PDF), New York, NY, USA: ACM .
Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S. (2000), “On the sorting-complexity of suffix tree construction.”, 《Journal of the ACM》 47 (6): 987–1011, doi:10.1145/355541.355547, S2CID 8164822 .
접미사 트리 각주
Giegerich, R.; Kurtz, S. (1997), “From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction” (PDF), 《Algorithmica》 19 (3): 331–353, doi:10.1007/PL00009177, S2CID 18039097, 2016년 3월 3일에 원본 문서 (PDF)에서 보존된 문서, 2012년 7월 13일에 확인함 .
Iliopoulos, Costas; Rytter, Wojciech (2004), 〈On Parallel Transformations of Suffix Arrays into Suffix Trees〉, 《15th Australasian Workshop on Combinatorial Algorithms》, CiteSeerX 10.1.1.62.6715 .
접미사 트리 각주
Mansour, Essam; Allam, Amin; Skiadopoulos, Spiros; Kalnis, Panos (2011), “ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings” (PDF), 《Proceedings of the VLDB Endowment》 5 (1): 49–60, arXiv:1109.6884, Bibcode:2011arXiv1109.6884M, doi:10.14778/2047485.2047490, S2CID 7582116 .
McCreight, Edward M. (1976), “A Space-Economical Suffix Tree Construction Algorithm”, 《Journal of the ACM》 23 (2): 262–272, CiteSeerX 10.1.1.130.8022, doi:10.1145/321941.321946, S2CID 9250303 .
접미사 트리 각주
Phoophakdee, Benjarath; Zaki, Mohammed J. (2007), 〈Genome-scale disk-based suffix tree indexing〉, 《SIGMOD '07: Proceedings of the ACM SIGMOD International Conference on Management of Data》, New York, NY, USA: ACM, 833–844쪽, CiteSeerX 10.1.1.81.6031 .
Sahinalp, Cenk; Vishkin, Uzi (1994), 〈Symmetry breaking for suffix tree construction〉, 《ACM Symposium on Theory of Computing》, 300–309쪽, doi:10.1145/195058.195164, ISBN 0-89791-663-8, S2CID 5985171
접미사 트리 각주
Shun, Julian; Blelloch, Guy E. (2014), “A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction”, 《ACM Transactions on Parallel Computing》 1: 1–20, doi:10.1145/2661653, S2CID 1912378 .
Tata, Sandeep; Hankins, Richard A.; Patel, Jignesh M. (2003), 〈Practical Suffix Tree Construction〉, 《VLDB '03: Proceedings of the 30th International Conference on Very Large Data Bases》 (PDF), Morgan Kaufmann, 36–47쪽 .
Weiner, P. (1973), 〈Linear pattern matching algorithms〉 (PDF), 《14th Annual IEEE Symposium on Switching and Automata Theory》, 1–11쪽, doi:10.1109/SWAT.1973.13, 2016년 3월 3일에 원본 문서 (PDF)에서 보존된 문서, 2015년 4월 16일에 확인함 .
Zamir, Oren; Etzioni, Oren (1998), 〈Web document clustering: a feasibility demonstration〉, 《SIGIR '98: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval》, New York, NY, USA: ACM, 46–54쪽, CiteSeerX 10.1.1.36.4719 .
쿼드트리
쿼드트리(Quadtree)는 각 내부 노드가 정확히 네 개의 자식을 갖는 트리 자료 구조이다. 쿼드트리는 팔진트리의 2차원 아날로그이며, 2차원 공간을 네 개의 사분면 또는 영역으로 재귀적으로 분할하여 공간을 분할하는 데 가장 자주 사용된다. 리프 셀과 관련된 데이터는 응용 프로그램에 따라 다르지만, 리프 셀은 "흥미로운 공간 정보의 단위"를 나타낸다.
분할된 영역은 정사각형 또는 직사각형일 수 있으며, 임의의 모양을 가질 수도 있다. 이 자료 구조는 1974년 라파엘 핀켈과 J.L. 벤틀리에 의해 쿼드트리라고 명명되었다. 유사한 분할은 Q-트리라고도 알려져 있다.
모든 형태의 쿼드트리는 몇 가지 공통적인 특징을 공유한다.
트리-피라미드(T-피라미드)는 "완전한" 트리이다. T-피라미드의 모든 노드는 리프 노드를 제외하고 4개의 자식 노드를 가진다. 모든 리프는 동일한 레벨에 있으며, 이미지의 개별 픽셀에 해당하는 레벨이다. 트리-피라미드의 데이터는 이진 힙이 완전 이진 트리를 배열에 압축적으로 저장하는 방식과 유사하게 암묵적 자료 구조로 배열에 압축적으로 저장될 수 있다.
쿼드트리 유형
쿼드트리는 영역, 점, 선 및 곡선을 포함하여 나타내는 데이터 유형에 따라 분류될 수 있다. 쿼드트리는 또한 트리의 모양이 데이터 처리 순서에 독립적인지 여부에 따라 분류될 수도 있다. 다음은 쿼드트리의 일반적인 유형이다.
영역 쿼드트리는 2차원 공간의 분할을 나타내며, 영역을 네 개의 동일한 사분면, 하위 사분면 등으로 분해하고, 각 리프 노드는 특정 하위 영역에 해당하는 데이터를 포함한다. 트리의 각 노드는 정확히 네 개의 자식을 갖거나 자식이 없다(리프 노드). 이 분해 전략을 따르는 쿼드트리(즉, 더 많은 정제가 필요한 흥미로운 데이터가 하위 사분면에 있는 한 하위 사분면을 세분화하는)의 높이는 분해되는 공간 내 흥미로운 영역의 공간 분포에 민감하며 의존적이다. 영역 쿼드트리는 트라이 (컴퓨팅)의 한 유형이다.
쿼드트리 유형
깊이가 n인 영역 쿼드트리는 2n × 2n 픽셀로 구성된 이미지를 나타내는 데 사용될 수 있으며, 각 픽셀 값은 0 또는 1이다. 루트 노드는 전체 이미지 영역을 나타낸다. 어떤 영역의 픽셀이 완전히 0 또는 1이 아니면, 해당 영역은 세분화된다. 이 응용 프로그램에서 각 리프 노드는 모두 0 또는 모두 1인 픽셀 블록을 나타낸다. 이러한 트리가 이미지를 저장하는 데 사용될 때 공간 절약 가능성에 주목하라. 이미지는 종종 전체적으로 동일한 색상 값을 가진 상당한 크기의 많은 영역을 포함한다. 이미지의 모든 픽셀을 큰 2차원 배열로 저장하는 대신, 쿼드트리는 픽셀 해상도 크기의 셀보다 훨씬 높은 수준에서 동일한 정보를 캡처할 수 있다. 트리 해상도와 전체 크기는 픽셀 및 이미지 크기에 의해 제한된다.
영역 쿼드트리는 데이터 필드의 가변 해상도 표현으로도 사용될 수 있다. 예를 들어, 영역의 온도는 쿼드트리로 저장될 수 있으며, 각 리프 노드는 자신이 나타내는 하위 영역의 평균 온도를 저장한다.
쿼드트리 유형
점 쿼드트리는 2차원 점 데이터를 표현하는 데 사용되는 이진 트리의 변형이다. 모든 쿼드트리의 특징을 공유하지만, 분할의 중심이 항상 점 위에 있으므로 진정한 트리이다. 일반적으로 O(log n) 시간에 작동하며 2차원, 순서가 있는 데이터 점을 비교하는 데 매우 효율적이다. 점 쿼드트리는 완전성을 위해 언급할 가치가 있지만, 일반화된 이진 탐색 도구로서 K-d 트리에 의해 능가되었다. 무작위 삽입을 가진 점 쿼드트리는 가중 평면 확률 격자라는 이름으로 연구되었다.
점 쿼드트리는 다음과 같이 구성된다. 삽입할 다음 점이 주어지면, 해당 점이 있는 셀을 찾아 트리에 추가한다. 새 점은 해당 점을 통과하는 수직선과 수평선에 의해 셀이 사분면으로 분할되도록 추가된다. 결과적으로 셀은 직사각형이지만 반드시 정사각형일 필요는 없다. 이 트리에서 각 노드는 입력 점 중 하나를 포함한다.
쿼드트리 유형
평면의 분할은 점 삽입 순서에 따라 결정되므로, 트리의 높이는 삽입 순서에 민감하며 의존적이다. "나쁜" 순서로 삽입하면 입력 점 수에 선형적인 높이의 트리(이 경우 연결 리스트가 됨)가 될 수 있다. 점 집합이 정적인 경우, 균형 잡힌 높이의 트리를 만들기 위한 사전 처리가 수행될 수 있다.
점 쿼드트리의 노드는 이진 트리의 노드와 유사하며, 주요 차이점은 일반적인 이진 트리처럼 두 개("왼쪽"과 "오른쪽") 대신 네 개의 포인터(각 사분면에 하나씩)를 갖는다는 것이다. 또한 키는 일반적으로 x, y 좌표를 참조하는 두 부분으로 분해된다. 따라서 노드에는 다음 정보가 포함된다.
점-영역(PR) 쿼드트리는 영역 쿼드트리와 매우 유사하다. 차이점은 셀에 저장되는 정보 유형이다. 영역 쿼드트리에서는 리프 셀의 전체 영역에 적용되는 균일한 값이 저장된다. 그러나 PR 쿼드트리의 셀은 리프 셀 내에 존재하는 점들의 목록을 저장한다. 앞에서 언급했듯이, 이 분해 전략을 따르는 트리의 높이는 점들의 공간 분포에 따라 달라진다. 점 쿼드트리처럼 PR 쿼드트리도 "나쁜" 점 집합이 주어지면 선형적인 높이를 가질 수 있다.
쿼드트리 유형
가장자리 쿼드트리(PM 쿼드트리와 매우 유사하게)는 점 대신 선을 저장하는 데 사용된다. 곡선은 셀당 하나의 선분만 남을 때까지 매우 세밀하게 셀을 세분화하여 근사화된다. 모서리/정점 근처에서 가장자리 쿼드트리는 최대 분해 수준에 도달할 때까지 계속 분할한다. 이로 인해 극도로 불균형한 트리가 생성되어 인덱싱 목적을 상실할 수 있다.
다각형 맵 쿼드트리(또는 PM 쿼드트리)는 퇴화될 수 있는 (즉, 고립된 정점이나 가장자리를 가질 수 있는) 다각형 컬렉션을 저장하는 데 사용되는 쿼드트리의 변형이다.
 PM 쿼드트리와 가장자리 쿼드트리 사이의 큰 차이점은 고려 중인 셀이 셀 내의 정점에서 세그먼트가 만나는 경우에도 세분화되지 않는다는 것이다.
쿼드트리 유형
PM 쿼드트리에는 세 가지 주요 클래스가 있으며, 각 검은색 노드에 저장하는 정보에 따라 달라진다. PM3 쿼드트리는 임의의 수의 교차하지 않는 가장자리와 최대 하나의 점을 저장할 수 있다. PM2 쿼드트리는 PM3 쿼드트리와 동일하지만, 모든 가장자리가 동일한 끝점을 공유해야 한다는 점이 다르다. 마지막으로 PM1 쿼드트리는 PM2와 유사하지만, 검은색 노드에는 점과 해당 가장자리가 포함되거나 점을 공유하는 가장자리 집합만 포함될 수 있으며, 점과 점을 포함하지 않는 가장자리 집합을 동시에 가질 수는 없다.
이 섹션은 사리엘 하르-펠레드의 책에 있는 하위 섹션을 요약한 것이다.
세분화된 셀에 해당하는 모든 노드를 저장하면 많은 빈 노드를 저장하게 될 수 있다. 리프에 흥미로운 데이터가 있는 서브트리(즉, "중요한 서브트리")만 저장하여 이러한 희소 트리의 크기를 줄일 수 있다. 실제로 크기를 더 줄일 수도 있다. 중요한 서브트리만 유지하면 가지치기 과정에서 중간 노드의 차수가 2인 긴 경로(하나의 부모와 하나의 자식에 대한 링크)가 남을 수 있다. 이 경로의 시작 부분에 있는 노드 만 저장하고 (제거된 노드를 나타내기 위해 일부 메타데이터를 연결하여) 끝에 있는 서브트리를 에 연결하면 된다. "나쁜" 입력 점이 주어지면 이러한 압축된 트리도 여전히 선형 높이를 가질 수 있다.
이 압축을 수행할 때 트리의 많은 부분을 잘라내지만, Z-차순 곡선을 활용하면 여전히 로그 시간 탐색, 삽입 및 삭제를 달성할 수 있다. Z-차순 곡선은 전체 쿼드트리(및 압축된 쿼드트리)의 각 셀을  시간 안에 1차원 선으로 매핑하여(그리고  시간 안에 다시 매핑하여) 요소에 대한 전체 순서를 생성한다. 따라서 정렬된 집합의 자료 구조(트리의 노드를 저장하는)에 쿼드트리를 저장할 수 있다.
계속하기 전에 합리적인 가정을 언급해야 한다. 이진수로 표현된 두 실수 가 주어졌을 때, 이들이 다른 첫 번째 비트의 인덱스를  시간에 계산할 수 있다고 가정한다. 또한 쿼드트리에서 두 점/셀의 최저 공통 조상을  시간에 계산하고 상대적인 Z-순서를 설정할 수 있으며, 바닥 함수를  시간에 계산할 수 있다고 가정한다.
이러한 가정을 통해 주어진 점 의 점 위치(즉, 를 포함할 셀 결정), 삽입 및 삭제 작업은 모두  시간에 수행될 수 있다(즉, 기본 정렬된 집합 자료 구조에서 검색을 수행하는 데 걸리는 시간).
에 대한 점 위치를 수행하려면(즉, 압축된 트리에서 해당 셀을 찾으려면):
구체적인 내용은 생략하고, 삽입 및 삭제를 수행하려면 먼저 삽입/삭제할 대상의 점 위치를 찾은 다음 삽입/삭제한다. 필요에 따라 노드를 생성하고 제거하면서 트리를 적절하게 재구성해야 한다.
쿼드트리 쿼드트리를 이용한 이미지 처리
쿼드트리, 특히 영역 쿼드트리는 이미지 처리 응용 분야에 잘 적용되었다. 이진 이미지 데이터에 대한 논의에 국한하겠지만, 영역 쿼드트리와 그 위에서 수행되는 이미지 처리 작업은 컬러 이미지에도 마찬가지로 적합하다.
이미지 조작에 쿼드트리를 사용하는 장점 중 하나는 합집합 및 교집합의 집합 연산을 간단하고 빠르게 수행할 수 있다는 것이다.

두 개의 이진 이미지가 주어졌을 때, 이미지 합집합(오버레이라고도 함)은 입력 이미지 중 하나라도 동일한 위치에 검은색 픽셀이 있으면 픽셀이 검은색인 이미지를 생성한다. 즉, 출력 이미지의 픽셀은 두 입력 이미지 모두의 해당 픽셀이 흰색일 때만 흰색이고, 그렇지 않으면 출력 픽셀은 검은색이다. 픽셀별로 연산을 수행하는 대신, 쿼드트리의 단일 노드로 여러 픽셀을 표현하는 능력을 활용하여 합집합을 더 효율적으로 계산할 수 있다. 아래 논의를 위해, 서브트리가 검은색과 흰색 픽셀을 모두 포함하면 해당 서브트리의 루트는 회색으로 칠해진다고 말한다.