Y패스트 트리에
Y-fast trie| Y패스트 트리에 | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 유형 | 트리 | ||||||||||||||||||||
| 발명된 | 1982 | ||||||||||||||||||||
| 발명자 | 댄 윌러드 | ||||||||||||||||||||
| 빅 O 표기의 시간 복잡도 | |||||||||||||||||||||
| |||||||||||||||||||||
컴퓨터 과학에서 y-fast trie는 경계 영역의 정수를 저장하기 위한 데이터 구조입니다.O(n) 공간을 사용하여 시간 O(log log M)에서 정확하게 이전 쿼리 또는 후속 쿼리를 지원합니다.여기서 n은 저장된 값의 수, M은 도메인 내의 최대값입니다.이 구조는 1982년[1] Dan Willard에 의해 x-fast trie에 의해 사용되는 O(n log M) 공간을 줄이기 위해 제안되었다.
구조.
y-fast trie는 2개의 데이터 구조로 구성됩니다.상단은 x-fast trie이고 하단은 다수의 균형 잡힌 이진 트리로 구성됩니다.키는 O(log M) 연속 요소의 그룹으로 나뉘며 각 그룹에 대해 균형 잡힌 이진 검색 트리가 생성됩니다.효율적인 삽입 및 삭제를 위해 각 그룹에는 최소 (log M)/4 및 최대 2개의 로그 M [2]요소가 포함됩니다.각 균형 잡힌 이진 검색 트리에 대해 대표 r이 선택됩니다.이러한 표현은 x-fast trie에 저장됩니다.대표 r은 그것과 관련된 트리의 요소일 필요는 없지만, r의 후계자 및 그 후계자에 관련된 트리의 최소 요소보다 작고, r의 이전 요소와 그 이전 버전과 관련된 트리의 최대 요소보다 큰 정수여야 합니다.처음에 트리의 표현은 트리의 최소 요소와 최대 요소 사이의 정수입니다.
x-fast trie에는 O(n/log M) 대표자가 저장되며 각 대표자는 O(log M) 해시 테이블에서 발생하므로 y-fast trie의 이 부분은 O(n) 공간을 사용합니다.균형 잡힌 이진 검색 트리는 O(n) 공간을 사용하는 총 n개의 요소를 저장합니다.따라서 총 y-fast trie는 O(n) 공간을 사용합니다.
운용
van Emde Boas 트리 및 x-fast tries와 마찬가지로 y-fast tries는 정렬된 연관 배열의 동작을 지원합니다.여기에는 통상적인 어소시에이트 어레이 조작과 더불어 Successor와 Previator의 2개의 주문 조작이 포함됩니다.
- Find(k): 지정된 키와 관련된 값을 찾습니다.
- Successor(k): 지정된 키보다 크거나 같은 최소 키를 가진 키/값 쌍을 찾습니다.
- 이전 버전(k): 지정된 키보다 크거나 작은 키를 가진 키/값 쌍을 찾습니다.
- 삽입(k, v): 지정된 키/값 쌍을 삽입합니다.
- 삭제(k): 지정된 키를 사용하여 키/값 쌍을 제거합니다.
검색
키 k는 k보다 큰 최소 대표 r의 트리 또는 r의 전임자 트리 중 하나에 격납할 수 있다.이는 바이너리 서치 트리의 대표가 그 트리에 격납되어 있는 요소일 필요는 없기 때문이다.따라서 먼저 x-fast trie에서 k보다 큰 가장 작은 대표 r을 찾습니다.이 대리인을 사용하여 r의 이전 버전을 가져옵니다.이 두 표현은 두 개의 균형 잡힌 이항 검색 트리를 가리키며, 두 트리 모두 k를 검색합니다.
x-fast trie에서 k보다 큰 최소 대표 r을 찾으려면 O(log log M)가 필요합니다.r을 사용하면 이전 대표 r을 찾으려면 일정한 시간이 걸립니다.O(log M) 요소를 포함하는 2개의 균형 잡힌 바이너리 검색 트리를 검색하려면 각각 O(log log M) 시간이 걸립니다.따라서 키 k와 그 값을 O(log log M) [1]시간 내에 찾을 수 있다.
후계자 및 전임자
키 k 자체와 마찬가지로, 그 후계자는 k보다 큰 가장 작은 대표 r의 트리 또는 이전 r의 트리 중 하나에 저장될 수 있다.따라서 키 k의 후속 값을 찾으려면 먼저 x-fast trie에서 k보다 큰 최소 표현값을 검색합니다.다음으로 이 담당자를 사용하여 x-fast trie에서 이전 버전을 가져옵니다.이 두 표현은 두 개의 균형 잡힌 이진 검색 트리를 가리키며, 하나는 [3]k의 후속 값을 검색합니다.
x-fast trie에서 k보다 큰 최소 대표 r을 찾는 데는 O(log log M) 시간이 걸리고 r을 사용하여 이전 버전을 찾는 데는 일정한 시간이 걸립니다.O(log M) 요소를 포함하는 2개의 균형 잡힌 바이너리 검색 트리를 검색하려면 각각 O(log log M) 시간이 걸립니다.따라서 키 k의 후계자와 그 값을 O([1]log log M)시간 내에 취득할 수 있다.
키 k의 이전 키를 검색하는 것은 후속 키를 찾는 것과 매우 유사합니다.하나는 x-fast trie에서 k보다 작은 가장 큰 대표 r을 검색하고 다른 하나는 r을 사용하여 x-fast trie에서 이전 r을 가져옵니다.마지막으로 이 두 대표자의 균형 잡힌 2진수 검색 트리를 검색하여 k의 전자를 찾습니다.이 작업에는 O(log log M) 시간이 걸립니다.
삽입
새 키/값 쌍(k, v)을 삽입하려면 먼저 k를 삽입해야 하는 균형 잡힌 이진 검색 트리를 결정해야 합니다.이를 위해 k의 후계자를 포함하는 트리 T를 찾을 수 있다.다음으로 T에 k를 삽입합니다.모든 밸런스 바이너리 검색 트리에 O(log M) 요소가 포함되도록 하기 위해 T를 2개의 밸런스 바이너리 트리로 분할하고 로그 M 요소가 3개 이상 포함되어 있는 경우 x-fast trie에서 대표자를 삭제합니다.두 개의 새로운 균형 이진 검색 트리 각각에는 최대 로그 M + 1개의 요소가 포함됩니다.각 트리의 대표자를 뽑아 x-fast trie에 삽입합니다.
k의 후계자를 찾으려면 O(log log M) 시간이 걸립니다.O(log M) 요소를 포함하는 균형 잡힌 이진 검색 트리에 k를 삽입하는 데도 O(log log M) 시간이 걸립니다.O(log M) 요소를 포함하는 바이너리 검색 트리를 O(log m) 시간으로 분할할 수 있습니다.마지막으로 3명의 대표자를 삽입 및 삭제하는 데 O(log M) 시간이 소요됩니다.단, O(log M) 삽입 및 삭제 시마다 트리를 최대 한 번 분할하므로 상각 시간이 일정하게 소요됩니다.따라서 새 키/값 쌍을 삽입하는 데 O(log log M) 상각 [3]시간이 걸립니다.
삭제
삭제는 삽입과 매우 유사합니다.먼저 균형 잡힌 이진 검색 트리 중 하나에서 키 k를 찾아 이 트리 T에서 삭제합니다.모든 균형 바이너리 검색 트리가 O(log M) 요소를 포함하도록 하기 위해 T가 (log M)/4 요소 미만일 경우 후속 또는 이전 버전의 균형 바이너리 검색 트리와 병합됩니다.병합된 트리의 대표자는 x-fast trie에서 삭제됩니다.병합된 트리에 3개 이상의 로그 M 요소가 포함될 수 있습니다.이 경우 새로 형성된 트리는 크기가 거의 같은 두 개의 트리로 분할됩니다.다음으로, 각 새로운 트리의 새로운 대표자를 선정하여 x-fast trie에 삽입합니다.
키 k를 찾으려면 O(log log M) 시간이 걸립니다.O(log M) 요소를 포함하는 균형 잡힌 이진 검색 트리에서 k를 삭제하는 데도 O(log log M) 시간이 걸립니다.균형 잡힌 이진 검색 트리를 병합하고 분할하려면 O(log log M) 시간이 걸립니다.마지막으로 오래된 대표자를 삭제하고 새로운 대표자를 x-fast trie에 삽입하는 데 O(log M) 시간이 걸립니다.그러나 균형 잡힌 이진 검색 트리는 O(log M) 삽입 및 삭제 때마다 최대 한 번 병합 및 분할됩니다.따라서 상각된 시간이 일정하게 소요됩니다.따라서 키/값 쌍을 삭제하는 데 O(log log M) 상각 [3]시간이 걸립니다.
레퍼런스
- ^ 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.
- ^ 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 c Schulz, André; Christiano, Paul (2010-03-04). "Lecture Notes from Lecture 9 of Advanced Data Structures (Spring '10, 6.851)" (PDF). Retrieved 2011-04-14.
