결정론적 탐색 트리(deterministic search tree)에 대한 무작위화(randomized) 기반 대안으로는 무작위 이진 탐색 트리인 트립(treap)과 스킵 리스트(skip list)가 대표적입니다. 두 자료 구조 모두 우아한 설계로 평가받으며, 무작위성을 활용해 단순하면서도 효율적인 갱신 연산을 가능하게 합니다.
이 글에서는 자료 구조 자체를 변경하지 않고도 트립과 스킵 리스트를 효율적인 손가락 검색 트리(finger search tree)로 구현할 수 있는 방법을 살펴봅니다. 두 자료 구조 모두 기대 시간(expected time) O(log d) 안에 손가락 검색을 수행할 수 있으며, 여기서 기대값은 자료 구조를 구축하는 과정에서 알고리즘이 생성하는 무작위 선택들에 대해 계산된다는 점이 특징입니다.
스킵 리스트(Skip List)에서의 손가락 검색
스킵 리스트에서는 원소 b를 담고 있는 노드에서 출발하여 단순히 그 지점부터 검색을 이어가는 방식으로 원소 a에 대한 손가락 검색을 수행할 수 있습니다. 만약 a < b라면 검색은 뒤쪽(역방향)으로 진행되고, a > b라면 앞쪽(정방향)으로 진행됩니다.
역방향 검색은 일반적인 스킵 리스트 검색과 대칭적인 구조를 가지지만, 정방향 검색은 상대적으로 더 복잡합니다. 일반적으로 스킵 리스트의 검색이 빠른 이유는 리스트 시작 부분의 센티넬(sentinel, 경계 노드)이 가장 높은 노드로 취급되기 때문입니다. 그러나 손가락(finger)이 높이 1짜리 낮은 노드와 연관되어 있을 수도 있습니다. 이로 인해 검색 도중 드물게 위로 올라가는(climb) 동작이 발생할 수 있는데, 이는 평소의 검색에서는 절대 나타나지 않는 상황입니다.
그럼에도 불구하고 이러한 복잡성에도 불구하고, 기대 시간 O(log d)의 검색 성능을 충분히 달성할 수 있다는 점이 주목할 만합니다.
트립(Treap)에서의 손가락 검색
트립은 무작위화된 이진 탐색 트리(randomized binary search tree, BST)로 정의됩니다. 트립에서의 검색은 다른 어떤 BST에서의 검색과 본질적으로 동일한 방식으로 이루어집니다. 다만 트립에는 거리가 d만큼 떨어진 두 원소 사이의 기대 경로 길이가 O(log d)라는 중요한 성질이 있습니다.
따라서 원소 b를 포함하는 노드에서 원소 a를 향해 손가락 검색을 수행하려면, 먼저 b에서부터 트리를 따라 위로 올라가며 a의 조상(ancestor) 노드를 찾습니다. 조상을 발견한 시점부터는 일반적인 BST 검색 방식으로 진행하면 됩니다. 한 노드가 다른 노드의 조상인지 판단하는 것은 사소한 작업이 아니지만, 트리에 추가 정보(augmentation)를 보강하여 이러한 형태의 질의를 지원하도록 하면 기대 시간 O(log d)의 손가락 검색을 구현할 수 있습니다.