shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
융합 트리는 유한 유니버스에서 w-비트 정수에 대한 연관 배열을 구현하는 또 다른 유형의 트리 자료 구조이다. 이들은 워드 수준 병렬 처리 및 비트 조작 기술을 사용하여 선행자/후속자 쿼리 및 업데이트에 대해 시간을 달성한다. 여기서 는 워드 크기이다. 융합 트리는 공간을 사용하며 해싱 또는 지수 트리를 사용하여 동적으로 만들 수 있다.
이사벨 (증명 보조기)에 검증된 구현이 있다. 기능적 정확성과 시간 경계 모두 증명되었다.
효율적인 명령형 표준 ML 코드를 생성할 수 있다.
컴퓨터 과학에서 기수 트리, 래딕스 트리(radix tree) 또는 기수 트라이(radix trie) 또는 압축 접두사 트리(compact prefix tree) 또는 압축 트라이(compressed trie)는 유일한 자식인 각 노드가 부모와 병합되는 공간 최적화된 트라이 (접두사 트리)를 나타내는 자료 구조이다. 그 결과 모든 내부 노드의 자식 수는 기수 트리의 기수 이하이며, 여기서 = 2 (일부 정수 ≥ 1). 일반 트리와 달리 엣지는 단일 요소뿐만 아니라 요소 시퀀스로도 레이블을 지정할 수 있다. 이로 인해 기수 트리는 작은 집합 (특히 문자열이 긴 경우) 및 긴 접두사를 공유하는 문자열 집합에 훨씬 더 효율적이다.
일반 트리(전체 키가 불일치 지점까지 시작부터 한꺼번에 비교됨)와 달리, 각 노드의 키는 비트 덩어리별로 비교되며, 해당 노드의 해당 덩어리에 있는 비트의 양은 기수 트라이의 기수 이다. 이 2일 때, 기수 트라이는 이진(즉, 해당 노드의 키의 1비트 부분을 비교)이며, 이는 트라이 깊이를 최대화하는 대신 희소성을 최소화한다. 즉, 키에서 분기하지 않는 비트 문자열의 혼동까지 최대화한다. ≥ 4가 2의 거듭제곱일 때, 기수 트라이는 -진 트라이이며, 이는 잠재적 희소성을 희생하여 기수 트라이의 깊이를 줄인다.
최적화로서, 엣지 레이블은 문자열에 대한 두 개의 포인터(첫 번째 및 마지막 요소용)를 사용하여 상수 크기로 저장할 수 있다.
이 문서의 예시에서는 문자열을 문자 시퀀스로 보여주지만, 문자열 요소의 유형은 임의로 선택할 수 있다. 예를 들어, 멀티바이트 문자 인코딩 또는 유니코드를 사용할 때 문자열 표현의 비트 또는 바이트로 선택할 수 있다.
기수 트리는 문자열로 표현할 수 있는 키를 가진 연관 배열을 구성하는 데 유용하다. 이들은 IP 라우팅 영역에서 특히 응용된다. 여기서 몇 가지 예외를 제외하고 광범위한 값을 포함할 수 있는 능력은 IP 주소의 계층적 구성에 특히 적합하다. 또한 정보 검색에서 텍스트 문서의 역색인에도 사용된다.
기수 트리는 삽입, 삭제 및 검색 연산을 지원한다. 삽입은 트리에 새 문자열을 추가하면서 저장되는 데이터 양을 최소화하려고 시도한다. 삭제는 트리에서 문자열을 제거한다. 검색 연산에는 (반드시 제한되지는 않지만) 정확한 조회, 선행 요소 찾기, 후행 요소 찾기 및 접두사가 있는 모든 문자열 찾기가 포함된다. 이 모든 연산은 O(k)이며, 여기서 k는 집합의 모든 문자열의 최대 길이이고, 길이는 기수 트라이의 기수와 동일한 비트 수로 측정된다.
조회.
조회 연산은 트라이에 문자열이 존재하는지 확인한다. 대부분의 연산은 특정 작업을 처리하기 위해 이 접근 방식을 어떤 식으로든 수정한다. 예를 들어, 문자열이 끝나는 노드가 중요할 수 있다. 이 연산은 일부 엣지가 여러 요소를 소비한다는 점을 제외하고 트라이와 유사하다.
다음 의사 코드는 이러한 메서드와 멤버가 존재한다고 가정한다.
엣지
노드
함수 lookup(문자열 x)
// 요소를 찾지 않은 채 루트에서 시작
노드 traverseNode := root;
정수 elementsFound := 0;
// 리프를 찾거나 계속 진행할 수 없을 때까지 순회
while (traverseNode != null &amp;&amp; !traverseNode.isLeaf() &amp;&amp; elementsFound &lt; x.length)
// x에서 아직 찾지 못한 요소를 기반으로 탐색할 다음 엣지 가져오기
엣지 nextEdge := 선택 edge
from traverseNode.edges
where edge.label is a prefix of x.suffix(elementsFound)
// x.suffix(elementsFound)는 x의 마지막 (x.length - elementsFound) 요소를 반환
// 엣지를 찾았는가?
if (nextEdge != null)
// 탐색할 다음 노드 설정
traverseNode := nextEdge.targetNode;
// 엣지에 저장된 레이블을 기반으로 찾은 요소 증가
elementsFound += nextEdge.label.length;
// 루프 종료
traverseNode := null;
// 리프 노드에 도달했고 정확히 x.length 요소를 사용했다면 일치하는 것을 찾은 것
return (traverseNode != null &amp;&amp; traverseNode.isLeaf() &amp;&amp; elementsFound == x.length);
문자열을 삽입하려면 더 이상 진행할 수 없을 때까지 트리를 검색한다. 이 시점에서 우리는 입력 문자열의 나머지 모든 요소로 레이블이 지정된 새 나가는 엣지를 추가하거나, 나머지 입력 문자열과 접두사를 공유하는 나가는 엣지가 이미 있는 경우, 이를 두 개의 엣지(처음 것은 공통 접두사로 레이블 지정됨)로 분할하고 진행한다. 이 분할 단계는 어떤 노드도 가능한 문자열 요소보다 많은 자식을 갖지 않도록 보장한다.
삽입의 여러 경우가 아래에 나와 있다. r은 단순히 루트를 나타낸다. 엣지는 필요한 경우 문자열을 종료하기 위해 빈 문자열로 레이블을 지정할 수 있으며 루트에는 들어오는 엣지가 없다고 가정한다. (위에서 설명한 조회 알고리즘은 빈 문자열 엣지를 사용할 때 작동하지 않는다.)
트리에서 문자열 x를 삭제하려면 먼저 x를 나타내는 리프를 찾는다. 그런 다음 x가 존재한다고 가정하고 해당 리프 노드를 제거한다. 리프 노드의 부모에게 다른 자식이 하나만 있는 경우 해당 자식의 들어오는 레이블이 부모의 들어오는 레이블에 추가되고 자식이 제거된다.
이 자료 구조는 1968년 도널드 모리슨과 게르노트 그베헨베르거가 발명했으며, 주로 모리슨과 관련이 있다.
도널드 커누스는 《컴퓨터 프로그래밍의 예술》 3권 498-500페이지에서 이들을 "패트리샤의 트리"라고 불렀는데, 이는 모리슨 논문의 제목에 있는 약어("PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric")에서 따온 것으로 추정된다. 오늘날 패트리샤 트리는 기수가 2인 기수 트리로 간주된다. 즉, 키의 각 비트가 개별적으로 비교되고 각 노드는 양방향(즉, 왼쪽 대 오른쪽) 분기이다.
다른 자료 구조와의 비교.
균형 트리와 달리 기수 트리는 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)는 주어진 텍스트의 모든 접미사를 키로, 텍스트 내 위치를 값으로 포함하는 압축된 트라이이다. 접미사 트리는 많은 중요한 문자열 연산을 특히 빠르게 구현할 수 있게 한다.
문자열 formula_1에 대한 이러한 트리의 구성은 formula_1의 길이에 비례하는 시간과 공간을 차지한다. 일단 구성되면, formula_1에서 서브스트링을 찾거나, 특정 수의 오류가 허용될 경우 서브스트링을 찾거나, 정규 표현식 패턴에 대한 일치를 찾는 것과 같은 여러 연산을 빠르게 수행할 수 있다. 접미사 트리는 또한 최장 공통 부분 문자열 문제에 대한 최초의 선형 시간 솔루션 중 하나를 제공했다. 이러한 속도 향상은 비용을 수반한다. 문자열의 접미사 트리를 저장하는 것은 일반적으로 문자열 자체를 저장하는 것보다 훨씬 더 많은 공간을 필요로 한다.
이 개념은 에 의해 처음 소개되었다.
위너는 접미사 formula_4 대신, 그의 트라이에 각 위치에 대한 접두사 식별자를 저장했다. 즉, formula_5에서 시작하여 formula_1에 한 번만 나타나는 가장 짧은 문자열이다. 그의 알고리즘 D는 formula_7에 대한 비압축 트라이를 받아 formula_8에 대한 트라이로 확장한다. 이러한 방식으로, formula_9에 대한 자명한 트라이에서 시작하여, formula_10번의 알고리즘 D의 연속적인 호출로 formula_11에 대한 트라이를 구축할 수 있다. 그러나 전체 실행 시간은 formula_12이다. 위너의 알고리즘 B는 구성된 트라이의 크기에 비례하는 전체 실행 시간을 달성하기 위해 여러 보조 데이터 구조를 유지한다. 후자는 formula_13의 경우처럼 여전히 formula_12 노드가 될 수 있다. 위너의 알고리즘 C는 최종적으로 압축된 트라이를 사용하여 선형 전체 저장 공간 및 실행 시간을 달성한다.
도널드 커누스는 나중에 후자를 그의 학생인 본 프랫에 따르면 "1973년의 알고리즘"으로 특징지었다.
교과서는 위너의 결과를 단순하고 더 우아한 형태로 재현하며, 위치 트리(position tree)라는 용어를 도입했다.
는 formula_1의 모든 접미사에 대한 (압축된) 트라이를 구축한 최초의 인물이었다. formula_5에서 시작하는 접미사는 일반적으로 접두사 식별자보다 길지만, 압축된 트라이에서 이들의 경로 표현은 크기가 다르지 않다. 반면에 McCreight는 위너의 보조 데이터 구조 대부분을 없앨 수 있었고, 접미사 링크만 남았다.
는 구성을 더욱 단순화했다. 그는 현재 우코넨 알고리즘으로 알려진, 당시 가장 빠른 알고리즘과 실행 시간이 일치하는 접미사 트리의 최초 온라인 구성을 제공했다.
이러한 알고리즘은 모두 상수 크기 알파벳에 대해 선형 시간이며, 일반적으로 최악의 경우 formula_17의 실행 시간을 가진다.
는 모든 알파벳에 대해 최적의 접미사 트리 구성 알고리즘을 제시했다. 특히, 이는 다항 범위의 정수 알파벳에서 파생된 문자열에 대한 최초의 선형 시간 알고리즘이다. Farach의 알고리즘은 외부 메모리, 압축, 간결한 접미사 트리 및 접미사 배열을 구성하기 위한 새로운 알고리즘의 기반이 되었다.
길이 formula_18인 문자열 formula_1에 대한 접미사 트리는 다음과 같은 트리로 정의된다.
formula_1의 한 접미사가 다른 접미사의 접두사이기도 한 경우, 해당 문자열에 대한 이러한 트리는 존재하지 않는다. 예를 들어, 문자열 abcbc에서 접미사 bc는 접미사 bcbc의 접두사이기도 하다. 이러한 경우, bc를 나타내는 경로는 리프에서 끝나지 않아 다섯 번째 규칙을 위반한다. 이 문제를 해결하기 위해 formula_1는 문자열에 나타나지 않는 터미널 기호(일반적으로 codice_1로 표시됨)로 채워진다. 이렇게 하면 어떤 접미사도 다른 접미사의 접두사가 되지 않으며, formula_1의 formula_18개 접미사 각각에 대해 formula_18개의 리프 노드가 존재한다. 모든 내부 비루트 노드는 분기하므로, 이러한 노드는 최대 formula_34개가 있을 수 있으며, 총 formula_35개의 노드(formula_18개의 리프, formula_34개의 내부 비루트 노드, 1개의 루트)가 있다.
접미사 링크는 이전의 선형 시간 구성 알고리즘의 핵심 기능이지만, Farach's algorithm을 기반으로 하는 대부분의 새로운 알고리즘은 접미사 링크를 사용하지 않는다. 완전한 접미사 트리에서 모든 내부 비루트 노드는 다른 내부 노드로의 접미사 링크를 가진다. 루트에서 노드까지의 경로가 문자열 formula_38를 나타내고, 여기서 formula_39는 단일 문자이고 formula_40는 문자열(비어 있을 수 있음)인 경우, 해당 노드는 formula_40를 나타내는 내부 노드로의 접미사 링크를 가진다. 예를 들어, 위 그림에서 codice_2 노드에서 codice_3 노드로의 접미사 링크를 참조하라. 접미사 링크는 트리에서 실행되는 일부 알고리즘에서도 사용된다.
일반화된 접미사 트리는 단일 문자열 대신 문자열 집합을 위해 만들어진 접미사 트리이다. 이는 이 문자열 집합의 모든 접미사를 나타낸다. 각 문자열은 다른 종료 기호로 끝나야 한다.
길이 formula_18인 문자열 formula_1에 대한 접미사 트리는 문자가 다항 범위의 정수 알파벳에서 오는 경우 formula_44 시간에 구축할 수 있다(특히 상수 크기 알파벳의 경우).
더 큰 알파벳의 경우, 실행 시간은 문자를 formula_45 크기 범위로 가져오기 위해 먼저 정렬하는 데 지배된다. 일반적으로 이는 formula_17 시간이 걸린다.
아래 비용은 알파벳이 상수라는 가정하에 주어진다.
길이 formula_18인 문자열 formula_1에 대한 접미사 트리가 구축되었거나, 총 길이 formula_49인 문자열 집합 formula_50에 대한 일반화된 접미사 트리가 구축되었다고 가정하자.
다음 작업을 수행할 수 있다:
접미사 트리는 노드 간의 상수 시간 최소 공통 조상 검색을 위해 formula_44 시간 내에 준비될 수 있다. 그러면 다음 작업도 수행할 수 있다.
접미사 트리는 텍스트 편집, 자유 텍스트 검색, 계산생물학 및 기타 응용 분야에서 발생하는 많은 문자열 문제를 해결하는 데 사용될 수 있다. 주요 응용 분야는 다음과 같다.
접미사 트리는 생물정보학 응용 분야에서 DNA 또는 단백질 서열(긴 문자열로 간주될 수 있음)에서 패턴을 검색하는 데 자주 사용된다. 불일치를 효율적으로 검색하는 능력은 가장 큰 강점으로 간주될 수 있다. 접미사 트리는 데이터 압축에도 사용된다. 반복되는 데이터를 찾는 데 사용될 수 있으며, 버로우즈-휠러 변환의 정렬 단계에 사용될 수 있다. LZW 압축 방식의 변형은 접미사 트리를 사용한다(LZSS). 접미사 트리는 또한 일부 검색 엔진에서 사용되는 데이터 클러스터링 알고리즘인 접미사 트리 클러스터링에도 사용된다.
각 노드와 엣지를 formula_86 공간으로 표현할 수 있다면, 전체 트리는 formula_44 공간으로 표현될 수 있다. 트리 내 모든 엣지의 모든 문자열 길이의 총합은 formula_12이지만, 각 엣지는 의 부분 문자열의 위치와 길이로 저장될 수 있어 총 공간 사용량은 formula_44 컴퓨터 워드가 된다. 접미사 트리의 최악의 공간 사용량은 피보나치 워드에서 볼 수 있으며, 전체 formula_107 노드를 제공한다.
접미사 트리를 구현할 때 중요한 선택은 노드 간의 부모-자식 관계이다. 가장 일반적인 방법은 형제 리스트라고 불리는 연결 리스트를 사용하는 것이다. 각 노드는 첫 번째 자식에 대한 포인터와 자신이 속한 자식 리스트의 다음 노드에 대한 포인터를 가진다. 효율적인 실행 시간 속성을 가진 다른 구현은 해시 맵, 정렬되거나 정렬되지 않은 배열 (배열 두 배 확장과 함께), 또는 균형 탐색 트리를 사용한다. 우리는 다음에 관심이 있다.
를 알파벳의 크기라고 하자. 그러면 다음과 같은 비용이 발생한다.
삽입 비용은 상각되며, 해싱 비용은 완전 해싱에 대해 주어진다.
각 엣지와 노드의 방대한 정보로 인해 접미사 트리는 매우 비싸며, 좋은 구현에서는 원본 텍스트 메모리 크기의 약 10~20배를 소비한다. 접미사 배열은 이 요구 사항을 8배로 줄인다(32비트 주소 공간과 8비트 문자로 구축된 LCP 값을 포함하는 배열의 경우). 이 인자는 속성에 따라 다르며 32비트 시스템에서 4바이트 너비의 문자(일부 유닉스 계열 시스템에서 모든 기호를 포함하는 데 필요하며, wchar_t 참조)를 사용할 경우 2에 도달할 수 있다. 연구자들은 더 작은 인덱싱 구조를 계속 찾아왔다.
병렬 구성.
접미사 트리 구성 속도를 높이기 위한 다양한 병렬 알고리즘이 제안되었다.
최근에는 formula_45 작업 (순차 시간)과 formula_109 스팬을 가진 접미사 트리 구성을 위한 실용적인 병렬 알고리즘이 개발되었다. 이 알고리즘은 공유 메모리 멀티코어 머신에서 좋은 병렬 확장성을 달성하며, 40코어 머신을 사용하여 인간 유전체 – 약 3GB –를 3분 이내에 인덱싱할 수 있다.
외부 구성.
접미사 트리의 메모리 사용량은 선형적이지만 실제 시퀀스 컬렉션의 크기보다 상당히 크다. 큰 텍스트의 경우 구성에 외부 메모리 접근 방식이 필요할 수 있다.
외부 메모리에서 접미사 트리를 구성하는 이론적 결과가 있다.
의 알고리즘은 정렬과 동일한 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분 이내에 전체 인간 유전체를 인덱싱할 수 있다.
쿼드트리(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 쿼드트리의 셀은 리프 셀 내에 존재하는 점들의 목록을 저장한다. 앞에서 언급했듯이, 이 분해 전략을 따르는 트리의 높이는 점들의 공간 분포에 따라 달라진다. 점 쿼드트리처럼 PR 쿼드트리도 "나쁜" 점 집합이 주어지면 선형적인 높이를 가질 수 있다.
가장자리 쿼드트리.
가장자리 쿼드트리(PM 쿼드트리와 매우 유사하게)는 점 대신 선을 저장하는 데 사용된다. 곡선은 셀당 하나의 선분만 남을 때까지 매우 세밀하게 셀을 세분화하여 근사화된다. 모서리/정점 근처에서 가장자리 쿼드트리는 최대 분해 수준에 도달할 때까지 계속 분할한다. 이로 인해 극도로 불균형한 트리가 생성되어 인덱싱 목적을 상실할 수 있다.
다각형 맵(PM) 쿼드트리.
다각형 맵 쿼드트리(또는 PM 쿼드트리)는 퇴화될 수 있는 (즉, 고립된 정점이나 가장자리를 가질 수 있는) 다각형 컬렉션을 저장하는 데 사용되는 쿼드트리의 변형이다.
PM 쿼드트리와 가장자리 쿼드트리 사이의 큰 차이점은 고려 중인 셀이 셀 내의 정점에서 세그먼트가 만나는 경우에도 세분화되지 않는다는 것이다.
PM 쿼드트리에는 세 가지 주요 클래스가 있으며, 각 검은색 노드에 저장하는 정보에 따라 달라진다. PM3 쿼드트리는 임의의 수의 교차하지 않는 가장자리와 최대 하나의 점을 저장할 수 있다. PM2 쿼드트리는 PM3 쿼드트리와 동일하지만, 모든 가장자리가 동일한 끝점을 공유해야 한다는 점이 다르다. 마지막으로 PM1 쿼드트리는 PM2와 유사하지만, 검은색 노드에는 점과 해당 가장자리가 포함되거나 점을 공유하는 가장자리 집합만 포함될 수 있으며, 점과 점을 포함하지 않는 가장자리 집합을 동시에 가질 수는 없다.
압축된 쿼드트리.
이 섹션은 사리엘 하르-펠레드의 책에 있는 하위 섹션을 요약한 것이다.
세분화된 셀에 해당하는 모든 노드를 저장하면 많은 빈 노드를 저장하게 될 수 있다. 리프에 흥미로운 데이터가 있는 서브트리(즉, "중요한 서브트리")만 저장하여 이러한 희소 트리의 크기를 줄일 수 있다. 실제로 크기를 더 줄일 수도 있다. 중요한 서브트리만 유지하면 가지치기 과정에서 중간 노드의 차수가 2인 긴 경로(하나의 부모와 하나의 자식에 대한 링크)가 남을 수 있다. 이 경로의 시작 부분에 있는 노드 formula_1만 저장하고 (제거된 노드를 나타내기 위해 일부 메타데이터를 연결하여) 끝에 있는 서브트리를 formula_1에 연결하면 된다. "나쁜" 입력 점이 주어지면 이러한 압축된 트리도 여전히 선형 높이를 가질 수 있다.
이 압축을 수행할 때 트리의 많은 부분을 잘라내지만, Z-차순 곡선을 활용하면 여전히 로그 시간 탐색, 삽입 및 삭제를 달성할 수 있다. Z-차순 곡선은 전체 쿼드트리(및 압축된 쿼드트리)의 각 셀을 formula_3 시간 안에 1차원 선으로 매핑하여(그리고 formula_3 시간 안에 다시 매핑하여) 요소에 대한 전체 순서를 생성한다. 따라서 정렬된 집합의 자료 구조(트리의 노드를 저장하는)에 쿼드트리를 저장할 수 있다.
계속하기 전에 합리적인 가정을 언급해야 한다. 이진수로 표현된 두 실수 formula_5가 주어졌을 때, 이들이 다른 첫 번째 비트의 인덱스를 formula_3 시간에 계산할 수 있다고 가정한다. 또한 쿼드트리에서 두 점/셀의 최저 공통 조상을 formula_3 시간에 계산하고 상대적인 Z-순서를 설정할 수 있으며, 바닥 함수를 formula_3 시간에 계산할 수 있다고 가정한다.
이러한 가정을 통해 주어진 점 formula_9의 점 위치(즉, formula_9를 포함할 셀 결정), 삽입 및 삭제 작업은 모두 formula_11 시간에 수행될 수 있다(즉, 기본 정렬된 집합 자료 구조에서 검색을 수행하는 데 걸리는 시간).
formula_9에 대한 점 위치를 수행하려면(즉, 압축된 트리에서 해당 셀을 찾으려면):
구체적인 내용은 생략하고, 삽입 및 삭제를 수행하려면 먼저 삽입/삭제할 대상의 점 위치를 찾은 다음 삽입/삭제한다. 필요에 따라 노드를 생성하고 제거하면서 트리를 적절하게 재구성해야 한다.
쿼드트리를 이용한 이미지 처리.
쿼드트리, 특히 영역 쿼드트리는 이미지 처리 응용 분야에 잘 적용되었다. 이진 이미지 데이터에 대한 논의에 국한하겠지만, 영역 쿼드트리와 그 위에서 수행되는 이미지 처리 작업은 컬러 이미지에도 마찬가지로 적합하다.
이미지 합집합/교집합.
이미지 조작에 쿼드트리를 사용하는 장점 중 하나는 합집합 및 교집합의 집합 연산을 간단하고 빠르게 수행할 수 있다는 것이다.
두 개의 이진 이미지가 주어졌을 때, 이미지 합집합(오버레이라고도 함)은 입력 이미지 중 하나라도 동일한 위치에 검은색 픽셀이 있으면 픽셀이 검은색인 이미지를 생성한다. 즉, 출력 이미지의 픽셀은 두 입력 이미지 모두의 해당 픽셀이 흰색일 때만 흰색이고, 그렇지 않으면 출력 픽셀은 검은색이다. 픽셀별로 연산을 수행하는 대신, 쿼드트리의 단일 노드로 여러 픽셀을 표현하는 능력을 활용하여 합집합을 더 효율적으로 계산할 수 있다. 아래 논의를 위해, 서브트리가 검은색과 흰색 픽셀을 모두 포함하면 해당 서브트리의 루트는 회색으로 칠해진다고 말한다.
이 알고리즘은 두 입력 쿼드트리(formula_21 및 formula_22)를 순회하면서 출력 쿼드트리 formula_23를 구축하는 방식으로 작동한다. 비공식적으로 알고리즘은 다음과 같다. 이미지의 동일한 영역에 해당하는 노드 formula_24 및 formula_25를 고려한다.
이 알고리즘은 작동하지만, 그 자체로 최소 크기의 쿼드트리를 보장하지는 않는다. 예를 들어, formula_38 크기의 바둑판(모든 타일이 픽셀인)과 그 보수를 합집합하는 결과를 고려해 보자. 결과는 루트 노드(검은색으로 칠해진)만 있는 쿼드트리로 표현되어야 할 거대한 검은색 사각형이지만, 대신 알고리즘은 깊이 formula_39의 완전 4진 트리를 생성한다. 이를 해결하기 위해, 결과 쿼드트리의 상향식 순회를 수행하여 네 자식 노드가 동일한 색상인지 확인하고, 이 경우 부모 노드를 동일한 색상의 리프로 대체한다.
두 이미지의 교집합은 거의 동일한 알고리즘이다. 두 이미지의 교집합을 생각하는 한 가지 방법은 흰색 픽셀에 대한 합집합을 수행하는 것이다. 따라서 교집합을 수행하려면 합집합 알고리즘에서 검은색과 흰색의 언급을 바꾼다.
연결 성분 레이블링.
이진 이미지에서 인접한 두 검은색 픽셀을 고려해 보자. 이들은 경계 수평 또는 수직 가장자리를 공유하면 인접한다. 일반적으로 두 검은색 픽셀은 인접한 픽셀로만 이동하여 다른 픽셀에서 도달할 수 있으면 연결된다(즉, 각 연속 쌍이 인접한 검은색 픽셀 경로가 존재한다). 연결된 검은색 픽셀의 각 최대 집합은 연결 성분이다. 이미지의 쿼드트리 표현을 사용하여 사메트는 쿼드트리 크기에 비례하는 시간으로 이러한 연결 성분을 찾고 레이블을 지정하는 방법을 보여주었다. 이 알고리즘은 다각형 색칠에도 사용될 수 있다.
알고리즘은 세 단계로 작동한다.
논의를 단순화하기 위해 쿼드트리 노드의 자식이 Z-차순 (SW, NW, SE, NE)을 따른다고 가정하자. 이 구조를 믿을 수 있기 때문에, 어떤 셀에 대해서도 계층 구조의 다른 수준에서 인접한 셀을 찾기 위해 쿼드트리를 탐색하는 방법을 안다.
1단계는 쿼드트리의 후위 순회로 수행된다. 각 검은색 리프 formula_14에 대해 북쪽 이웃 및 동쪽 이웃(즉, formula_14의 셀과 가장자리를 공유하는 북쪽 및 동쪽 셀)을 나타내는 노드를 살펴본다. 트리가 Z-순서로 구성되어 있으므로 남쪽 및 서쪽 이웃은 이미 처리되고 고려되었다는 불변성을 가진다. 현재 고려 중인 북쪽 또는 동쪽 이웃을 formula_1라고 하자. 만약 formula_1가 검은색 픽셀을 나타내면:
2단계는 합집합-찾기 자료 구조를 사용하여 수행할 수 있다. 각 고유 레이블을 별도의 집합으로 시작한다. 첫 번째 단계에서 기록된 모든 동등 관계에 대해 해당 집합을 합집합한다. 그 후, 남아있는 각 고유 집합은 이미지의 고유한 연결 성분과 연결된다.
3단계는 또 다른 후위 순회를 수행한다. 이번에는 각 검은색 노드 formula_14에 대해 합집합-찾기의 find 연산( formula_14의 이전 레이블과 함께)을 사용하여 formula_14의 새 레이블을 찾고 할당한다( formula_14가 속한 연결 성분과 연결된).
쿼드트리를 이용한 메시 생성.
이 섹션은 하르-펠레드와 데 베르그 등의 책에서 발췌한 장을 요약한 것이다.
메시 생성은 본질적으로 추가 처리가 수행될 수 있는 점 집합의 삼각측량이다. 따라서 결과 삼각측량이 특정 속성(예: 비균일성, "너무 가늘지 않은" 삼각형, 희소 영역의 큰 삼각형, 밀집 영역의 작은 삼각형 등)을 갖는 것이 바람직하며, 이는 추가 처리를 더 빠르고 오류가 적게 만든다. 점 집합에 구축된 쿼드트리는 이러한 원하는 속성을 가진 메시를 생성하는 데 사용될 수 있다.
쿼드트리의 리프와 해당 셀 formula_14를 고려해 보자. 셀의 각 변이 인접 셀의 모서리 점에 의해 각 변에서 최대 한 번만 교차되면 formula_14는 (메시 생성을 위해) 균형 잡혔다고 말한다. 이는 formula_14에 인접한 리프의 쿼드트리 수준이 formula_14의 수준과 최대 1만큼 차이 난다는 것을 의미한다. 모든 리프에 대해 이것이 참이면 전체 쿼드트리가 (메시 생성을 위해) 균형 잡혔다고 말한다.
셀 formula_14와 formula_14를 중심으로 하는 동일한 크기의 셀로 구성된 formula_58 이웃을 고려해 보자. 이 이웃을 확장 클러스터라고 부른다. 쿼드트리가 균형 잡혀 있고, 점 집합의 점을 포함하는 모든 리프 formula_1에 대해 해당 확장 클러스터도 쿼드트리에 있으며 확장 클러스터에 점 집합의 다른 점이 포함되어 있지 않으면 쿼드트리는 잘 균형 잡혔다고 말한다.
메시 생성은 다음과 같이 수행된다.
트리 셀의 모서리 점을 삼각측량의 정점으로 간주한다. 변환 단계 전에 우리는 일부에 점이 있는 상자들을 가지고 있다. 변환 단계는 다음 방식으로 수행된다. 각 점에 대해 셀의 가장 가까운 모서리를 점에 맞게 변형하고, 결과로 생성되는 네 개의 사각형을 "좋은" 삼각형으로 삼각측량한다(관심 있는 독자는 "좋은" 삼각형을 만드는 것에 대한 자세한 내용은 Har-Peled의 12장을 참조한다.).
남은 정사각형은 몇 가지 간단한 규칙에 따라 삼각측량된다. 각 정규 정사각형(내부에 점이 없고 변에 모서리 점이 없는)에 대해 대각선을 도입한다. 우리가 점들을 잘 균형 잡는 속성으로 분리하는 방식 때문에, 변을 교차하는 모서리를 가진 정사각형은 변형된 정사각형이 아니다. 따라서 교차하는 모서리를 가진 정사각형은 다음과 같이 삼각측량할 수 있다. 교차하는 변이 하나인 경우, 사각형은 교차점과 반대쪽 모서리를 연결하는 긴 대각선을 추가하여 세 개의 삼각형이 된다. 교차하는 변이 네 개인 경우, 네 교차점 중 두 개 사이에 모서리를 추가하여 사각형을 절반으로 분할한 다음, 이 두 끝점을 나머지 두 교차점에 연결한다. 다른 정사각형의 경우, 중앙에 점을 도입하고 사각형의 네 모서리와 각 교차점에 연결한다.
결국, 쿼드트리에서 구축된 점 집합의 잘 삼각측량된 메시를 얻게 된다.
다음 의사 코드는 점만 처리하는 쿼드트리를 구현하는 한 가지 방법을 보여준다. 다른 접근 방식도 사용할 수 있다.
이러한 구조가 사용된다고 가정한다.
// 점과 벡터를 나타내는 간단한 좌표 객체
struct XY
// 반차원과 중심을 가진 축 정렬 경계 상자
struct AABB
XY center;
float halfDimension;
QuadTree 클래스.
이 클래스는 하나의 쿼드트리와 그것이 뿌리내린 노드를 모두 나타낸다.
class QuadTree
// 이 쿼드트리 노드에 저장할 수 있는 요소의 수를 나타내는 임의의 상수
constant int QT_NODE_CAPACITY = 4;
// 이 쿼드트리의 경계를 나타내기 위해 반차원과 중심을 가진 축 정렬 경계 상자
AABB boundary;
// 이 쿼드트리 노드의 점들
Array of XY [size = QT_NODE_CAPACITY] points;
// 자식들
QuadTree* northWest;
QuadTree* northEast;
QuadTree* southWest;
QuadTree* southEast;
// 메서드
function subdivide() {...} // 이 쿼드를 4개의 동일한 영역의 쿼드로 완전히 분할하는 4개의 자식을 생성한다.
다음 메서드는 필요에 따라 분할하여 점을 쿼드트리의 적절한 쿼드에 삽입한다.
// 쿼드트리에 점 삽입
function insert(XY p)
// 이 쿼드트리에 속하지 않는 객체 무시
if (!boundary.containsPoint(p))
return false; // 객체를 추가할 수 없음
// 이 쿼드트리에 공간이 있고 세분화가 없다면 여기에 객체 추가
if (points.size &lt; QT_NODE_CAPACITY &amp;&amp; northWest == null)
points.append(p);
// 그렇지 않다면, 세분화한 다음 어떤 노드든 받아들일 점을 추가
if (northWest == null)
subdivide();
// 마지막 노드만 데이터를 포함하기를 원한다면 이 쿼드 배열에 포함된 점/데이터를 새 쿼드에 추가해야 한다.
if (northWest-&gt;insert(p)) return true;
if (northEast-&gt;insert(p)) return true;
if (southWest-&gt;insert(p)) return true;
if (southEast-&gt;insert(p)) return true;
// 그렇지 않다면, 알 수 없는 이유로 점을 삽입할 수 없다 (이런 일은 절대 일어나서는 안 됨)
범위 쿼리.
다음 메서드는 범위 내에 포함된 모든 점을 찾는다.
// 범위 내에 나타나는 모든 점 찾기
function queryRange(AABB range)
// 결과 배열 준비
Array of XY pointsInRange;
// 범위가 이 쿼드와 교차하지 않으면 자동으로 중단
if (!boundary.intersectsAABB(range))
return pointsInRange; // 빈 목록
// 이 쿼드 레벨에서 객체 확인
for (int p = 0; p &lt; points.size; p++)
if (range.containsPoint(points[p]))
pointsInRange.append(points[p]);
// 자식이 없으면 여기서 종료
return pointsInRange;
// 그렇지 않으면 자식의 점들을 추가
pointsInRange.appendArray(northWest-&gt;queryRange(range));
pointsInRange.appendArray(northEast-&gt;queryRange(range));
pointsInRange.appendArray(southWest-&gt;queryRange(range));
pointsInRange.appendArray(southEast-&gt;queryRange(range));
Aluru와 Samet의 조사는 쿼드트리에 대한 좋은 개요를 제공한다.
펜윅 트리(Fenwick tree) 또는 이진 인덱스 트리(binary indexed tree, BIT)는 값의 배열을 저장하고 값의 누적 합을 효율적으로 계산하며 값을 업데이트할 수 있는 자료 구조이다. 또한 지정된 값 이하의 합계를 가진 가장 긴 접두사를 찾기 위한 효율적인 순위 검색 연산도 지원한다. 주로 자주 업데이트되는 통계 빈도 테이블의 누적 분포 함수에 대해 작동하는 데 사용된다.
이 구조는 1989년 보리스 랴프코가 제안했으며 1992년에 추가 수정이 발표되었다. 이후 피터 펜윅이 1994년 논문에서 이 구조를 설명한 후 펜윅 트리라는 이름으로 알려지게 되었다.
값의 단순 배열은 업데이트하기 쉽지만(상수 시간) 누적 합을 계산하거나 접두사 길이를 검색하는 데는 formula_1 시간이 필요하다.
누적 합 배열은 상수 시간에 누적 합을 반환하고, formula_2 시간에 접두사 길이를 검색할 수 있지만, 값 중 하나를 업데이트하는 데는 formula_1 시간이 필요하다.
펜윅 트리는 세 가지 작업을 모두 formula_2 시간에 수행할 수 있다. 이는 값을 formula_5개의 노드를 가진 트리로 표현하여 각 트리의 노드가 해당 부모 노드의 인덱스(배타적)부터 해당 노드의 인덱스(포괄적)까지의 값의 합을 저장함으로써 달성된다. 트리는 그 자체가 암시적 자료 구조이며 formula_6개의 값 배열로 저장될 수 있으며, 암시적 루트 노드는 배열에서 생략된다. 트리 구조는 값 검색, 값 업데이트, 누적 합 및 범위 합 작업을 formula_2 노드 액세스만을 사용하여 수행할 수 있도록 한다.
값의 배열이 주어졌을 때, 때로는 특정 결합적이항 연산 (정수의 덧셈이 가장 흔함)에 따라 각 인덱스까지의 값의 누적 합을 계산하는 것이 바람직하다. 펜윅 트리는 기본 값 배열의 변경을 허용하고 모든 후속 쿼리가 이러한 변경을 반영하도록 하면서, 어떤 인덱스에서든 누적 합 또는 접두사 합을 쿼리하는 방법을 제공한다.
펜윅 트리는 적응형 산술 부호화를 구현하는 데 특별히 고안되었는데, 이는 생성된 각 심볼의 수를 유지하고 이를 주어진 심볼보다 작은 심볼의 누적 확률로 변환해야 한다. 지원하는 연산의 개발은 주로 이 경우의 사용에 동기가 부여되었다.
펜윅 트리는 노드가 연속적으로 번호가 매겨지고, 부모-자식 관계가 노드 인덱스에 대한 산술 연산으로 결정되는 암시적 자료 구조이다.
이 인덱스 산술에서 중요한 함수는 최하위 비트이다. 이는 인덱스 formula_8를 나누는 가장 큰 2의 거듭제곱이다. 이는 지수(0, 1, 2, 3, ...)가 아닌 2의 거듭제곱(1, 2, 4, 8, ...)이다. 2의 보수 산술에서 formula_9 (여기서 &amp;는 비트 AND를 나타냄)로 효율적으로 계산할 수 있다.
펜윅 트리는 1-기반 배열 formula_10에 formula_6개의 값을 사용하여 가장 쉽게 이해된다. 반개방 구간 표기법을 사용하여 formula_12는 formula_8(배타적)부터 formula_14(포괄적)까지의 범위를 나타낸다. 해당 펜윅 배열 formula_15은 범위 합 formula_16를 저장한다. 즉, formula_17를 포함하여 끝나는 formula_18개 값의 합이다.
일부 설명에서는 가상의 노드 0이 사용되지만, 실제로는 액세스되지 않으며 명시적으로 저장할 필요가 없다. formula_19이지만 이 값은 실제로는 필요하지 않다. formula_20은 값 0을 가진 빈 범위 formula_21의 합을 포함하는 것으로 간주될 수 있다.
"펜윅 트리"는 실제로는 동일한 배열에 대한 세 가지 암시적 트리를 의미한다: 인덱스를 접두사 합으로 변환하는 데 사용되는 쿼리 트리, 요소를 업데이트하는 데 사용되는 업데이트 트리, 그리고 접두사 합을 인덱스로 변환하는 데 사용되는 검색 트리(순위 쿼리). 처음 두 트리는 일반적으로 위로 이동하며, 세 번째 트리는 일반적으로 아래로 이동한다.
쿼리 트리.
쿼리 트리는 노드 formula_8의 부모가 formula_23가 되도록 정의된다. 예를 들어, 6 = 1102의 부모는 4 = 1002이다. 암시적 노드 0은 루트이다.
트리의 각 레벨 formula_24는 formula_24개의 고유한 2의 거듭제곱 합에 해당하는 인덱스를 가진 노드를 포함한다(formula_26은 빈 합 0을 나타냄). 예를 들어, 레벨 formula_27은 노드 formula_28를 포함하고 레벨 formula_29는 노드 formula_30를 포함한다.
노드 formula_8는 formula_32개의 자식(formula_33)을 가지며, 총 formula_18개의 자손을 가진다. (이 숫자에는 formula_6보다 큰 노드가 포함되며, 이 노드들은 생략되고 액세스되지 않는다.)
아래 다이어그램은 16개 노드 펜윅 트리의 쿼리 트리의 구조를 보여주며, 루트를 포함하므로 15개 요소 배열 A에 해당한다:
누적 합 formula_36를 찾으려면, formula_8와 그 부모, 부모의 부모 등 루트(포함하지 않음)까지의 값을 더한다. 범위 합 formula_38를 계산하려면, formula_39과 formula_14에 대한 누적 합을 뺀다.
이는 첫 번째 공통 조상에서 멈춤으로써 최적화될 수 있다. 극단적인 예는 단일 엔트리 formula_41를 요청하는 것이다. 이 경우, formula_14와 formula_43의 공통 조상은 formula_44이므로, formula_45에서 시작하고 formula_46인 동안 formula_47를 빼고 codice_1로 업데이트한다.
업데이트 트리.
업데이트 트리는 쿼리 트리의 거울상이다. 노드 formula_8의 부모는 formula_49이다 (여기서 |는 비트 OR을 나타냄). 예를 들어, 6 = 1102의 부모는 8 = 10002이다.
이 개념적인 트리는 무한하지만, formula_6까지의 인덱스를 가진 부분만 저장되거나 사용된다. formula_6보다 큰 인덱스를 가진 가상의 노드를 제외하면, formula_6의 이진 표현에서 설정된 각 비트에 대해 하나의 분리된 트리의 숲이 된다.
여기서 노드의 조상은 자신의 범위 합을 포함하는 모든 노드이다. 예를 들어, formula_53은 formula_54의 합을 포함하고, formula_55은 formula_56의 합을 포함한다.
formula_17의 값 중 하나를 수정하려면, formula_47에 변경 사항을 더한 다음, formula_8의 부모, 그 다음 조부모 등으로 인덱스가 formula_6을 초과할 때까지 계속한다.
검색 트리.
다른 두 트리와 달리, 검색 트리는 이진 트리이며 커누스가 "옆으로 된 힙"이라고 부르는 순서로 배열된다. 각 노드에는 인덱스의 이진 표현에서 후행 0의 수와 동일한 높이가 할당되며, 부모와 자식은 인접 높이의 수치적으로 가장 가까운 인덱스이다. 홀수 인덱스(formula_61)를 가진 노드는 리프이다. 짝수 인덱스를 가진 노드는 다음 최저 인덱스의 가장 가까운 두 노드를 자식으로 가지며, formula_62이다. 검색 트리에서 노드 formula_8의 부모는 formula_64이다.
예를 들어, 6 = 1102의 자식은 5 = 1012와 7 = 1112이며, 부모는 4 = 1002이다.
이 트리는 잠재적으로 무한하지만, 우리는 그 루트를 formula_6보다 작거나 같은 2의 가장 큰 거듭제곱인 가장 높은 기존 노드로 정의할 수 있다.
노드가 formula_6보다 큰 인덱스를 가진 가상의 부모를 가질 수 있지만 여전히 기존의 조부모를 가질 수 있다. 위 예제가 5개 노드 트리에 적용된다면, 노드 5는 가상의 부모 6을 가지지만, 기존의 조부모 4를 가진다.
검색 트리는 이전 두 트리의 조합으로 간주될 수 있다. 노드의 왼쪽 서브트리는 업데이트 트리의 모든 자손을 포함하고, 오른쪽 서브트리는 쿼리 트리의 모든 자손을 포함한다. 검색 트리에서 노드의 부모는 쿼리 또는 업데이트 부모(노드가 각각 오른쪽 또는 왼쪽 자식인지에 따라 다름)이며, 다른 유형의 부모는 검색 트리에서 여러 번 위로 이동하여 찾을 수 있다.