Skip List

스킵 리스트(Skip List)는 균형잡힌 이진 탐색 트리를 일부 대체할 수 있는 자료구조이다. 원소의 탐색, 추가, 삭제를 평균 $O(\log n)$ ($n$은 원소의 개수)의 시간에 할 수 있으며, 또한 약간의 기능만 추가함으로써 $k$번째 원소($k$th element) 연산 또한 $O(\log n)$의 시간에 수행할 수 있다.

스킵 리스트는 연결 리스트에 약간의 변형을 가해서 만들어졌다. 만약 연결 리스트에 원소들을 정렬된 순서로 저장하고 있다고 하자. 이 때 원소를 삽입하기 위해서는 (1) 이 원소가 들어갈 위치를 찾은 뒤($O(n)$) (2) 이 위치에 원소를 넣으면($O(1)$) 된다. 삭제도 마찬가지 원리로 작동하므로, 어떤 원소를 찾는 시간만 줄인다면 탐색, 추가, 삭제 모든 연산의 시간 복잡도를 줄일 수 있다는 이야기가 된다.

어떻게 하면 원소를 찾는 시간을 줄일 수 있을까? 만약, 리스트의 각 원소에 대해서 그 다음 원소를 가리키는 포인터 뿐만 아니라 $2$개 뒤의 원소를 가리키는 포인터를 가지고 있으면 어떨까? 그러면 탐색 시간을 $1 \over 2$로 줄일 수 있을 것이다. 그렇다면, $2^2$개 뒤의 원소를 가리키는 포인터도 가진다면? 다시 $1 \over 2$로 시간이 줄어든다. $2^3$은? $2^4$는? 이렇게 계속해서 포인터를 $\log n$개 만들어두면, 탐색을 $O(\log n)$ 시간에 할 수 있을 것이다!

하지만, 정확히 $2^k$개! 하고 개수를 정해두고 리스트를 관리하면 삽입과 삭제 과정에서 리스트의 구조가 망가지게 될 수도 있다. 이 때 가장 좋은 방법은 랜덤화를 하는 것이다. 각 노드는 $1 \over 2$의 확률로 $1$개의 포인터를, $1 \over {2^2}$의 확률로 $2$개의 포인터를, $\cdots$, $1 \over {2^k}$의 확률로 $k$개의 포인터를 가지는 것이다. ($20$개 정도로 상한선을 정해두는 게 좋다.) 노드의 $i$번째 포인터는, 이 노드 다음에 나오는 레벨이 $i$ 이상인 첫 노드를 가리키게 될 것이다. 이 방법으로는 어떤 순서로 삽입과 삭제가 일어난다고 하더라도 평균 $O(\log n)$이 보장된다.

스킵 리스트의 노드는 다음과 같은 형태를 가진다.

struct node {
    vector<node*> nxt;
    int val;
    node(int k, int v) : nxt(k, NULL), val(v) {}
    int lvl() { return nxt.size(); }
};
 

이 때, 노드의 다음 포인터의 개수(레벨)를 다음과 같이 무작위로 정할 것이다. 메모리를 절약하고 싶다면, 아래 randsz() 함수에서 높은 레벨이 나올 확률을 줄이면 된다(이를테면 $1 \over 2$에서 $1 \over 3$으로). 물론 그 만큼의 상수 배의 시간을 희생하게 될 것이다.

int randsz() {
    for (int i=1; i<20; i++) if (rand()%2 or i==19) return i;
}

노드의 $i$번째 포인터는 레벨이 $i$ 이상인 다음 노드(노드 뒤에 있는 레벨이 $i$ 이상인 노드들 중 가장 왼쪽에 있는 것)를 가리킨다. 어떤 원소를 찾는 연산은 포인터를 계속 따라감으로써 할 수 있다. 레벨이 높은 포인터가 낮은 포인터보다 더 멀리 이동할 수 있을 것이므로, 레벨이 높은 포인터를 이용할 수 있다면 그것을 이용하고, 아니면 레벨을 낮추는 과정을 반복하자.

bool find(int key) {
    node *now = head;
    for (int i=19; ~i; i--) {
        while (now->nxt[i]->val < key) now = now->nxt[i];
    }
    now = now->nxt[0];
    if (now->val == key) return true;
    return false;
}

위 코드로 설명이 될 것이다.

그럼 이제 추가 및 삭제 연산은 쉽다. 추가 및 삭제할 위치를 find 함수로 찾고, 그 위치에 원소가 들어가도록 조절해주면 된다. 이는 원래의 연결 리스트에서의 삽입을 여러 번 구현하는 것과 동일하다. 이를 위해서는 find 함수에서, 각 레벨에서 방문하게 된 마지막 원소가 무엇인지 기록하여야 한다.

vector<node*> vis;
bool find(int key) {
    node *now = head;
    for (int i=19; ~i; i--) {
        while (now->nxt[i]->val < key) now = now->nxt[i];
        vis[i] = now;
    }
    now = now->nxt[0];
    if (now->val == key) return true;
    return false;
}
 

이와 같은 간단한 변형으로 find 함수가 각 레벨에서 방문하는 마지막 원소를 기록할 수 있다.

void add(int val) {
    if (find(val)) return;
 
    node* obj = new node(randsz(), val);
    for (int i=0; i<obj->lvl(); i++) {
        obj->nxt[i] = vis[i]->nxt[i];
        vis[i]->nxt[i] = obj;
    }
}
void erase(int val) {
    if (!find(val)) return;
 
    node* obj = vis[0]->nxt[0];
    for (int i=0; i<obj->lvl(); i++) {
        vis[i]->nxt[i] = obj->nxt[i];
    }
    delete obj;
}
 

이 때, 각 노드에 있는 포인터에 "이 포인터가 몇 개 뒤의 원소를 가리키는지"를 기록하는 것도 그리 어렵지 않다는 사실을 알 수 있다. 만약 이를 기록한다면, $k$번째 원소 찾기 연산도 어렵지 않게 할 수 있을 것이다. 그리 어렵지 않고, 구현된 풀 버전 코드를 첨부한다. 비슷한 역할을 할 수 있는 AVL, splay, RB 트리에 비해서 확실히 짧은 길이의 소스 코드를 볼 수 있다.

다만, 아직까지는 스킵 리스트를 응용해야만 할 수 있는 작업들이 눈에 띄지는 않는다. 짧고 간단한 kth element 구현체로서의 가치 딱 그 정도만 보이는 자료구조이다. 하지만 랜덤화를 통해서 시간 복잡도마저 개선할 수 있었다는 점은 주목할 수 있을 것 같다.

struct node {
    vector<node*> nxt;
    vector<int> ind;
    int val;
    node(int k, int v) : nxt(k, NULL), ind(k, 1), val(v) {}
    int lvl() { return nxt.size(); }
};
 
struct skiplist {
    node *head, *tail;
    vector<node*> vis;
    vector<int> ind;
    skiplist() : vis(20, NULL), ind(20, 0) {
        head = new node(20, -inf);
        tail = new node(20, inf);
        for (int i=0; i<20; i++) head->nxt[i] = tail, tail->ind[i] = inf;
    }
    int randsz() {
        for (int i=1; i<20; i++) if (rand()%3 or i==19) return i;
    }
    bool find(int key) {
        node *now = head;
        for (int i=19; ~i; i--) {
            ind[i] = 0;
            while (now->nxt[i]->val < key) ind[i] += now->ind[i], now = now->nxt[i];
            vis[i] = now;
        }
        now = now->nxt[0];
        if (now->val == key) return true;
        return false;
    }
    int kth(int ord) {
        node *now = head;
        for (int i=19; ~i; i--) while (now->ind[i] <= ord) ord -= now->ind[i], now = now->nxt[i];
        return now->val;
    }
    void add(int val) {
        if (find(val)) return;
 
        node* obj = new node(randsz(), val);
        for (int i=0, sum=1; i<obj->lvl(); i++) {
            obj->nxt[i] = vis[i]->nxt[i];
            obj->ind[i] -= sum - 1;
            vis[i]->nxt[i] = obj;
            vis[i]->ind[i] = sum;
            sum += ind[i];
        }
        for (int i=obj->lvl(); i<20; i++) vis[i]->ind[i]++;
    }
    void erase(int val) {
        if (!find(val)) return;
 
        node* obj = vis[0]->nxt[0];
        for (int i=0; i<obj->lvl(); i++) {
            vis[i]->nxt[i] = obj->nxt[i];
            vis[i]->ind[i] += obj->ind[i];
        }
        delete obj;
    }
} t;