스킵 리스트

스킵 리스트(skip list)는 정렬된 원소를 빠르게 탐색, 삽입, 삭제할 수 있도록 설계된 확률적 자료구조이다. 1989년 William Pugh가 제안하였으며, 연결 리스트(linked list)의 구조를 확장하여 이진 탐색 트리 수준의 효율성을 얻을 수 있도록 고안되었다.

개요

스킵 리스트는 여러 수준의 연결 리스트를 위로 확장한 구조를 가진다. 기본 연결 리스트는 가장 하위 레벨에 존재하며, 그 위로 확률적으로 선택된 노드들만 포함하는 상위 레벨들이 존재한다. 각 노드는 자신이 속한 레벨의 다음 노드를 가리키는 포인터를 가진다. 탐색, 삽입, 삭제 등의 연산은 상위 레벨부터 내려가며 진행되어, 일반 연결 리스트보다 빠른 속도를 제공한다.

구조

스킵 리스트는 레벨(level)의 개념을 기반으로 구성된다.

• Level 0: 전체 원소를 포함하는 기본 연결 리스트
• Level 1 이상: 일정 확률(p, 일반적으로 1/2 또는 1/4)에 따라 무작위로 선택된 노드만 포함
• Head node: 모든 레벨의 시작점을 포함하는 특수 노드

노드마다 여러 개의 포인터가 있으며, 자신의 레벨 수에 따라 상위 레벨까지 연결된다.

연산

스킵 리스트는 다음과 같은 주요 연산을 효율적으로 수행할 수 있도록 설계되었다.

• 탐색
  • 탐색 연산은 찾고자 하는 키 값 k에 대해, 가장 높은 레벨에서 시작하여 오른쪽으로 이동하면서 현재 노드의 다음 노드의 키가 k 이하일 때까지 진행한다.
  • 조건이 만족되지 않으면 한 단계 아래 레벨로 내려가 같은 과정을 반복하며, 최하위 레벨까지 도달한 후 k 이하의 가장 큰 키 값을 갖는 노드를 찾는다.

• 삽입
  • 삽입할 위치는 탐색 연산을 통해 찾는다. 그 후, 새 노드의 레벨을 확률적으로 결정하여 해당 레벨까지의 포인터를 조정한다.
  • 새 노드는 0번 레벨(가장 아래)부터 자신의 레벨까지의 모든 레벨에서 연결되어야 하며, 각 레벨마다 이전 노드의 포인터를 적절히 갱신해야 한다.
  • 레벨이 기존 최대 레벨보다 높아지면, 리스트의 레벨도 확장된다.

• 삭제
  • 삭제 연산도 먼저 탐색을 통해 삭제 대상 노드를 찾는다.
  • 이후 해당 노드가 존재하는 각 레벨에서 연결 포인터를 수정하여 노드를 제거한다.
  • 삭제 이후 상위 레벨에서 더 이상 노드가 없다면 리스트의 전체 레벨을 줄이는 작업이 수행된다.

시간 복잡도

스킵 리스트는 다음과 같은 평균 시간 복잡도를 갖는다.

• 탐색: O(log n)
• 삽입: O(log n)
• 삭제: O(log n)

최악의 경우 O(n)일 수 있으나, 확률적 구조 덕분에 평균적으로는 균형잡힌 이진 탐색 트리와 유사한 성능을 가진다.

탐색

• 최상위 레벨에서 시작하여 다음 규칙에 따라 탐색한다.
  • 현재 노드의 다음(next) 노드의 키가 찾고자 하는 키보다 작으면 → 오른쪽으로 이동
  • 그 외의 경우 → 한 단계 아래 레벨로 내려감
• 레벨 0까지 반복하면서, 마지막으로 지나간 노드를 반환한다.
• 탐색은 각 레벨당 평균 한 번씩 이동하므로, 전체 기대 시간은 O(log n)이다.

삽입

• 새 노드의 레벨은 확률 p (일반적으로 1/2)에 따라 무작위로 결정된다.
  • 레벨 k가 선택될 확률은 p^(k+1), 예를 들어 p=1/2이면 (1/2)^(k+1)
• 삽입 위치 찾기 (검색 단계)
  • 탐색과 동일하게 최고 레벨부터 오른쪽으로 이동하고, 조건이 맞지 않으면 아래로 내려가며 레벨 0까지 반복
  • 각 레벨에서 새 노드가 삽입될 위치의 직전 노드를 기록
  • 이 탐색 단계의 기대 시간은 O(log n)
• 포인터 갱신 (삽입 단계)
  • 선택된 최고 레벨 h에 대해, 각 레벨 i (0 ≤ i ≤ h)에 대해 다음을 수행***새 노드의 next[i]를 prev[i].next[i]로 지정
    • prev[i].next[i]를 새 노드로 갱신
  • 레벨 h의 기대값은 상수 수준이므로, 이 단계의 기대 시간은 O(1)
• 삽입 전체 기대 시간: O(log n)

=== 삭제 ===*삭제할 노드의 위치를 탐색하는 과정은 삽입 시와 동일하게 수행된다.

• • 최상위 레벨에서 시작하여, 각 레벨에서 삭제 대상 노드 직전까지 이동
  • 레벨 0에서 삭제할 노드를 확인
  • 이 탐색 단계의 기대 시간은 O(log n)
• 포인터 갱신 (삭제 단계)
  • 삭제할 노드가 레벨 h에 존재한다고 할 때, 각 레벨 i (0 ≤ i ≤ h)에 대해
    • prev[i].next[i]를 삭제 노드의 next[i]로 갱신
  • 레벨 h의 기대값은 상수 수준이므로, 이 단계의 기대 시간은 O(1)
• 삭제 전체 기대 시간: O(log n)

공간 복잡도

• 각 키가 레벨 k를 갖는 확률은 1/2^(k+1)
• 따라서 레벨 k에 속하는 노드 수의 기대값은 n × 1/2^(k+1)
• 모든 레벨을 더하면
  • n×(1/2 + 1/4 + 1/8 + …) = n
• 결국 원래 리스트와 상위 레벨들을 합하면 2n이다. 따라서 선형 복잡도 수준이므로,
• 결론: 기대 공간 복잡도는 O(n)입니다.

예제

다음은 Python에서 간단한 스킵 리스트 노드 구조의 예시이다.

import random

class SkipNode:
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level, p):
        self.max_level = max_level
        self.p = p
        self.header = SkipNode(None, max_level)
        self.level = 0

    def random_level(self):
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

장점

• 간단한 구현으로도 이진 탐색 트리 수준의 성능 달성
• 포인터 조작만으로 동적 삽입, 삭제에 용이
• 동시성 제어가 상대적으로 쉬움 (Lock-free skip list 구현 등)

단점

• 공간 사용량 증가 (다수의 포인터 필요)
• 성능이 확률에 의존함

같이 보기

• 이진 탐색 트리
• 연결 리스트
• 해시 테이블
• AVL 트리
• 동시성 제어

참고 문헌

• William Pugh (1990). "Skip Lists: A Probabilistic Alternative to Balanced Trees". Communications of the ACM.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms. MIT Press.