한양과기고 에듀테크 수업도구 대시보드

스킵 리스트 (Skip List)

정렬된 연결 리스트는 순서 유지는 쉽지만 탐색이 O(n)이다. 스킵 리스트는 그 위에 급행 노선(express lane)을 여러 층 쌓아 멀리 건너뛰며(skip) 탐색해, 균형 트리 없이도 평균 O(log n)의 탐색·삽입·삭제를 얻는다. 각 노드의 높이는 동전 던지기(확률 p=0.5)로 무작위 결정되므로 회전이나 재조정 코드가 전혀 없다. Redis의 Sorted Set이 내부적으로 쓰는 자료구조다.

인터랙티브 데모

노드 수 n

현재 최대 층수

–

마지막 탐색 비교 횟수

–

이론값 ⌈log₂ n⌉

주황색 경로 = 탐색이 실제로 따라간 링크. 위층에서 크게 건너뛰고, 목표를 지나치면 한 층 내려간다.

왜 동전 던지기인가

노드를 삽입할 때 층을 하나씩 올린다: 동전이 앞면(50%)이면 한 층 더 쌓고, 뒷면이면 멈춘다. 그 결과 약 1/2의 노드가 2층 이상, 1/4이 3층 이상, 1/2ᵏ이 (k+1)층 이상이 된다. 각 층의 노드 수가 절반씩 줄어드니 층수는 평균 log₂ n, 한 층에서 건너뛰는 거리도 평균 2칸 → 전체 탐색이 O(log n).

지금 스킵 리스트의 층별 노드 분포

균형 트리(AVL·레드블랙)는 삽입마다 회전으로 균형을 강제하지만, 스킵 리스트는 확률에 맡겨 기대값으로 균형을 이룬다. 구현이 짧고 동시성(락 분할)에 유리한 이유다.

탐색 의사코드

# target 이상인 첫 노드를 찾는다
def search(target):
    node = head
    for level in range(top_level, -1, -1):   # 맨 위 급행 노선부터
        while node.next[level] and node.next[level].key < target:
            node = node.next[level]              # 목표보다 작으면 계속 건너뛴다
        # 지나치기 직전에서 한 층 내려간다
    node = node.next[0]                        # 맨 아래층에서 한 칸
    return node if node and node.key == target else None

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

다른 정렬 구조와 비교

구조	탐색	삽입/삭제	특징
정렬된 배열	`O(log n)`	`O(n)`	이진 탐색은 빠르나 삽입 시 원소 밀기
정렬된 연결 리스트	`O(n)`	`O(1)`*	위치만 알면 삽입은 빠르지만 그 위치 찾기가 느림
이진 탐색 트리(균형 X)	`O(n)` 최악	`O(n)` 최악	정렬 입력이면 한쪽으로 치우침
AVL / 레드블랙 트리	`O(log n)`	`O(log n)`	보장은 확실, 회전 로직 복잡
스킵 리스트	`O(log n)` 기대	`O(log n)` 기대	구현 간단, 범위 질의·동시성에 유리, 최악은 `O(n)`(확률 극히 낮음)

핵심 정리

급행 노선

위층일수록 노드가 성기게 배치돼 멀리 건너뛴다. 아래로 내려갈수록 촘촘해져 정밀 탐색.

확률적 균형

회전 없이 동전 던지기만으로 기대값상 균형. 코드가 트리보다 훨씬 짧다.

범위 질의

맨 아래층이 완전한 정렬 리스트라 x~y 사이 원소 나열이 자연스럽다(Redis ZRANGEBYSCORE).

최악의 경우

동전이 계속 뒷면이면 O(n). 하지만 확률이 1/2ⁿ 수준이라 실무에서 무시 가능.