#2 알고리즘 Advanced Data Structure : Skip List

Data structure 자체가 알고리즘을 구현하는 방법이 될 수 있습니다. 

Skip List

  정렬된 linked list에 대해 적용하는 알고리즘으로 빠른 검색및 삽입 삭제를 가능하게 해주는 자료구조입니다. Skip List는 key와 element쌍으로 되어있는 리스트가 여러 레이어에 걸쳐 있는 형태입니다. 각 레이어는 플러스 무한대와 마이너스 무한대를 항상 키 값으로 가지고있고 가장 하위 레이어인 S0는 오름차순으로 정렬되어 있습니다. 그리고 하위레이어는 상위 레이어를 포함하는 형태입니다. 그림으로 살펴보면 아래 그림과 같습니다. 

Skip List에서의 Search

  Skip List에서의 Search는 최상단 list의 첫번째 위치에서부터 시작합니다. 만약 현재 위치의 다음 element가 찾으려는 값보다 크다면 아래로 내려가고 이를 모든 레이어에 걸쳐 반복하는 식입니다. binary search tree에서 원하는 값을 찾는 과정과 비슷합니다. 

Skip list는 Randomized algorithm입니다. 

  Randomized algorithm이른 랜덤성을 기초로 알고리즘을 구현 하는것을 말합니다. 다들 잘 아는 quick sort의 경우에도 pivot을 랜덤으로 결정하는 Randomized algorithm의 일종입니다. Skip list의 랜덤성은 동전을 던졌을때 앞면이 나올 확률입니다.  이는 Skip list를 만드는 과정, 바로 insertion에서 설명하도록 하겠습니다. 

Skip List에서의 Insertion

  동전을 던졌을때 2번 연속 head가 나오면 i = 2입니다. 만약 i가 현재 Skip list의 높이 h보다 크다면 i+1만큼의 높이만큼 리스트를 위쪽에 추가합니다. 만약 i가 5라면 높이 6까지 리스트가 만들어졌을것이고 key값을 많이 가지지 못한 리스트가 위에 많이 생성되어 있을 것입니다. 말로는 이해하기가 힘듭니다. 아래 그림을 보면서 다시 이해해보도록 하겠습니다. 

  insert key값이 15이고 동전을 던졌을때 윗면이 나온 횟수가 2인 경우입니다. 

  1. i가 2이므로 높이 3까지 리스트가 만들어졌고 시작은 S2부터 하게 됩니다. S2에서 시작했을 때 현재 리스트에        15가 없습니다. 그렇다면 15를 추가해준 후 아래 레이어로 내려갑니다.                                                 

  2. 아래 레이어로 내려가 S1에서 순차적으로 탐색을 하면서 15보다 큰값이 나타나면 멈추어 15를 삽입합니다. 

  3. S0에서 자신보다 작은 값은 건너뛰고 큰값이 나오면 멈춰서 15를 삽입하게 됩니다. 그리고 양옆으로만 연결          하는것이 아니라 입력된 수 15들 끼리도 서로 연결해줍니다. 

Skip List에서의 Deletion 

  

  insert에서 같은 키값끼리 모두 연결 해 놓았기 때문에 가장 상위 레이어에서 키값을 찾기만 한다면 한번에 모두 삭제 할 수 있습니다. 아주 간단합니다. 여기서 중요한것은 빈 리스트는 1개만 남기고 모두 삭제한다는 것입니다. 이렇게 함으로써 만약 insert시에 동전의 윗면이 아주 적은 확률로 많이 나와서 쓸데없이 높은 리스트가 생성되었다고 해도 모두 정리가 되게 됩니다. 아래 예제는 34를 찾아서 삭제하는 예시입니다. 

Skip List의 시간복잡도와 공간복잡도

  

  한 레이어의 첫번째 item에서 전진하다가 내가 원하는 키를 만날 확률은 1/2입니다. 동전을 던졌을때 만약 윗면이 나왔다면 그 층에 레이어가 생성되고 키가 삽입되었을 것이기 때문입니다. 그리고, 몇번을 전진해야 원하는 키를 만날 수 있는 지는 동전을 던진 횟수와 상관있습니다. 동전을 던졌을때 수없이 던지게 된다면 앞면과 뒷면이 동일한 수만큼 나오게 됩니다. 따라서 앞면이 나오게되는 최소의 던지는 개수는 확률적으로 두번이라고 할 수 있습니다. 그리고 트리의 높이는 logn입니다. 따라서 1/2 * 2 * log n이므로 O(log n)의 시간복잡도를 얻을 수 있습니다. 이는 worst case분석이 아닙니다. Skip List의 경우 worst case분석을 하게되면 무한히 동전이 앞면이 나오는 경우를 가정해야 하는데 이로는 알고리즘의 실제적인 성능을 분석 할 수 없기 때문입니다. 

 공간복잡도는 트리의 높이와 상관있습니다. 아까 트리의 높이가 log n이라고 하였는데, 아주 자세하게 증명하는 식은 저도 확실히 이해할 수 없어서 어느정도 approximation해서 이해하는 부분만 보고 넘어갔습니다. n개의 key값에 대해서 여러 레이어중 하나인 Si가 한개의 key값을 저장하고 있을 확률은 n/(2^i)입니다.(i는 윗면이 나온 횟수입니다.) 동전을 던져서 앞면이 계속 나올 횟수로 key값의 개수를 나눈 것입니다. 확률이 가장 높은것을 고르면 평균적으로 Skip List가 유지하고 있는 높이를 알 수 있게 됩니다. 확률이 1이되는 i의 값은 log n이기 때문에 높이는 거의 항상 log n으로 유지되고 레이어가 올라갈때마다 확률적으로 1/2씩 key의 개수가 작아지므로 공간복잡도는 O(n)입니다. 

Skip List의 구현 방법

  Skip List는 quad node형태로 구현합니다. 한 레이어 내에서의 링크드 리스트 뿐만 아니라 위아래로도 모두 링크를 가지고 있어야 삭제와 검색, 업데이트를 빨리 할 수 있기 때문입니다. 

마무리

  아마 앞으로 몇개의 알고리즘에 대해서는 확률적으로 분석하는 방법을 사용하게 될 것입니다. 언뜻 이해가 되지 않죠, 그리고 linked list나 key값과 element를 사용하는 dictionary같은 자료구조를 잘 모르시는 분들은 그부분을 조금 학습하고 오셔야 이 부분을 이해 할 수 있을 것입니다. 다음에는 binary heap과 binomial heap을 한번에 할 수있도록 준비해 보겠습니다.