스킵 리스트 편집하기 (부분)

==시간 복잡도==
스킵 리스트는 다음과 같은 평균 시간 복잡도를 갖는다.
*탐색: O(log n)
*삽입: O(log n)
*삭제: O(log n)
최악의 경우 O(n)일 수 있으나, 확률적 구조 덕분에 평균적으로는 균형잡힌 이진 탐색 트리와 유사한 성능을 가진다.

아래 분석 내용은 일부 p = 1/2으로 고정하여 쓰여졌음에 주의하자.

=== 탐색 ===
*최상위 레벨에서 시작하여 다음 규칙에 따라 탐색한다.
**현재 노드의 다음(next) 노드의 키가 찾고자 하는 키보다 작으면 → 오른쪽으로 이동
**그 외의 경우 → 한 단계 아래 레벨로 내려감
*레벨 0까지 반복하면서, 마지막으로 지나간 노드를 반환한다.
*탐색은 각 레벨당 평균 한 번씩 이동하므로, 전체 기대 시간은 O(log n)이다.

=== 삽입 ===
*새 노드의 레벨은 확률 p 에 따라 무작위로 결정된다.
**레벨 k가 선택될 확률은 p<sup>(k+1)</sup>, 예를 들어 p=1/2이면 (1/2)<sup>(k+1)</sup>
*'''삽입 위치 찾기 (검색 단계)'''
**탐색과 동일하게 최고 레벨부터 오른쪽으로 이동하고, 조건이 맞지 않으면 아래로 내려가며 레벨 0까지 반복
**각 레벨에서 새 노드가 삽입될 위치의 직전 노드를 기록
**이 탐색 단계의 기대 시간은 O(log n)
* '''포인터 갱신 (삽입 단계)'''
**선택된 최고 레벨 h에 대해, 각 레벨 i (0 ≤ i ≤ h)에 대해 다음을 수행***새 노드의 next[i]를 prev[i].next[i]로 지정
***prev[i].next[i]를 새 노드로 갱신
**레벨 h의 기대값은 상수 수준이므로, 이 단계의 기대 시간은 O(1)
*'''삽입 전체 기대 시간: O(log n)'''

=== 삭제 ===
*삭제할 노드의 위치를 탐색하는 과정은 삽입 시와 동일하게 수행된다.
**최상위 레벨에서 시작하여, 각 레벨에서 삭제 대상 노드 직전까지 이동
**레벨 0에서 삭제할 노드를 확인
**이 탐색 단계의 기대 시간은 O(log n)
*'''포인터 갱신 (삭제 단계)'''
**삭제할 노드가 레벨 h에 존재한다고 할 때, 각 레벨 i (0 ≤ i ≤ h)에 대해
***prev[i].next[i]를 삭제 노드의 next[i]로 갱신
** 레벨 h의 기대값은 상수 수준이므로, 이 단계의 기대 시간은 O(1)
* '''삭제 전체 기대 시간: O(log n)'''