스킵 리스트 (skip list) 동작 방법

skip list는 linked list와 비슷하게 다음 원소를 가리키는 포인터를 가지고 있다.

그렇기 때문에 데이터의 삽입/삭제를 빠르게 할 수 있다. 이것은 linked list 특성상 당연해 보이는데 skip list는 여기에 검색 속도까지 책임진다.  

 

linked list부터 시작해서 어떤 방법으로 검색 속도를 향상시키는지, 부작용은 없는지 확인해보자.

 

• 시간 복잡도 $O(n)$
• 공간 복잡도 $O(n)$

linked list를 먼저 그려보면 위와 같다. 삽입/삭제는 앞, 뒤 노드만 수정하면 되기 때문에 빠르게 할 수 있지만 역시 검색이 문제다. 다음 원소를 가리키는 포인터만 따라가서는 당연히 속도가 좋지 않기 때문인데, 포인터를 여러 개 두는 방향으로 이를 개선한다.

 

그러면 다음 원소뿐만 아니라 그다음 원소도 가리키도록 포인터를 하나 더 추가해보자.

• 메모리를 더 추가(n/2)해서 속도를 더 향상(n/2) 시켰다.

메모리를 더 추가해서 속도를 향상시켰다. 그러면 더 메모리를 추가해보자.

 

• 메모리를 더 추가(n/4)해서 속도를 더 향상 시켰다.

지금은 $2^0$, $2^1$, $2^2$칸 앞을 가리키는 포인터를 추가했지만, 극단적으로 $2^i$ 앞을 가리키는 포인터를 추가하면 검색하는 속도는 $O(logn)$까지도 줄일 수 있다. 아주 좋아 보이지만 list에 삽입과 삭제가 생긴다면 이 구조를 유지하기가 어려워진다.

 

예를 들어 가운데 5가 삭제된다고 했을 때 이와 같은 구조를 유지하려면 매우 여러 원소를 수정해야 할 것이다.

 

skip list

이 문제를 skip list는 확률에 근거해서 포인터를 관리하며 푼다.

항상 최선의 모양을 유지하지는 않고 포인터 개수를 확률적으로 유지한다.

• $\frac{1}{2^1}$ 확률로 포인터 1개를 가짐
• $\frac{1}{2^2}$ 확률로 포인터 2개를 가짐
• $\frac{1}{2^i}$ 확률로 포인터 i개를 가짐

이렇게 확률로 포인터 개수를 잡으면 임의의 원소를 봤을 때 앞뒤 상관없이 독립적으로 자신의 포인터 개수를 가질 수 있다. 즉, 임의의 원소가 삽입/삭제되었을 때 해당 원소만 신경 쓰면 된다는 뜻이다.

 

원소를 생성할 때 랜덤 포인터 개수를 구하는 코드를 보면 다음과 같다.

int getRandomHeight() {
  int height = 1;
  while(height < MAX_HEIGHT && rand(0, 1) < p)
    height++;

  return height;
}

 

 

---

 

예제

랜덤 하게 구조를 가진 skip list에 대해서 삽입과 삭제를 직접 해보자.

1. Delete 7

삭제를 하기 위해 먼저 빨간색 선을 따라가며 7을 빠르게 찾는다.
7을 삭제하기 전에 파란색 원소가 가리키던 7을 향한 포인터를 수정해 주어야 한다. 각각에 대해 7이 가리키던 9와 8을 가리키도록 수정한다. 그 후에 7을 삭제하면 깔끔하게 7의 전과 후를 연결시키면서 지울 수 있다.

 

지울 원소를 찾아가면서(빨간색) 수정해야 할 원소(파란색)를 저장하며 코딩하면 된다.

bool find(int key, vector<node*>& path) {
  node *cur = head;
  for (int i = MAX_HEIGHT - 1; i >= 0; i--) {
    while (cur->next[i]->value < key) 
      cur = cur->next[i];
    path[i] = cur;
  }

  return cur->next[0]->val == key
}

 

2. Insert 7

이제 7을 삽입하는 과정을 살펴보자.

위 그림과 마찬가지로 삽입할 위치를 찾아간 후 getRandomHeight() 를 통해 랜덤 포인터 개수를 얻는다.

 

그리고 삭제할 때와는 반대로 생성한 포인터에 파란색 원소들이 가리키는 포인터를 대입하고, 파란색 원소는 새로 생성한 원소를 가리키도록 수정한다. 그러면 생성 전과 마찬가지로 생성한 랜덤 포인터 개수의 앞뒤를 매끄럽게 연결할 수 있다.

 

---

 

용도

길게 설명했지만 결국 하는 일은 정렬을 유지하며 삽입과 삭제를 빠르게 하는 것이다.

같은 역할로 떠오르는 게 database의 b/b+ tree, red-black tree, AVL tree, splay tree 등이 있다. 이들은 각각의 자료구조에 맞는 정책과 리벨런싱을 통해 빠른 속도를 보장한다. skip list와 비슷하게 확률에 근거한 treap 자료구조도 있는데 그럼 과연 skip list의 장점은 무엇일까?

 

내가 생각하는 장점은 아래 두 가지가 있다.

 

첫 번째로 getRandomHeight() 에서 포인터 개수를 생성할 때 사용되는 p 변수가 될 것 같다. p가 0이라면 linked list가 될 것이고, p가 1에 가깝다면 메모리를 검색 속도에 쏟아붓는 구조가 될 것이다. 이 p를 적절히 조절하여 메모리와 시간의 타협점을 쉽게 조절할 수 있다.

 

두 번째로는 tree를 사용했을 때의 단점을 이해하면 보인다.

위에 언급한 tree들은 자기만의 알고리즘으로 특정 조건이 발생하면 리벨런싱을 통해 트리를 재구성한다. 이때 lock이 발생하고, 특정 경우에는 연속적인 리벨런싱도 충분히 발생할 수 있다. 멀티스레드에서 트리를 참조한다면 그 피해는 짐작하기 어려워진다. skip list도 삽입/삭제 시 lock이 필요하지만, tree에서 발생하는 연속적인 리벨런싱은 발생하지 않는다.