일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Z 알고리즘
- acmicpc.net
- Manacher's algorithm
- 그래프
- codeforces
- boj
- ICPC 연습
- Divide and conquer optimization
- DP
- convex hull
- 2794
- 8192
- 14179
- BAPC 2018
- Implementation
- Manacher 알고리즘
- 볼록 껍질
- 기하
- IOI 2013
- Z algorithm
- 세그먼트 트리
- 컨벡스 헐
- JOI
- 코드포스
- BAPC
- 백준 온라인 저지
- 기하 알고리즘
- 구현
- JOI 2018
- POI Solution
- Today
- Total
프로그래밍 연습장
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)$이 보장된다.
스킵 리스트의 노드는 다음과 같은 형태를 가진다.
1 2 3 4 5 6 7 | struct node { vector<node*> nxt; int val; node(int k, int v) : nxt(k, NULL), val(v) {} int lvl() { return nxt.size(); } }; | cs |
이 때, 노드의 다음 포인터의 개수(레벨)를 다음과 같이 무작위로 정할 것이다. 메모리를 절약하고 싶다면, 아래 randsz() 함수에서 높은 레벨이 나올 확률을 줄이면 된다(이를테면 $1 \over 2$에서 $1 \over 3$으로). 물론 그 만큼의 상수 배의 시간을 희생하게 될 것이다.
1 2 3 | int randsz() { for (int i=1; i<20; i++) if (rand()%2 or i==19) return i; } | cs |
노드의 $i$번째 포인터는 레벨이 $i$ 이상인 다음 노드(노드 뒤에 있는 레벨이 $i$ 이상인 노드들 중 가장 왼쪽에 있는 것)를 가리킨다. 어떤 원소를 찾는 연산은 포인터를 계속 따라감으로써 할 수 있다. 레벨이 높은 포인터가 낮은 포인터보다 더 멀리 이동할 수 있을 것이므로, 레벨이 높은 포인터를 이용할 수 있다면 그것을 이용하고, 아니면 레벨을 낮추는 과정을 반복하자.
1 2 3 4 5 6 7 8 9 | 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; } | cs |
위 코드로 설명이 될 것이다.
그럼 이제 추가 및 삭제 연산은 쉽다. 추가 및 삭제할 위치를 find 함수로 찾고, 그 위치에 원소가 들어가도록 조절해주면 된다. 이는 원래의 연결 리스트에서의 삽입을 여러 번 구현하는 것과 동일하다. 이를 위해서는 find 함수에서, 각 레벨에서 방문하게 된 마지막 원소가 무엇인지 기록하여야 한다.
1 2 3 4 5 6 7 8 9 10 11 12 | 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; } | cs |
이와 같은 간단한 변형으로 find 함수가 각 레벨에서 방문하는 마지막 원소를 기록할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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; } | cs |
이 때, 각 노드에 있는 포인터에 "이 포인터가 몇 개 뒤의 원소를 가리키는지"를 기록하는 것도 그리 어렵지 않다는 사실을 알 수 있다. 만약 이를 기록한다면, $k$번째 원소 찾기 연산도 어렵지 않게 할 수 있을 것이다. 그리 어렵지 않고, 구현된 풀 버전 코드를 첨부한다. 비슷한 역할을 할 수 있는 AVL, splay, RB 트리에 비해서 확실히 짧은 길이의 소스 코드를 볼 수 있다.
다만, 아직까지는 스킵 리스트를 응용해야만 할 수 있는 작업들이 눈에 띄지는 않는다. 짧고 간단한 kth element 구현체로서의 가치 딱 그 정도만 보이는 자료구조이다. 하지만 랜덤화를 통해서 시간 복잡도마저 개선할 수 있었다는 점은 주목할 수 있을 것 같다.
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 | 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; | cs |
'알고리즘' 카테고리의 다른 글
de Bruijn 수열 (2) | 2020.02.21 |
---|---|
Ray Casting Algorithm (5) | 2019.07.21 |
키타마사 법 (0) | 2018.03.25 |
Manacher의 알고리즘과 Z 알고리즘 (0) | 2018.02.27 |
그래프의 간선 리스트 표현 (2) | 2017.12.06 |