스킵 리스트 (Skip List)

스킵 리스트 (Skip List)

다층 연결 리스트 구조로 상위 레벨이 하위 레벨의 지름길 역할을 하여 평균 O(log n) 시간에 검색·삽입·삭제를 수행하는 확률적 자료구조

목적: 균형 트리 대안, 빠른 검색·삽입·삭제, 단순한 구현, 동시성

특징: 다층 구조, 확률적 균형, 지름길, 연결 리스트 기반

구조: 레벨 0(모든 노드) + 상위 레벨(일부 노드), 상위 레벨은 지름길

동작

• •검색: 최상위 레벨부터 → 다음 노드 > 목표면 아래 레벨 → 반복
• •삽입: 검색으로 위치 찾기 → 동전 던지기(확률 p=0.5)로 레벨 결정 → 각 레벨에 삽입
• •삭제: 검색으로 찾기 → 모든 레벨에서 제거

확률적 균형: 삽입 시 50% 확률로 상위 레벨 승격 → 평균 log₂(n) 레벨

시간 복잡도: 검색·삽입·삭제 평균 O(log n), 최악 O(n)

공간 복잡도: 평균 O(n), 추가 포인터 ~2n

장점: 구현 단순(균형 불필요), 평균 O(log n), 동시성 지원(락 적음), 범위 쿼리

단점: 확률적(최악 O(n)), 추가 메모리(포인터), 캐시 비효율

적용사례: Redis(Sorted Set), LevelDB, 메모리 관리, 동시성 자료구조

비교: 스킵 리스트(확률적/단순) vs AVL(결정적/복잡/균형보장) vs Red-Black(복잡/균형)

연관: 연결 리스트, 확률적 자료구조, Redis, 동시성