본문 바로가기

이글루스

수까락의 프로그래밍 이야기

검색페이지 이동

사이드 메뉴

이글루스 블로그 정보

Skip lists에 대한 짧은 소견

앱으로 보기

본문 폰트 사이즈 조절

이글루스 블로그 컨텐츠

연결리스트에서 특정 노드의 검색, 특정 위치로의 삽입, 특정 노드 제거의 복잡도는 O(n) 이다.
head부터 노드 by 노드로 적합한 노드를 찾아가야 되기 때문이다.

이를 해결하기 위해 1989년 메릴랜드 대학의 William Pugh 교수는 "Skip Lists"라는 걸 고안하게 된다.
위 동작들이 binary search tree에서의 효율인 O(log n)의 효율로 이루어 지게 하려는 것이다.
최상의 경우 input data가 random인 경우 O(log n)의 효율을 가지게 되지만,
최악의 경우 정렬된 데이터들이 입력된다면 O(n)의 복잡도를 가지게 된다.

Skip lists는 일반적인 연결리스트와 아래와 같은 차이를 가진다.
1. 일반적인 연결리스트의 노드는 하나의 'next' 포인터를 가지지만, Skip Lists의 노드는 다수의 'next' 포인터를 가진다. (foward 포인터라 불림)
2. 노드의 Foward 포인터 수는 노드의 수에 따라 달라질 수 있다.

Skip Lists에서 노드는 level을 가진다라고 표현되며 level=foward 포인터의 수이다.
그리고 레벨의 수를 노드의 크기라 부른다. Header는 MaxLevel 수를 가진다.

ex) Skip every second node


Node의 방문수는 (n/2)+1이 된다. 즉 (16/2)+1 = 9

ex) Skip every second and fourth node

Node의 방문수는 (n/4)+3이 된다. 즉 (16/4)+3 = 7

ex) Skip every 2^i th node


이 방식은 언뜻 보기에 효율이 좋아보이지만 삽입과 삭제 후 node들의 재정렬이 필요하며 이 과정의 효율은 O(n)이 된다.

위의 3가지 예를 보면 알 수 있듯이 Skip Lists에는 node의 수 제약이 있는 거 같다.
ex 1과 2의 방식은 node list에 변화가 있을 때 node들의 재정렬은 필요없지만 수가 많아져도 효율이 증가하지 않는다. 3의 방식은 언뜻 보기에 node수가 증가해도 전체 list의 탐색 성능은 보장이 되는 것 같지만 node list에 변화가 있을 때 기존의 링크를 모두 갱신, 재정렬 하는 과정에 추가 비용이 소모된다.

소수의 데이터를 다루면서 특정 위치의 노드에 대한 오퍼레이션이 많은 경우 간단히 map 같은 자료구조를 쓰는 것이 훨씬 정신 건강에 이롭다는 생각이 든다. (게다가 코딩하기도 쉽지 않다 -_-)
이러한 이유들로 제안된 지 17년이 되었지만 널리 쓰여지지 않고 있는 것 같다.

BUT !!! 여유가 생기면 Skip Lists에 대해 좀 더 알아보고 그 강력함을 느껴봐야 겠다.


포스트 공유하기

썸네일
Sweeper님의 글 구독하기
덧글 0 관련글(트랙백) 0
신고
맨 위로
앱으로 보기 배너 닫기

공유하기

주소복사

아래의 URL을 길게 누르면 복사할수있습니다.

http://sweeper.egloos.com/m/867460
닫기

팝업

모바일기기에서만 이용이 가능합니다.
운영체제가 안드로이드, ios인
모바일 기기에서 이용해주세요.

덧글 삭제

정말 삭제하시겠습니까?

비밀번호 확인

게시글 신고하기

밸리 운영정책에 맞지 않는 글은 고객센터로
보내주세요.

신고사유


신고사유와 맞지 않을 경우 처리되지 않을 수 있습니다.
저작권 위반/명예훼손 등은 고객센터를 통해 권리침해
신고해주세요.
고객센터 바로가기