[ Open Data Structures ] - Skiplists - 2

SkiplistList

이렇게 되면 Get/Set 함수도 함께 자명해집니다.

? 어렵습니다. Add 함수가 두 개라서 헷갈릴 수 있습니다. 그런데 둘은 Parameter가 다르다는 점을 알아야 합니다. 노드를 받는 Add를 하나씩 분석해보며 이해하도록 합시다. 각 노드의 변의 길이를 결정하는 부분이 조금 헷갈렸으나 천천히 짚어보니 이해가 됐습니다.

Node* u = sentinel; 은 기존 Skiplist처럼 좌상단의 노드부터 시작합니다. k는 추가하려는 노드의 높이를 나타냅니다. r = h는 Skiplist의 높이를 취합니다. 첫 번째 While문은 Skiplist의 높이를 조건으로 사용합니다. 두 번째 while 문에서 처음 j가 등장합니다.

기본적으로 j는 수직으로 이동할 때는 값이 변화하지 않습니다. 오직 수평으로 이동할 때만 값이 바뀌며 sentinel로부터 현재 검사 중인 노드 사이의 거리를 갖습니다. 이 두 번째 While문은 참이면 수평으로 이동하고 그렇지 않으면 추가하려는 위치 i보다 현재 검사 중인 노드의 길이(다음 노드까지의 거리)가 더 길다는 뜻이기 때문에 수평으로 이동하지 않고 노드의 변의 길이를 1 더 늘려줍니다. 그것이 u->length[r]++가 가지는 의미입니다. 이 while문을 탈출했다는 것은 현재 검사하는 노드가 추가하려는 위치 i 바로 직전이라는 점입니다.

해당 노드의 높이 r이 k보다 작거나 같으면 다음 노드로 가는 길에 반드시 노드 i가 있을 겁니다. 아래 그림을 보면 됩니다. 그것을 확인하는 것이 if( r <= k)입니다.

_w->next[r] = u->next[r]; 추가하려는 새로운 노드 w(위의 그림으로 위치는 4이고 데이터는 x)의 다음 노드는 기존의 위치 4의 노드입니다. 그것을 우리는 Find하는 것처럼 갖고 있었고 Find는 찾는 노드의 직전의 노드를 반환해주기 때문에 u(코드대로라면 3을 갖고 있습니다.)의 다음 노드를 호출하는 것이 맞습니다.

u->next[r] = _w; 그러면 원래 3의 위치에 있던 노드의 다음 노드는 이제 새로 추가된 _w입니다. 다음이 조금 헷갈리는 변의 길이를 정하는 코드입니다. 

_w->length[r] = u->length[r] - (_i - j);
u->length[r] = _i - j;

w의 변의 길이는  w에서 다음 노드까지의 거리를 말합니다. 기본적인 수학이니 수직선을 긋고 생각해봅니다. j는 여태껏 수평으로 이동한 거리(3)의 값을 갖고 있습니다. _i는 현재 추가한 w가 sentinel로부터 떨어진 거리(4)를 뜻합니다. 사실 조금 더 직관적으로 이해할 수 있는 방법이 있었습니다. 정의에 의하면 L0의 모든 변의 길이는 1이었습니다. 그러니 새로 추가한 노드와 다음 노드 사이는 당연히 1의 거리를 갖습니다.

Remove Operation

지금까지 배운 내용을 토대로 하면 Remove operation은 자명해야 합니다. 삭제할 노드가 있는 L0의 i번 째 노드까지 탐색경로를 따라가면서 한 레벨씩 아래로 내려갈 때마다 변의 길이를 감소시킵니다.