Skip List

Skip List는 정렬된 연결 리스트를 기반으로 하여 빠른 검색, 삽입, 삭제 연산을 지원하는 확률적 데이터 구조이다.

Skip List는 여러 레벨의 연결 리스트로 구성된 데이터 구조로, 각 레벨은 그 아래 레벨의 일부 요소를 포함하며, 최하위 레벨은 모든 요소를 포함한다.

A schematic picture of the skip list data structure
https://en.wikipedia.org/wiki/Skip_list#/media/File:Skip_list.svg

특징

  1. 다중 레벨 구조: 여러 층의 연결 리스트로 구성된다.
  2. 확률적 균형: 랜덤화를 통해 구조의 균형을 유지한다.
  3. 정렬 상태 유지: 요소들은 정렬된 순서로 유지된다.

장점

  1. 빠른 검색: 평균 O(log n) 시간 복잡도로 검색이 가능하다.
  2. 효율적인 삽입/삭제: 평균 O(log n) 시간에 삽입과 삭제가 가능하다.
  3. 구현의 단순성: 균형 이진 탐색 트리에 비해 구현이 간단하다.

단점

  1. 추가 메모리 사용: 여러 레벨의 포인터로 인해 추가 메모리가 필요하다.
  2. 확률적 성능: 최악의 경우 O(n) 시간 복잡도가 발생할 수 있다.

응용

  1. 데이터베이스 인덱싱: RocksDB와 같은 키-값 저장소에서 사용된다.
  2. 메모리 관리: 비휘발성 메모리 최적화에 활용된다.
  3. 캐시 구현: 효율적인 캐시 시스템 구축에 사용된다.

동작 원리

  1. 검색: 최상위 레벨에서 시작하여 목표 값보다 작은 노드를 따라 이동하고, 큰 값을 만나면 아래 레벨로 내려간다.
  2. 삽입: 랜덤하게 레벨을 결정하고, 해당 레벨까지 노드를 생성하여 연결한다.
  3. 삭제: 노드를 찾아 모든 레벨에서 제거한다.

구성 요소

  1. 노드: 키, 값, 여러 레벨의 다음 노드 포인터를 포함한다.
  2. 헤드 노드: 모든 레벨의 시작점 역할을 한다.
  3. 레벨: 여러 층의 연결 리스트 구조를 형성한다.

구현 방식

JavaScript를 사용한 Skip List 구현 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

class Node {
    constructor(key, value, level) {
        this.key = key;
        this.value = value;
        this.forward = new Array(level + 1).fill(null);
    }
}

class SkipList {
    constructor(maxLevel, p) {
        this.maxLevel = maxLevel;
        this.p = p;
        this.header = new Node(null, null, maxLevel);
        this.level = 0;
    }

    randomLevel() {
        let lvl = 0;
        while (Math.random() < this.p && lvl < this.maxLevel) {
            lvl++;
        }
        return lvl;
    }

    insert(key, value) {
        let update = new Array(this.maxLevel + 1).fill(null);
        let current = this.header;

        for (let i = this.level; i >= 0; i--) {
            while (current.forward[i] !== null && current.forward[i].key < key) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        let newLevel = this.randomLevel();
        if (newLevel > this.level) {
            for (let i = this.level + 1; i <= newLevel; i++) {
                update[i] = this.header;
            }
            this.level = newLevel;
        }

        let newNode = new Node(key, value, newLevel);
        for (let i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    search(key) {
        let current = this.header;
        for (let i = this.level; i >= 0; i--) {
            while (current.forward[i] !== null && current.forward[i].key < key) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        if (current !== null && current.key === key) {
            return current.value;
        }
        return null;
    }
}

// 사용 예
let skipList = new SkipList(4, 0.5);
skipList.insert(3, "value3");
skipList.insert(6, "value6");
skipList.insert(7, "value7");
console.log(skipList.search(6)); // 출력: value6

Python을 활용한 Skip List 구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

import random

class Node:
    """스킵 리스트의 노드 정의"""
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)  # 레벨별 포인터 배열

class SkipList:
    """스킵 리스트 구현"""
    def __init__(self, max_level=4, p=0.5):
        self.max_level = max_level
        self.p = p  # 레벨을 결정하는 확률
        self.head = Node(-1, 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

    def insert(self, value):
        """스킵 리스트에 값 삽입"""
        update = [None] * (self.max_level + 1)
        current = self.head

        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current

        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl

        new_node = Node(value, lvl)
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def search(self, value):
        """값 검색 (O(log N))"""
        current = self.head
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
        current = current.forward[0]
        return current and current.value == value

# 사용 예제
skiplist = SkipList()
skiplist.insert(10)
skiplist.insert(20)
skiplist.insert(30)

print("20 찾기:", skiplist.search(20))  # True
print("15 찾기:", skiplist.search(15))  # False

def test_skip_list():
    sl = SkipList()
    sl.insert(5)
    sl.insert(15)
    sl.insert(25)

    assert sl.search(5) == True
    assert sl.search(15) == True
    assert sl.search(25) == True
    assert sl.search(10) == False  # 존재하지 않는 값

    print("스킵 리스트 테스트 통과!")

test_skip_list()

참고 및 출처