스킵리스트

스킵리스트(skip list)는 정렬된 요소들의 리스트에서 효율적인 탐색, 삽입, 삭제를 가능하게 하기 위해 여러 개의 레벨을 도입한 확률 기반의 자료구조이다.

1 개요

스킵리스트는 1990년 William Pugh가 제안한 자료구조로, 균형 이진 탐색 트리와 유사한 성능을 가지면서도 구현이 간단한 것이 특징이다. 각 요소는 여러 레벨의 연결 리스트에 포함될 수 있으며, 레벨이 높을수록 더 많은 원소를 건너뛰며 빠르게 탐색할 수 있다. 이러한 구조를 통해 평균적으로 O(log n)의 시간 복잡도로 탐색, 삽입, 삭제가 가능하다.

2 구조

스킵리스트는 여러 층의 연결 리스트로 구성되며, 각 층은 하위 층을 참조할 수 있는 노드들로 이루어져 있다. 가장 아래층은 모든 원소를 포함한 기본 리스트이며, 위쪽 레벨로 올라갈수록 선택된 일부 노드들만 포함된다. 노드가 상위 레벨로 포함될 확률은 일반적으로 1/2로 설정된다.

3 연산

스킵리스트에서의 주요 연산은 다음과 같다.

• 탐색: 가장 높은 레벨부터 시작하여 오른쪽으로 이동하며 탐색하고, 더 이상 진행할 수 없으면 한 단계 아래로 내려가며 반복한다.
• 삽입: 삽입 위치를 찾은 후, 임의의 확률로 레벨을 결정하여 해당 위치에 노드를 삽입한다.
• 삭제: 탐색을 통해 삭제할 노드를 찾고, 각 레벨에서 해당 노드를 제거한다.

4 시간 복잡도

스킵리스트의 연산 시간 복잡도는 다음과 같다.

• 탐색: 평균 O(log n), 최악 O(n)
• 삽입: 평균 O(log n)
• 삭제: 평균 O(log n)

이러한 성능은 각 노드가 상위 레벨에 포함될 확률이 일정하다는 가정 하에 성립한다.

5 장점과 단점

• 장점
  • 구현이 단순하며, 트리 기반 구조보다 직관적이다.
  • 동적 삽입과 삭제가 용이하다.
  • 병렬 처리 및 동시성 제어에 유리한 구조를 가질 수 있다.

• 단점
  • 최악의 경우 성능이 저하될 수 있다.
  • 많은 포인터를 사용하므로 메모리 사용량이 높다.

6 활용

스킵리스트는 다음과 같은 분야에서 활용된다.

• 메모리 내 데이터베이스 및 키-값 저장소 (예: Redis)
• 트랜잭션 시스템에서의 인덱싱
• 분산 시스템에서의 정렬된 데이터 저장

7 파이썬 구현

다음은 간단한 스킵리스트의 파이썬 구현 예시이다.

import random

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

class SkipList:
    MAX_LEVEL = 16
    P = 0.5

    def __init__(self):
        self.level = 0
        self.header = Node(None, self.MAX_LEVEL)

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

    def insert(self, key):
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.header

        for i in reversed(range(self.level + 1)):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]
        if current is None or current.key != key:
            lvl = self.random_level()
            if lvl > self.level:
                for i in range(self.level + 1, lvl + 1):
                    update[i] = self.header
                self.level = lvl
            new_node = Node(key, lvl)
            for i in range(lvl + 1):
                new_node.forward[i] = update[i].forward[i]
                update[i].forward[i] = new_node

    def search(self, key):
        current = self.header
        for i in reversed(range(self.level + 1)):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
        current = current.forward[0]
        if current and current.key == key:
            return True
        return False

8 같이 보기

• 이진 탐색 트리
• AVL 트리
• 레드-블랙 트리
• 연결 리스트
• 해시 테이블

9 참고 문헌

• William Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees", Communications of the ACM, 1990.
• Thomas H. Cormen et al., "Introduction to Algorithms", MIT Press.