스킵 리스트

스킵 리스트는 AVL 트리나 레드-블랙 트리와 동일한 로그 시간 복잡도를 가지는 확률적 데이터 구조다. 검색과 업데이트 연산을 효율적으로 지원하면서도 다른 맵 데이터 구조에 비해 구현이 상대적으로 간단하다.

스킵 리스트 S는 계층적으로 구성된 정렬된 연결 리스트 *{L0, ..., Ln}*로 이루어져 있다. 각 계층 L은 L0 계층의 항목들을 점진적으로 포함한다. {L1, ... Ln} 계층의 항목들은 동전 던지기 함수를 기반으로 1/2의 확률로 무작위로 선택된다. 탐색을 위해 각 계층의 항목은 아래 계층의 노드와 다음 노드에 대한 참조를 가지고 있다. 이 계층들은 아래 계층으로 향하는 고속 차선 역할을 하여, 차선을 건너뛰고 이동 거리를 줄임으로써 빠른 O(log n) 탐색을 가능하게 한다. 최악의 경우에는 일반 연결 리스트와 마찬가지로 O(n)으로 탐색 성능이 저하된다.

스킵 리스트 S의 특징은 다음과 같다:

리스트 L0은 삽입된 모든 항목을 포함한다.
리스트 *{L1, ..., Ln}*에서 Li는 Li-1의 항목들 중 무작위로 선택된 부분집합을 포함한다.
높이는 동전 던지기를 통해 결정된다.

그림 1

검색 과정

엘리먼트 N을 검색할 때는 가장 상위 레이어 Ln부터 시작해 L0까지 탐색한다.

목표는 현재 레이어의 가장 오른쪽 위치에서 값이 목표 항목보다 작고, 다음 노드의 값이 목표 항목보다 크거나 같거나 nil인 엘리먼트 K를 찾는 것이다 (K.key < N.key <= (K.next.key or nil)). 만약 K.next의 값이 N과 같다면 검색을 종료하고 K.next를 반환한다. 그렇지 않다면 K.down을 사용해 아래 레이어(레이어 Ln-1)로 이동한 후 동일한 과정을 반복한다. 이 과정은 K.down이 nil인 L0 레이어에 도달할 때까지 계속되며, L0에서도 해당 항목을 찾지 못하면 항목이 존재하지 않음을 의미한다.

삽입 과정

엘리먼트 N을 삽입하는 과정은 검색과 유사하다. 최상위 레이어 Ln부터 L0까지 탐색을 진행한다. 이때 탐색 경로를 스택에 기록해둔다. 이 스택은 동전 던지기가 시작될 때 위쪽으로 경로를 탐색할 수 있게 도와주며, 새로운 엘리먼트를 삽입하고 참조를 업데이트하는 데 사용된다.

목표는 레이어 Ln의 가장 오른쪽 위치에서 값이 새로운 항목보다 작고, 다음 노드의 값이 크거나 nil인 엘리먼트 K를 찾는 것이다 ( K.key < N.key < (K.next.key or nil) ). 엘리먼트 K를 스택에 넣고, K.down을 사용해 아래 레이어(Ln-1)로 이동한 후 같은 과정(전진 탐색)을 반복한다. 이 과정은 K.down이 nil이 될 때까지 계속되며, 이는 레이어 L0에 도달했음을 의미한다.

L0에서는 N을 K 뒤에 삽입할 수 있다.

여기서 흥미로운 부분은 동전 던지기 함수를 사용해 무작위로 레이어를 생성하는 것이다.

동전 던지기 함수가 0을 반환하면 전체 과정이 종료된다. 하지만 1을 반환하면 두 가지 가능성이 있다: