skip list란 무엇이며, 어떻게 O(log n) 검색을 달성하나요?

Question

Accepted Answer

**skip list(스킵 리스트)**는 여러 **"급행 차선(express lane)"** 레벨로 보강된 정렬된 linked list입니다. 상위 레벨은 많은 노드를 건너뛰므로, 검색이 아래로 내려가며 오른쪽으로 이동하여 **O(log n)** 기대 시간을 달성합니다. balanced tree의 확률적이고 더 단순한 대안과 같습니다. ## 구조 ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (전체 리스트) ``` 각 노드는 확률 `p`(흔히 0.5)로 상위 레벨로 승급되므로, 평균적으로 각 레벨은 그 아래 레벨의 절반만큼의 노드를 갖습니다. ## 검색 ```text search(25): 좌상단에서 시작, next <= target인 동안 오른쪽으로 이동, 아니면 한 레벨 아래로 내려감. 레벨 0까지 반복. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # 동전 던지기가 노드의 높이를 결정 return lvl ``` ## 복잡도 | 연산 | 기대 | 공간 | |---|---|---| | 검색 | O(log n) | O(n) | | 삽입 / 삭제 | O(log n) | — | ## balanced tree 대비 트레이드오프 - **강점:** red-black/AVL보다 구현이 훨씬 단순함; 회전 없음; 동시성 버전이 쉬움(Redis sorted set, Java `ConcurrentSkipListMap`에서 사용됨). - **약점:** 확률적 보장(최악의 경우 보장 아님); 노드당 추가 포인터. ## 왜 중요한가 skip list는 훨씬 적은 코드와 쉬운 락프리 동시성으로 tree와 같은 O(log n) 정렬 연산을 제공하며, 이것이 Redis 같은 실제 시스템이 이를 선택하는 이유입니다. 복잡한 결정론적 균형 로직을 대체하기 위해 **무작위화(randomization)**를 사용하는 훌륭한 예입니다.