스킵 리스트의 핑거 탐색이란?
스킵 리스트(Skip List)에서는 이미 요소 b를 담고 있는 노드를 알고 있다면, 그 지점에서 탐색을 이어가 다른 요소 a를 찾는 핑거 탐색(finger search)을 수행할 수 있습니다. 처음부터 전체 리스트를 훑는 대신, 이미 파악한 위치를 출발점으로 삼는 효율적인 탐색 방식입니다.
탐색 방향은 어떻게 결정될까?
찾으려는 값 a와 현재 노드의 값 b를 비교하면 탐색 방향이 정해집니다. a < b이면 탐색은 뒤쪽(역방향)으로 진행되고, a > b이면 앞쪽(정방향)으로 진행됩니다.
역방향 탐색은 일반적인 스킵 리스트 탐색과 대칭적인 구조를 가져 비교적 단순합니다. 반면 정방향 탐색은 실제로 훨씬 더 까다롭습니다.
정방향 탐색이 복잡한 이유
평소 스킵 리스트 탐색이 빠르게 동작하는 이유는 리스트 맨 앞의 센티넬(sentinel) 노드가 가장 높은 노드로 간주되기 때문입니다. 덕분에 상위 레벨부터 시작해 빠르게 탐색 범위를 좁혀 나갈 수 있습니다.
그러나 핑거(finger)가 높이 1짜리 낮은 노드와 연결되어 있을 수도 있습니다. 이런 경우 탐색 도중 위로 올라가야 하는 상황이 드물게 발생할 수 있는데, 이는 일반적인 탐색에서는 절대 일어나지 않는 현상이기 때문에 처리가 까다롭습니다.
스킵 리스트의 핵심 성질
스킵 리스트의 가장 중요한 특성은 다음과 같습니다.
- 공간 효율성: 기대 선형(expected linear) 공간만 필요합니다.
- 레벨 구조: 기대 O(log n)개의 레벨로 구성됩니다.
- 탐색 속도: 기대 O(log n) 시간에 탐색이 가능합니다.
- 삽입·삭제: 주어진 위치에서 기대 O(1) 시간에 삽입과 삭제를 지원합니다.
역방향 핑거 탐색을 위한 자료 구조
스킵 리스트의 다양한 성질과 확장에 관한 연구에서는, 핑거 탐색이 기대 O(log d) 시간(d는 두 요소 사이의 거리)에 수행되도록 하는 의사 코드도 함께 제시되었습니다.
역방향 핑거 탐색을 원활하게 하기 위해, 노드 V를 가리키는 핑거는 기대 O(log n) 공간을 사용하는 핑거 자료 구조로 저장됩니다. 이 자료 구조는 각 레벨 i마다 V의 왼쪽에 있는 노드를 가리키는 포인터를 보관하며, 해당 레벨의 포인터는 V 자신 또는 V보다 오른쪽에 있는 노드를 가리킬 수 있습니다. 핑거를 이동시킬 때는 이 포인터 목록을 그에 맞춰 갱신해야 합니다.
역방향 핑거 탐색의 동작 순서
역방향 핑거 탐색은 다음과 같이 진행됩니다.
- 핑거 자료 구조 안에서 탐색 키 y보다 왼쪽에 위치한 가장 낮은 노드를 찾습니다. 이때 노드들은 레벨이 증가하는 순서대로 살펴봅니다.
- 식별된 노드에서부터 표준 스킵 리스트 탐색과 유사한 방식으로 아래 방향으로 탐색을 이어갑니다.