상위문서 : 자료구조
필수참고문서 : 연결리스트
목차
1. 개요
2. 설명
3. 스킵리스트의 문제점
4. 구현
3.1. JAVA로 구현
3.2. C#으로 구현
3.2. C#으로 구현
1.개요
스킵리스트란 연결리스트의 고질적인 문제인 탐색시간이 오래걸리는 점을 개선을 위해 노드간 이동시 스킵 포인터를 이용하여 빠르게 탐색이 가능한 랜덤 자료구조이다.
2.설명
용사가 마왕을 무찌르는 RPG게임을 생각해보자 용사는 다섯개의 대 스테이지를 깨야하며 각 스테이지는 소규모 스테이지 5개씩을 가지고 있다. 만약 키보드 화살표로 스테이지를 선택하는게 가능하다.
예를들어 1-1 스테이지에서 출발해 -> 화살표를 누르면 1-2로 바뀌는 것이다. 여기서 1-5스테이지에서 ->를 누르면 2-1스테이지로 바뀐다. 그런데 이런 방식으로 5-5스테이지를 플레이 하려면 ->버튼만 25번 눌러야한다. 그런데 개발자가 플레이어들이 게임을 좀더 쉽게하기 위해서 처음 선택할때는 대 스테이지부터 선택이 가능하게 바꾸었다. 이때 5-5스테이지를 선택하려면 1->2->3->4->5->5.1->5.2->5.3->5.4->5.5 10번만 조작하면 된다. 25에서 10으로 확 줄었다. 또 4-5스테이지를 가고 싶으면 1->2->3->4->5->5.1->4.5로 선택하면 된다. 이렇게 건너뜀으로서 탐색을 더욱 빠르게 할 수 있는것이 스킵리스트의 장점이다.
3. 스킵리스트의 문제점
그런데 생각해보자 위에서 봤던 스킵리스트 그림에서 추가 및 삭제가 이루어지면 자연스레 스킵할 수 있는 구간이 짧아 지는 곳도 생기며 길어지는 곳도 생긴다. 그렇다고 다시 전체 노드를 탐색하며 스킵할 수 있는 구간을 만든다고 해도 시간복잡도가 너무 걸린다. 이를 타파하기 위해서 생겨난 것이 동전 던지기 알고리즘이다. 동전 던지기 알고리즘은 동전이 항상 1/2 확률로 앞과 뒤가 나오는 것을 이용한 알고리즘이다. 스킵리스트의 각 노드마다 이 동전 던지기 알고리즘을 실행해 앞이 나오는 횟수만큼 레벨을 추가하는 것이다. 동전을 던져 앞이 나올 때마다 레벨 1이 올라가며 뒷면이 나오는 순간 알고리즘이 끝이 난다. 이때 레벨이 올라갈 확률은 다음과 같다.
레벨 0 : 뒤=1/2=50%
레벨 1 : 앞뒤=(1/2)^2=25%
레벨 2 : 앞앞뒤=(1/2)^3=12.5%
레벨 3 : 앞앞앞뒤=(1/2)^4= 6.25%
레벨 4 : 앞앞앞앞뒤=(1/2)^5= 3.125%
레벨 5 : 앞앞앞앞앞뒤=(1/2)^6= 1.0625%
레벨 5까지 가려고하면 약 1퍼의 확률을 뚤어야한다... 이렇듯 이런 비율로 레벨을 설정하면 적당한 스킵 노드가 만들어진다. 물론 1/2보다 더 작은 1/4나 1/6을 사용할 수 있지만 여기서 구현은 1/2로 간다.
레벨 0 : 뒤=1/2=50%
레벨 1 : 앞뒤=(1/2)^2=25%
레벨 2 : 앞앞뒤=(1/2)^3=12.5%
레벨 3 : 앞앞앞뒤=(1/2)^4= 6.25%
레벨 4 : 앞앞앞앞뒤=(1/2)^5= 3.125%
레벨 5 : 앞앞앞앞앞뒤=(1/2)^6= 1.0625%
레벨 5까지 가려고하면 약 1퍼의 확률을 뚤어야한다... 이렇듯 이런 비율로 레벨을 설정하면 적당한 스킵 노드가 만들어진다. 물론 1/2보다 더 작은 1/4나 1/6을 사용할 수 있지만 여기서 구현은 1/2로 간다.
4. 구현
구현을 위해서 쿼드 노드에 대해서 알아야한다. 원래 스킵리스트는 쿼드 노드를 사용하지 않아도 구현할 수 있지만 쿼드 노드를 사용하면 일반적인 경우보다 더욱 쉽게 구현이 가능하다
또한 더럽게 운이 좋을(?) 경우 레벨 10까지 생긴다고 해보자 이러면 각각의 레벨을 위해서 따로 준비해야되는 일이 여간 많은게 아니다. 따라서 어느정도 레벨에 제한을 둬야한다.
또한 더럽게 운이 좋을(?) 경우 레벨 10까지 생긴다고 해보자 이러면 각각의 레벨을 위해서 따로 준비해야되는 일이 여간 많은게 아니다. 따라서 어느정도 레벨에 제한을 둬야한다.
