Skip List

🐣 들어가기 앞서

- 정렬된 리스트는 어떻게 그 순서를 유지하는지 설명하실 수 있나요?
- 그렇다면, 정렬된 리스트에서 특정 범위를 검색하는 과정을 설명하실 수 있나요?

만약, 설명이 힘들다면 이번 글을 읽으시면 도움이 될 겁니다.

이 글에서는 정렬된 리스트에서 빠른 검색을 위한 자료구조 Skip List를 소개합니다.

🌟 Skip List

아래와 같은 정렬된 Linked List가 있다고 가정해 봅시다.

위 리스트에서 '10'을 찾는다고 할 떄 걸리는 시간은 10입니다.
그럼 빠른 이동을 할 수 있는 고속도로(레벨)를 위에 만들어 봅시다.

이제 '10'을 찾을 때 걸리는 시간은 5입니다. 하지만 저장할 정보가 4만큼 늘었습니다. 추가적인 공간을 할당함으로써 빠른 검색을 제공할 수 있습니다.

이러한 개념을 활용하여, 동전 뒤집기(1/2)를 통해 레벨을 늘릴지 결정한다고 가정해 봅시다.

위와 같은 그림이 나오게 될 거고, 이는 Skip List라고 할 수 있습니다.

Skip List에서는 위 그림과 같은 과정으러 값을 찾게 됩니다. 이때 시간 복잡도는 평균적으로 O(log n)이며 공간복잡도는 무작위 Skip List에서 높이가 log n이 되고, 각 레벨에서의 노드 수가 평균적으로 상수배로 증가하기 때문에 전체 공간 복잡도는 O(n log n)이 됩니다.

🧵 Skip List 구현

이제 Skip List의 작동 방식을 살펴보았으니, 구현된 코드를 보며 전체적인 동작의 흐름을 살펴봅니다.

전체적인 코드는 여기서 확인할 수 있습니다.

🔗 Node class

class Node<K extends Comparable<K>, V> {  
    private int level;  
  
    private K key;  
    private V value;  
  
    private Node<K, V> left, right, up, down;  
  
    public Node(K key, V value, int level) {  
        this.key = key;  
        this.value = value;  
        this.level = level;  
    }
    
    /* Getter, Setter... */
}

우선 값을 저장할 Node를 작성합니다. Node에는 앞과 뒤 뿐만 아니라 위, 아래의 주소를 가지고 있어야 합니다.

🔎 Skip List에서의 조회

Skip List는 head애서 우측으로 탐색을 하며, 찾는 값이 우측 값보다 작으면 한단계 아래로 내려 갑니다.

private Node<K, V> findNode(K key) {  
	// head에서 탐색 시작
    Node<K, V> node = head;  
    Node<K, V> next;  
    Node<K, V> down;  
    K nodeKey;  

	// 레벨 별 탐색
    while (true) {  
        next = node.getNext();  

		// 다음 노드의 키 값이 주어진 키보다 클 때까지
        while(next != null && lessThanOrEqual(key, next.getKey())) {  
            node = next;  
            next = node.getNext();  
        }  
  
        nodeKey = node.getKey();  
        // 현재 노드의 키 값이 주어진 키와 동일한 경우 반복문을 종료
        if (nodeKey != null && equalTo(key, nodeKey)) {  
            break;  
        }  
  
        down = node.getDown();  
        // 아래 노드가 더 있는 경우 노드를 아래 노드로 업데이트
        if (down != null) {  
            node = down;  
        } else {  
            break;  
        }  
    }  
  
    return node;  
}

🌕 Skip List에서의 추가

1. findBy 메서드를 통해 가장 가까우며 작은 값을 찾아 삽입합니다.
2. 동전 뒤집기 결과에 따라 통해 레벨을 늘립니다.
   • 만약, 최대 레벨을 갱신하면 해더를 갱신해 줍니다.

public void add(K key, V value) {  
    Node<K, V> node = findNode(key);  
    if (node.getKey() != null && equalTo(key, node.getKey())) {  
        node.setValue(value);  
        return;  
    }  
  
    Node<K, V> prevNode = node;  
    int currentLevel = 1;  
    int headLevel = head.getLevel();  
    Node<K, V> newNode = new Node<>(key, value, currentLevel);
    insertAfter(newNode, prevNode);  
  
    while (canBuildNextLevel()) {  
	    // 최대 레벨을 넘긴 경우
        if (currentLevel >= head.getLevel()) {  
            Node<K, V> newHead = new Node<>(null, null, headLevel + 1);  
            linkVertical(newHead, head);  
            head = newHead;  
            headLevel = head.getLevel();  
        }  

		// 높인 레벨의 노드와 연결될 노드 탐색
        while (prevNode.getUp() == null) {  
            prevNode = prevNode.getPrevious();  
        }  
        prevNode = prevNode.getUp();  

		// 노드 연결
        Node<K, V> upperNode = new Node<>(key, value, prevNode.getLevel());  
        insertAfter(prevNode, upperNode);  
        linkVertical(upperNode, newNode);  
        newNode = upperNode;  
        currentLevel++;  
    }  
    size++;  
}

🗑️ Skip List에서의 삭제

1. findBy를 통해 주어진 키를 찾습니다.
2. 반환된 노드의 연결을 끊으며 아래 노드로 이동합니다.

public V remove(K key) {  
    Node<K, V> node = findNode(key);  
    if (!equalTo(key, node.getKey())) {  
        return null;  
    }  
  
    V deletedValue = node.getValue();  
    while (node != null) {  
        Node<K, V> downNode = node.getDown();  
        node.disconnect();  
        node = downNode;  
    }  
  
    return deletedValue;  
}

👻 3줄 요약

1. Linked List와 유사한 구조를 가지며, 각 노드는 여러 레벨을 가짐으로써 빠른 검색과 효율적인 범위 검색을 제공합니다.
2. 레벨을 확률적으로 할당하여, 각 노드가 다양한 레벨을 가지도록 합니다.
3. 모든 연산의 평균 시간 복잡도는 O(log n)입니다.

📘 참고 문헌

Algorithms Lab Youtube
Wikipedia