X-Fast Trie
X-fast trie| X-Fast Trie | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 유형 | 트리 | ||||||||||||||||||||
| 발명된 | 1982 | ||||||||||||||||||||
| 발명자 | 댄 윌러드 | ||||||||||||||||||||
| 빅 O 표기의 시간 복잡도 | |||||||||||||||||||||
| |||||||||||||||||||||
컴퓨터 과학에서 x-fast trie는 경계 영역의 정수를 저장하기 위한 데이터 구조입니다.O(n log M) 공간을 사용하여 시간 O(log log M)에서 정확하게 이전 쿼리 또는 후속 쿼리를 지원합니다.여기서 n은 저장된 값의 수, M은 도메인 내의 최대값입니다.이 구조는 1982년 [1]Dan Willard에 의해 더욱 복잡한 y-fast trie와 함께 O(log log M) 쿼리 시간을 유지하면서 van Emde Boas 트리의 공간 사용을 개선하기 위한 방법으로 제안되었다.
구조.
x-fast trie는 비트 단위 trie입니다.각 서브트리는 공통 프레픽스로 시작하는 바이너리 표현을 가진 값을 저장합니다.각 내부 노드에는 서브트리의 값에 대한 공통 프레픽스로 라벨이 붙습니다.일반적으로 왼쪽 아이는 프레픽스 끝에0 을 추가하고 오른쪽 아이는 1 을 추가합니다.0 ~ M - 1 의 정수의 바이너리 표현에서는, 「log2 M」비트를 사용하고 있기 때문에, 트라이의 높이는 O(log M)입니다.
x-fast trie의 모든 값은 Leaf에 저장됩니다.내부 노드는 하위 트리에 리프가 있는 경우에만 저장됩니다.내부 노드에 왼쪽 자식이 없는 경우 대신 오른쪽 하위 트리에 하위 포인터라고 하는 최소 리프 포인터를 저장합니다.마찬가지로 오른쪽 자식이 없는 경우 왼쪽 서브트리에서 가장 큰 리프 포인터를 저장합니다.각 리프에는 이전 리프 및 후속 리프 포인터가 저장되어 이중 링크 리스트가 형성됩니다.마지막으로 각 레벨의 해시 테이블에는 해당 레벨의 모든 노드가 포함됩니다.이러한 해시 테이블은 함께 Level-Search Structure(LSS; 레벨 검색 구조)를 형성합니다.최악의 쿼리 시간을 보장하기 위해 이러한 해시 테이블은 동적 완전 해시 또는 뻐꾸기 해시를 사용해야 합니다.
각 요소에는 길이 O(log M)의 루트부터 리프까지의 경로가 있기 때문에 총 공간 사용량은 O(n log M)입니다.
운용
van Emde Boas 트리와 마찬가지로 x-fast tries는 정렬된 연관 배열의 작업을 지원합니다.여기에는 통상적인 어소시에이트 어레이 조작과 더불어 Successor와 Previator의 2개의 주문 조작이 포함됩니다.
- Find(k): 지정된 키와 관련된 값을 찾습니다.
- Successor(k): 지정된 키보다 크거나 같은 최소 키를 가진 키/값 쌍을 찾습니다.
- 이전 버전(k): 지정된 키보다 크거나 작은 키를 가진 키/값 쌍을 찾습니다.
- 삽입(k, v): 지정된 키/값 쌍을 삽입합니다.
- 삭제(k): 지정된 키를 사용하여 키/값 쌍을 제거합니다.
검색
데이터 구조 내의 키 k와 관련된 값은 모든 리프의 [2]해시 테이블인 LSS[0]에서 k를 검색하여 일정 시간 내에 찾을 수 있습니다.
후계자 및 전임자
키 k의 후계자 또는 선행자를 찾으려면 먼저 k의 가장 낮은 조상인 A를 찾습니다k.이 노드는 trie에서 k와 가장 긴 공통 프레픽스를 가진 노드입니다.A를 찾기k 위해 레벨에서 이진 검색을 수행합니다.레벨 h/2부터 시작합니다.여기서 h는 트라이의 높이입니다.각 레벨에서 적절한 길이의 접두사 k를 사용하여 레벨 검색 구조의 대응하는 해시 테이블을 쿼리합니다.이 프리픽스를 가진 노드가 존재하지 않는 경우 A는 상위 레벨이어야 하며k 검색은 상위 레벨로 제한됩니다.이 프레픽스를 가진 노드가 존재할 경우k A는 상위 레벨일 수 없으므로 검색을 현재 레벨과 하위 레벨로 제한합니다.
k의 가장 낮은 조상을 찾으면 k는 하위 트리 중 하나에 잎이 있고(그렇지 않으면 trie에 있지 않습니다), k는 다른 하위 트리에 있어야 합니다.따라서 하위 포인터는 k의 후속 또는 이전을 가리킵니다.어느 쪽을 찾느냐에 따라 다음 리프 또는 이전 리프 링크 목록에서 한 단계를 수행해야 할 수도 있습니다.
trie의 높이가 O(log M)이므로 가장 낮은 상위 항목에 대한 이진 검색에 O(log log M) 시간이 걸립니다.그 후, 후계자 또는 선행자를 일정 시간 내에 찾을 수 있으므로 총 쿼리 시간은 O(log log M)[1]가 됩니다.
삽입
키와 값의 쌍(k, v)을 삽입하려면 먼저 k의 이전과 후속을 찾습니다.그런 다음 k의 새 리프를 생성하여 후속 리프와 이전 리프의 링크 목록에 삽입하고 v에 대한 포인터를 제공합니다.다음으로는 루트에서 새 리프로 이동하여 필요한 노드를 만들고 필요에 따라 각 해시 테이블에 삽입하여 하위 포인터를 업데이트합니다.
trie의 전체 높이를 내려가야 하기 때문에 이 과정은 O([3]log M) 시간이 걸립니다.
삭제
키 k를 삭제하려면 리프 위에 있는 해시 테이블을 사용하여 리프를 찾습니다.링크 목록에서 삭제하지만 후속 버전과 이전 버전 중 어느 쪽이 해당 버전인지 기억합니다.그런 다음 하위 트리가 k개만 포함하는 모든 노드를 제거하고 필요에 따라 하위 포인터를 업데이트하면서 리프에서 트리의 루트로 이동합니다.k를 가리켰던 하위 포인터는 이제 누락된 하위 트리에 따라 k의 후속 또는 이전 중 하나를 가리킵니다.
삽입과 마찬가지로 이 작업에는 O(log M) 시간이 걸립니다.트라이의 [3]모든 레벨을 통과해야 하기 때문입니다.
논의
Willard는 x-fast tries를 주로 O(n) 공간만 사용하고 O(log log M) [1]시간에 삽입 및 삭제를 허용하면서 동일한 쿼리 시간을 제공하는 y-fast tries의 도입으로 도입했습니다.
patricia tries와 유사한 압축 기술을 사용하여 실제로 [4]x-fast try의 공간 사용을 크게 줄일 수 있습니다.
레벨에 대한 바이너리 검색 전에 지수 검색을 사용하여 현재 프리픽스x뿐만 아니라 그 후계자x + 1을 쿼리함으로써 x-fast tries는 시간 O(log log δ) 내에 이전 쿼리와 후속 쿼리에 응답할 수 있습니다.여기서 δ는 쿼리 값과 이전 값 또는 [2]후속 쿼리의 차이입니다.
레퍼런스
- ^ a b c Willard, Dan E. (1983). "Log-logarithmic worst-case range queries are possible in space Θ(N)". Information Processing Letters. Elsevier. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3. ISSN 0020-0190.
- ^ a b Bose, Prosenjit; Douïeb, Karim; Dujmović, Vida; Howat, John; Morin, Pat (2010), Fast Local Searches and Updates in Bounded Universes (PDF), Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pp. 261–264
- ^ a b Schulz, André; Christiano, Paul (2010-03-04). "Lecture Notes from Lecture 9 of Advanced Data Structures (Spring '10, 6.851)" (PDF). Retrieved 2011-04-13.
- ^ Kementsietsidis, Anastasios; Wang, Min (2009), Provenance Query Evaluation: What's so special about it?, Proceedings of the 18th ACM conference on Information and knowledge management, pp. 681–690
