데이터 구조의 무작위 손가락 검색 트리

결정적 탐색 트리에 대한 두 가지 무작위 대안은 무작위 이진 탐색 트리, 트레프 및 건너뛰기 목록입니다. treap과 skip 목록은 모두 우아한 데이터 구조로 정의되며, 여기서 무작위화는 간단하고 효율적인 업데이트 작업을 용이하게 합니다.

이 섹션에서는 트리프와 건너뛰기 목록이 데이터 구조를 변경하지 않고 효율적인 손가락 검색 트리로 구현될 수 있는 방법을 설명합니다. 두 데이터 구조 모두 예상 O(log d) 시간을 소비하여 손가락 검색을 지원합니다. 여기서 예상은 데이터 구조를 구성하는 동안 알고리즘에 의해 생성된 무작위 선택보다 우선합니다.

목록 건너뛰기

건너뛰기 목록에서 이 지점에서 검색을 계속하면 b 요소를 포함하는 노드에서 요소를 손가락으로 검색할 수 있습니다. a b이면 순방향으로 검색이 진행됩니다. 역방향 케이스는 건너뛰기 목록에서 일반 검색과 대칭이지만 정방향 케이스는 실제로 더 복잡합니다. 일반적으로 스킵 리스트에서의 검색은 리스트의 시작에 있는 센티넬이 가장 높은 노드로 간주되기 때문에 빠를 것으로 예상됩니다. 그러나 우리의 손가락은 높이가 1인 노드와 연관될 수 있습니다. 이 때문에 검색을 시도하는 동안 거의 오르지 않을 수 있습니다. 평소에는 절대 일어나지 않는 일. 그러나 이러한 복잡성에도 불구하고 O(log d) 예상 검색 시간을 달성할 수 있습니다.

트립

Treap은 BST(Randomized Binary Search Tree)로 정의됩니다. Treap에서 검색하는 것은 다른 BST에서 요소를 검색하는 것과 유사합니다. 그러나 Treaps는 distanced의 두 요소 사이의 예상 경로 길이가 O(log d)로 표시되는 속성을 가지고 있습니다. 따라서 요소 a에 대한 요소 b를 포함하는 노드에서 손가락 검색을 하려면 요소 a의 조상이 발견될 때까지 b 요소에서 트리를 올라갈 수 있으며, 이 지점에서 일반적인 BST 검색은 일반적인 방식으로 진행됩니다. 노드가 다른 노드의 조상인지 계산하는 것은 중요하지 않지만 예상 O(log d) 손가락 검색 시간을 제공하기 위해 이 형식의 쿼리를 지원하도록 트리를 확장할 수 있습니다.