Deterministic Skip Lists (DSL)

There are several well-known solutions, the AVL tree, the B-tree and its special case the 2-3 tree, the red-black tree, etc., all of which are balanced search trees, but which are rarely used for main memory applications in (non research) computational practice. Evidently, they seem too hard or complicated to implement for the "root mean square programmer". Our general question then becomes "how hard is it to understand and implement such a data structure?" or "how many neurons must fire in the head of the programmer to slove the dictionary problem in logarithmeic time?" Intriguing as a lower bound for the latter form may be, we restrict ourselves to what we feel is a new upper bound.

위 내용이 논문에 소개된 글이다. 정말 재미있는 소개글이지 싶다. 우리가 흔히 들어왔던 로그 함수를 그리는 데이터 구조를 이해하고 구현하는 것이 얼마나 어려운가?, 로그적인 시간 내에 사전적인 문제를 풀기 위해 프로그래머의 머리 속에서 얼마나 많은 뉴런들이 타버려야 하는가?
나는 위 소개글을 읽고 한바탕 웃고 말았다. 그런 반면 Skip List에 대한 기대감에 차게 만들었다.

특징 몇 가지를 살펴보자.
1. 똑같은 입력 값이라고 하더라도, 입력 순서에 따라 트리의 모양은 달라진다.
2. 실 구현은 배열과 Linked List로 구현 가능하다.
3. 구현하기가 일반 다른 알고리즘보다 훨씬 간단하다.
4. Top-Down 방식으로 삽입, 검색, 삭제가 이루어진다.
5. 최악의 검색 비용 log(n)을 가지는 몇몇 deterministic version(1-2 Skip List, 1-2-3 Skip List)을 표현한다.

1-2 Skip List에서 최대 개수의 포인터는 절대 2n을 초과하지 않는다. (배열 구현시)
배열 구현시 삽입과 삭제시 비용이 높아진다. 삽입시 비용이 높아지는 것은 다른 알고리즘과 비슷하여 큰 문제가 되지 않으나, 삭제시 그 만큼의 비용이 발생한다는 것은 문제이다. (삭제 연산이 많이 발생하지 않는다면 상관없다.) 따라서 이 문제를 해결하기 위해서 우리는 배열 구현을 Linked List로 구현을 하면 된다. 그러나, 배열 구현보다 3배의 요구 공간(6n)이 요구된다. Linked List로 구현한다는 것은 노드를 올리거나 내리기 위해 단지 몇몇 포인터만 변경만 하면 되기 때문이다.

1-2 Skip List는 높이 h-1에 1 또는 2 노드가 존재하고 있다.  1-2 Skip List와 2-3 tree간의 비교는 쉽게 일반화되어진다. 또한 1-2-3 Skip List는 높이 h-1에 최소 1개 최대 3개의 노드가 존재한다. 이 또한 2-3-4 트리와의 비교가 쉽게 된다. 삽입, 검색, 삭제 알고리즘은 하단에 Pseudo Code가 있으니 별도의 설명은 생략을 하며, 필요하신 분들은 논문을 직접 읽어보면 될 듯하다.
 

아래의 Pseudo Code는 Linked List를 기반으로 한 Pseudo Code이며 배열 코드는 인터넷에 검색을 해보면 코드들이 많이 있다.

1. Search Pseudo Code

node * Search(v)
int v;
{

node *x;

x = head;
bottom->key = v;
while (x != bottom) {

while( v > x->key)  x = x->r;
if( x->d == bottom)

return ( (v == x->key) ? x : bottom);

x = x->d;

}

}

논문에 나와 있는 내용이다. 검색 모듈이 2개가 있는데, 1번째는 거의 Binary Search Tree와 같다. 위 모듈은 bottom이 아닌 말단 노드까지 진행을 해야 한다.

2. Insert Pseudo Code

int Insert(v)
int v;
{

node *t, *x;

x = head;
bottom->key = v;
while( x != bottom) {

while( v > x->key) x = x->r;
if( (x->d == bottom) && (v == x->key))

return 0;

if( (x->d == bottom) || (x->key == x->d->r->r->r->key)) {

t = (node *) malloc(sizeof(struct node));
t->r = x->r;
t->d = x->d->r->r;
x->r = t;
t->key = x->key;
x->key = x->d->r->key;

}

                        x = x->d;

}

if( head->r != tail) {

t = (node *) malloc(sizeof(struct node));
t->d = head;
t->r = tail;
t->key = maxkey;
head = t;

}

}

위 모듈을 한 번 그려보면, 거의 포인터만 옮기는 수준이다. 다른 알고리즘에 비하면 정말 간단하다. 이 모듈 또한 논문에서 제공이 된다.

3. Delete Pseudo Code

int Delete(v)
int v;
{

node *t, *x, *p;
char *tmpKey;

x = head->d;
bottom->key = v;

while(x != bottom) {

while( v > x->key) { p = x; x = x->r; }
if( (x->d == bottom) {

if( v == x->key) {

if( p == x) { x = x->r; p->key = x->key; }

p->r = x->r;

free(x);

}

if( head->d->key == max) {

t = head->d;
head->d = head->d->d;
free(t);

}
return 1;

}

 

if( x == x->key) { p = x; x = x->r; }

if( x->r == tail && p->d->r->key != p->key) {

p->key = p->d->r->key;
x->d = p->d->r->r;

}

if( p != x) {

if( x->d->r->key == x->key) {

if( p->d->r->r->r->r != x->d) { // merge

p->key = x->key;
t = x;
p->r = x->r;
free(t);
x = p;

}
else { // borrow

p->key = p->d->r->r->key;
x->d = p->d->r->r->r;

}

}
else {

if( v> x->d->key) {

tmpKey = x->d->key;
x->d = x->d->r;
p->key = tmpKey;
x = p;

}

}

}
else {

if( x->d->d == bottom && x->d->r->key == x->key)

x = x->r;

}
p = x = x->d;

}

return 0;

}

위 삭제 알고리즘은 내가 직접 구현한 내용이다. 약간 모자라는 부분이 있지만, 삭제하면서도 1-2-3 Skip List를 유지해야 하므로, 삽입 알고리즘보다 약간은 길다. 약간 어설프긴 하지만 돌아가는데에는 무리가 없다. 시간 나는대로 손을 봐서 좀 더 완벽한 모듈을 구현해야 하는 숙제가 남아 있다.

아무튼, 위 논문대로 복잡도라든지 코드 구현 내용이라든지 전혀 다른 알고리즘에 비해 뒤질 것이 없어 보인다. 역시 사람은 공부해야 하는가보다. 공부를 안 하면 이런 좋은 알고리즘이 있는지 없는지 조차 모르니 말이다.

** 관련 글 **
http://research.cs.queensu.ca/home/daver/235/C2102557243/E20070330101410/Media/SkipList.pdf
http://www.cs.ucr.edu/cs141/cs141_04sum/
http://en.literateprograms.org/Skip_list_(C_Plus_Plus)
http://www.cosc.canterbury.ac.nz/research/RG/alg/dict.html
http://www.ddj.com/184404217
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf