IT용어위키

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

개요

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

구조

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

연산

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

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

시간 복잡도

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

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

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

장점과 단점

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

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

활용

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

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

파이썬 구현

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

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

같이 보기

참고 문헌

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.