데이터 구조에서 핑거 탐색(finger search)은 해당 구조가 지원하는 일반적인 탐색 연산을 확장한 개념입니다. 쿼리와 함께 데이터 구조 내 특정 요소를 가리키는 참조(핑거, finger)가 추가로 주어진다는 점이 특징입니다. 일반적인 요소 탐색 시간은 데이터 구조에 포함된 요소의 개수에 대한 함수로 표현되지만, 핑거 탐색의 시간은 목표 요소와 핑거 사이의 거리에 대한 함수로 다룹니다.
거리의 정의와 시간 복잡도
m개의 요소로 이루어진 집합에서 두 요소 a와 b 사이의 거리 d(a, b)는 두 요소의 순위(rank) 차이로 정의됩니다. 예를 들어 a와 b가 각각 i번째, j번째로 큰 요소라면 거리는 |i − j|가 됩니다. 어떤 구조에서 일반 탐색이 O(f(m))의 시간이 소요된다면, 이상적으로는 핑거 b에서 요소 a를 찾는 핑거 탐색은 O(f(d))의 시간을 소모해야 합니다.
d ≤ m이므로 최악의 경우 핑거 탐색은 일반 탐색보다 나쁘지 않습니다. 그러나 실제로는 이렇게 퇴화된(degenerate) 핑거 탐색이 일반 탐색보다 더 많은 작업을 수행할 수 있습니다. 예를 들어 f(n) = log n이고, 핑거 탐색이 최악의 경우 일반 탐색보다 두 배의 비교를 수행한다면, d > √n일 때는 오히려 핑거 탐색이 더 느려집니다. 따라서 핑거 탐색은 목표 요소가 핑거 근처에 있을 것이라고 합리적으로 기대할 수 있는 경우에만 구현하는 것이 바람직합니다.
구현 방식
널리 쓰이는 일부 데이터 구조는 구조 자체를 변경하지 않고도 핑거 탐색을 지원합니다. 요소 a를 찾기 위해 탐색 구간(interval)을 좁혀 가는 방식으로 탐색을 수행하는 구조에서는, 요소 b로부터의 핑거 탐색이 일반적으로 다음과 같이 이루어집니다. 먼저 b에서부터 탐색 과정을 역으로 되돌려 탐색 구간이 요소 a를 포함할 만큼 충분히 커질 때까지 확장한 뒤, 그 시점부터는 평소처럼 탐색을 진행합니다.
정렬된 연결 리스트
연결 리스트에서는 보통 한쪽 끝에서 다른 쪽 끝까지 순회하며 선형적으로 요소를 탐색합니다. 그러나 리스트가 정렬되어 있고 요소 b를 담고 있는 노드에 대한 참조가 있다면, b에서 탐색을 시작함으로써 요소 a를 O(d) 시간 안에 찾을 수 있습니다.
정렬된 배열
정렬된 배열 B에서는 일반적으로 이진 탐색(binary search)으로 요소 a를 찾습니다. 핑거 탐색은 B[j] = b에서 시작하는 단측 탐색(one-sided search)으로 구현합니다. 이진 탐색이 매 비교마다 탐색 공간을 절반으로 줄이는 반면, 단측 탐색은 매 비교마다 탐색 공간을 두 배로 넓힙니다. 구체적으로, 단측 탐색의 k번째 반복(a > b라고 가정)에서 고려되는 구간은 B[j, j+2k−1]입니다. B[j + 2k−1] ≥ a가 되는 순간 확장을 멈추고, 해당 구간을 대상으로 이진 탐색을 수행해 요소 a를 찾습니다. 단측 탐색이 k번의 반복으로 a를 포함하는 구간을 찾았다면 d > 2k−2임을 알 수 있습니다. 이 범위를 이진 탐색하는 데에도 k번의 반복이 추가로 필요하므로, b에서 a를 향한 핑거 탐색은 O(k) = O(log d)의 시간을 소모합니다.
스킵 리스트(Skip List)
스킵 리스트에서는 요소 b를 담고 있는 노드에서부터 탐색을 이어가는 방식으로 요소 a에 대한 핑거 탐색을 수행할 수 있습니다. a < b라면 뒤쪽 방향으로, a > b라면 앞쪽 방향으로 탐색이 진행됩니다. 후방 탐색은 스킵 리스트의 일반 탐색과 대칭적이지만, 전방 탐색은 실제로 더 복잡합니다. 일반적으로 스킵 리스트의 탐색이 빠른 이유는 리스트 시작 부분의 센티넬(sentinel)이 가장 높은 노드로 간주되기 때문입니다. 그러나 핑거가 되는 노드는 높이 1짜리 노드일 수 있습니다. 이 때문에 탐색 도중 드물게 위로 올라가야 하는 상황이 발생할 수 있으며, 이는 일반 탐색에서는 결코 일어나지 않는 일입니다. 그럼에도 불구하고 이런 복잡성이 있더라도 기대 탐색 시간 O(log d)를 달성할 수 있습니다.
트랩(Treap)
트랩(treap)은 무작위화된 이진 탐색 트리(randomized BST)로 정의됩니다. 트랩에서의 탐색은 다른 BST에서의 탐색과 유사합니다. 다만 트랩은 거리가 d만큼 떨어진 두 요소 사이의 기대 경로 길이가 O(log d)라는 성질을 가집니다. 따라서 요소 b를 담은 노드에서 요소 a를 향해 핑거 탐색을 하려면, b에서부터 트리를 위로 올라가며 a의 조상(ancestor)을 찾고, 조상을 발견한 시점부터는 일반적인 BST 탐색을 진행하면 됩니다. 한 노드가 다른 노드의 조상인지 판단하는 것은 간단하지 않지만, 트리를 증강(augment)하여 이러한 형태의 질의를 지원하게 하면 기대 시간 O(log d)의 핑거 탐색을 제공할 수 있습니다.
로프(Rope)와 트리
로프(rope) 자료구조의 구현체는 일반적으로 위치 반복자(cord position iterator)를 사용해 문자열을 순회합니다. 이 반복자는 문자열의 특정 문자를 가리키는 핑거로 볼 수 있습니다. 대부분의 균형 트리와 마찬가지로, 로프는 트리의 루트만 주어졌을 때 잎(leaf) 하나의 데이터를 얻는 데 O(log m)의 시간이 필요합니다. 트리의 모든 잎을 읽으려면 O(m·log m)의 시간이 필요할 것으로 보이지만, 약간의 추가 정보를 저장하면 반복자가 다음 잎을 O(1) 시간에 읽고, 트리의 모든 잎을 O(m) 시간에 읽도록 구현할 수 있습니다.