1. 개요

• SkipList는 BST와는 다른 방식으로 탐색의 시간복잡도 O(log n)을 달성하기 위한 자료구조이다.

• 기본적으로는 음의 무한과 양의 무한 값을 지닌 두 node사이에 위치하는 LinkedList라고 볼 여지가 있으나, SkipList는 랜덤성과 level를 이용하여 탐색의 효율을 유지한다.

• SkipList의 node는 상하좌우 pointer를 지닌다.

• 값을 더할 경우, 더하기 전에 코인토스를 시행한다. 그리고 뒷면(tail)이 나올때까지 반복한다.

• 한번 뒷면이 나오면, 뒷면이 나오기까지의 시행횟수만큼 level를 더하고, 모두에 데이터를 더한다. 모양은 다음과 같다.

level3 -inf    10                       inf 

level2 -inf    10     20          40    inf

level1 -inf    10     20    30    40    inf

• 탐색을 할 경우, 시작은 최상단 level의 -inf부터 시작한다. 목적하려는 데이터가 현재 node보다 크다면 오른쪽으로, 작다면 하위 레벨로 내려간다. 더 내려갈 레벨이 없다면, 데이터는 SkipList 내부에 없는 것이고, 중간에 일치한다면 존재하는 것이다.

2. 쓰임새

• SkipList는 BST에 비해 다음과 같은 이점을 가진다.

  	1. BST는 데이터가 remove될 경우, 구조에 변형이 생기기 때문에 접속이 동시에 이루어졌을 경우 처리에 문제가 생길 수 있다. SkipList는 구조에 변형이 생기진 않기 때문에, 동시 접속이 이루어져도 큰 문제는 생기지 않는다.
  	2. BST의 시간복잡도는 평균적으로, 이론적으로는 O(log n)이 맞다. 하지만, 실질적인 시간복잡도는 BST의 형태에 영향을 크게 받는다. 예를들어, BST가 degenerate한 상태이면, 시간복잡도는 O(n)이 되어버려 사용한 목적을 달성할 수 없다. 이를 보정하기 위한 여러 방법들이 존재하지만, 구현이 복잡해지는 문제가 발생한다. 이에 비하면 SkipList는 구현이 더 편리하다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xII+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.