현재 노드(current)와 다음 노드(next)
현재 노드는 지금 서 있는 노드이고 다음 노드는 같은 층의 바로 오른쪽 노드입니다. 이동하기 전에 next.key가 목표를 넘는지 비교합니다.
아주 작은 예: current=13@\(L0, \text{next}=19, \text{target}=18\)
L0, next=19, target=18이면 오른쪽 이동 금지입니다.4. Probabilistische Datenstrukturen (4 Punkte)
4(c) · 18과 66 검색 경로 — 오른쪽으로 갈 수 있을 만큼 가고, 넘으면 아래로
선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.
- 용어: 기호와 전제
- 직관: 비유와 작은 예
- 풀이: 실제 상태 변화
- 확인: 검산과 자가점검
자료의 성격과 정확성 경계
문제 문언, 초기 그림, p와 난수열은 SoSe 2025 시험 기억 복기(reconstructed) 자료이며 공식 시험지나 공식 답안이 아닙니다. 구조·검색·삽입 알고리즘은 SoSe 2026 현재 강의로 검증했고, ‘난수가 p보다 작으면 승격’ 규칙과 유사 연산은 공식 Übung Sheet08 해설로 교차 확인했습니다. 그림의 정답은 이 명시된 난수 convention과 누적 상태 \(4(a)\to 4(b)\to 4(c)\)4(a)→4(b)→4(c)를 전제로 합니다.
문제를 읽기 전에 알아둘 기호와 용어
기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.
| 기호·용어 | 뜻 | 작은 예 |
|---|---|---|
| 항목 (Level 0 (L0)) | 모든 실제 key가 빠짐없이 있는 가장 아래의 완전한 정렬 리스트입니다. | 초기 L0: −∞,13,21,47,66,95 |
| 항목 (−∞ / head) | 모든 key보다 작은 sentinel node이며 각 level의 탐색 시작점입니다. 실제 저장 key가 아닙니다. | 검색은 −∞@L2에서 시작 |
| 항목 (tower) | 같은 key의 node가 Level 0부터 어떤 최고 level까지 수직으로 연결된 묶음입니다. | 초기 key 47은 L0,L1,L2의 세 node |
| 항목 (next / down) | next는 같은 level에서 오른쪽 node, down은 같은 tower의 바로 아래 node를 가리키는 pointer입니다. | 47@L1.down=47@L0 |
| 빈 포인터 (nil) | 더 이동할 node가 없음을 나타내는 값입니다. L0에서 \(\text{down}=\text{nil}\)down=nil이 되면 검색 실패입니다. | 13@L0에서 \(\text{down}=\text{nil}\)down=nil |
| 항목 (p, r) | p는 승격 확률, r은 [0,1)에서 받은 난수입니다. 이 페이지의 규칙은 \(r<p\)r<p이면 한 층 승격입니다. | \(0.15<0.33\)0.15<0.33이므로 67을 L1에 추가 |
먼저 문제의 정체를 줄글로 이해하기
검색은 최고 Level의 head에서 시작합니다. 다음 key가 목표 이하이면 오른쪽, 다음 key가 목표보다 크거나 next가 없으면 아래로 이동합니다. 현재 key가 목표와 같으면 즉시 성공입니다.
18은 목록에 없으므로 Level 0까지 내려가 13 뒤에서 \(\text{next}=19\)next=19가 너무 큰 것을 확인한 후 nil로 내려가 실패합니다. 검색 실패도 마지막으로 비교한 위치까지 경로를 그려야 합니다.
66은 Level 2에서 19와 47을 급행으로 지나고, 67이 너무 큰 Level 1에서 내려간 뒤 Level 0의 66으로 이동해 성공합니다.
필요한 개념을 깊게 배우기
0단계 · 검색(search) 규칙
current.next가 존재하고 \(\text{next}.\text{key}\le k\)next.key≤k이면 오른쪽으로 이동합니다. 그렇지 않으면 current.down으로 내려갑니다. 이 규칙 때문에 목표를 절대로 오른쪽으로 지나치지 않습니다.
\(\text{current}.\text{key}=k\)current.key==k이면 찾은 것이고, 아래로 내려갈 곳이 nil이면 목록에 없다는 뜻입니다.
수식으로 정확히 쓰기
핵심 규칙\mathrm{next.key}\le k\Longrightarrow\text{오른쪽}
핵심 규칙\mathrm{next.key}>k\;\lor\;\mathrm{next}=\mathrm{nil}\Longrightarrow\text{아래쪽}
1단계 · 실패 검색: 18은 없음
2층 머리 노드(head)에서 다음 값\((\text{next})=19>18\)(next)=19>18이므로 곧바로 1층 머리 노드로 내려갑니다. 1층에서도 \(19>18\)19>18이라 0층 머리 노드로 내려갑니다.
0층에서는 다음 값 \(13\le 18\)13≤18이라 13으로 이동합니다. 이제 다음 값 \(19>18\)19>18이고 더 내려갈 층이 없으므로 18은 없습니다.
수식으로 정확히 쓰기
핵심 규칙(-\infty)_{2}\downarrow(-\infty)_{1}\downarrow(-\infty)_{0}\rightarrow13_{0},\qquad 19_{0}>18\Longrightarrow\text{실패}
2단계 · 성공 검색: 66을 찾음
2층에서 \(19\le 66,\)19≤66,이어서 \(47\le 66\)47≤66이므로 오른쪽으로 두 번 갑니다. 다음 노드가 없으므로 1층의 47로 내려갑니다.
1층에서 다음 값 \(67>66\)67>66이므로 0층의 47로 내려갑니다. 0층에서 다음 값 \(66\le 66\)66≤66이므로 66으로 이동하고 등호를 확인해 성공합니다.
수식으로 정확히 쓰기
핵심 규칙(-\infty)_{2}\rightarrow19_{2}\rightarrow47_{2}\downarrow47_{1}\downarrow47_{0}\rightarrow66_{0},\qquad 66=66\Longrightarrow\text{성공}
3단계 · 경로 길이와 기대 검색시간
답안의 화살표는 실제 현재 노드(current) 이동만 그리되, 왜 방향을 바꿨는지 다음 키(next key) 비교를 옆에 적으면 부분점수를 지키기 쉽습니다.
스킵 리스트는 높은 층에서 여러 0층 노드를 건너뛰므로 평균 검색 시간이 로그입니다. 다만 한 번의 구체적 구조에서는 경로 길이가 난수로 만들어진 탑 배치에 좌우됩니다.
수식으로 정확히 쓰기
핵심 규칙\mathbb{E}[T_{\text{검색}}(n)]=\Theta\!\left(\\(\log_{1/p}n\)log₁/p}n\right)
이 소문제를 왜 배우나
Skip List의 속도는 높은 express level에서 여러 L0 node를 건너뛰고, 목표를 넘기 직전에만 아래로 내려가는 검색 경로에서 나옵니다. 성공 검색과 실패 검색을 모두 그리면 next 비교, 실제 이동, nil 종료를 구분할 수 있습니다.
- 최고 head에서 시작해 \(\text{next}.\text{key}\le \text{target}\)
next.key≤target이면 right, 아니면 down이라는 규칙을 매 단계 적용할 수 있습니다. - 실제 이동 edge와 ‘너무 커서 선택하지 않은 next’ 비교를 다른 표식으로 읽고 검색 경로를 재현할 수 있습니다.
- target을 찾은 성공과 L0 아래 nil에 도달한 실패를 정확한 종료 조건으로 설명할 수 있습니다.
풀이 전에 꼭 알아야 할 말
오른쪽 이동(right move)
다음 노드가 존재하고 \(\text{next}.\text{key}\le \text{target}\)next.key≤target일 때만 현재 노드를 다음 노드로 바꿉니다. 이 규칙은 목표보다 큰 키를 지나치지 않게 합니다.
아주 작은 예: \(\text{target}=66\)
target=66에서 \(19\le 66,47\le 66\)19≤66,47≤66이므로 L2에서 오른쪽입니다.아래쪽 이동(down move)
다음 노드가 없거나 \(\text{next}.\text{key}>\text{target}\)next.key>target이면 같은 키 탑의 바로 아래 노드로 내려갑니다. 중간 층을 한 번에 건너뛰지 않습니다.
아주 작은 예: 47@L2 다음이 없으면 47@L1로 내려갑니다.
찾음(found)과 빈 포인터(nil)
\(\text{current}.\text{key}=\text{target}\)current.key=target이면 즉시 성공입니다. current.down이 nil이 되어 반복을 빠져나오면 그 키는 목록에 없습니다.
아주 작은 예: 13@\(L0.\text{down}=\text{nil}\)
L0.down=nil이므로 search(18)은 실패합니다.급행을 타되 목적지를 지나치기 전에 환승하기
목적지 66을 향해 특급선에서 19와 47까지 빠르게 갑니다. 다음 급행역 67은 목적지를 지나므로 타지 않고 같은 47역의 아래 노선으로 환승합니다. 일반선에서 66을 만나면 내리고, 18처럼 두 역 사이에 표지판이 없으면 지상 아래까지 내려가 부재를 확정합니다.
현재 서 있는 역
↔
current node
다음 역이 목적지 이하
↔
\(\text{next}.\text{key}\le \text{target}\)
next.key≤target이면 right다음 역이 목적지를 초과
↔
\(\text{next}.\text{key}>\text{target}\)
next.key>target이면 down가장 아래에서도 역 없음
↔
\(\text{down}=\text{nil}\)
down=nil이면 NOT FOUND비유의 한계: 실제 알고리즘은 뒤로 돌아가지 않고, 비교한 모든 next node로 이동하는 것도 아닙니다. 그림에서는 실선 path와 이동하지 않은 blocked comparison을 구분해야 합니다.
한 단계마다 하는 세 질문
equality를 먼저 검사하고, 그다음 right 가능 여부를 봅니다. right가 불가능하면 down이며 L0 아래에서는 nil이 됩니다.
먼저 작은 예제로 연습 · L1=[−∞,5], L0=[−∞,2,5,8]에서 search(7)
최고 L1 head에서 시작합니다. 실제 이동과 비교했지만 선택하지 않은 \(\text{next}=8\)next=8을 구분합니다.
\(\text{next}=5\le 7\)next=5≤7이므로 목표를 넘지 않고 급행으로 이동할 수 있습니다.
같은 level에 next가 없으므로 5 tower의 L0 node로 내려갑니다.
5@L1 ↓ 5@L0next=8을 보고 right 거부\(8>7\)8>7이라 이동하면 목표를 지나치므로 5@L0에 머문 채 down을 선택합니다.
down=nil로 실패L0 아래 node가 없어 \(\text{current}=\text{nil}\)current=nil이 되고 search는 NOT FOUND를 반환합니다.
작은 예제의 결론: 실패는 ‘못 찾았다’는 추측이 아니라 목표가 들어갈 두 이웃 5와 8을 확인한 뒤 L0 아래로 내려가 증명됩니다.
이제 실제 시험 문제에 연결
search(18)은 L2에서 왜 바로 내려가나?
head의 \(\text{next}=19\)next=19가 18보다 큽니다. 오른쪽으로 가면 목표를 넘으므로 −∞@L2에서 −∞@L1로 내려갑니다.
L0에서는 왜 13까지 오른쪽으로 가나?
\(\text{next}=13\le 18\)next=13≤18이라 안전합니다. 그 다음 \(\text{next}=19\)next=19는 18보다 커서 이동하지 않고 13@L0에서 아래를 선택합니다.
search(18)의 실패를 무엇으로 확정하나?
13과 19 사이에 18 node가 없고 13@\(L0.\text{down}=\text{nil}\)L0.down=nil이라 더 탐색할 level이 없습니다. 따라서 \(\text{current}=\text{nil}\)current=nil로 종료해 NOT FOUND입니다.
search(66)은 L2에서 어디까지 가나?
\(19\le 66,47\le 66\)19≤66,47≤66이라 −∞→\(19\to 47\)19→47로 이동합니다. L2에 next가 없으므로 47 tower를 L1으로 내려갑니다.
왜 L1의 67로 가지 않나?
\(67>66\)67>66이라 목표를 지나치므로 blocked comparison으로만 표시합니다. 47@L1에서 47@L0로 내려간 뒤 \(\text{next}=66\)next=66으로 이동해 FOUND입니다.
답이 맞는지 스스로 검산
- 경로의 첫 node가 최고 level의 −∞이고 모든 right edge는 도착 \(\text{key}\le \text{target}\)
key≤target인지 확인합니다. - 모든 down edge가 같은 key의 바로 아래 level로 이어지며 L2에서 L0로 중간 node를 건너뛰지 않는지 확인합니다.
- 18은 13 다음 19가 blocked이고 \(\text{down}=\text{nil}\)
down=nil로 끝나며, 66은 \(\text{current}.\text{key}=66\)current.key==66에서 즉시 끝나는지 확인합니다. - overlay의 실선 화살표는 실제 이동, 빨간 점선은 비교했지만 이동하지 않은 next임을 구분합니다.
30초 자가점검
search(20)은 최종 구조에서 L2의 19 뒤 어디로 가나?
힌트: L2의 다음 47과 target 20을 비교하세요.
정답: \(47>20\)47>20이라 19@L2에서 19@L1로 내려가고, 다시 L0로 내려가 \(\text{next}=21>20\)next=21>20을 확인한 뒤 nil로 실패합니다.
next.key가 target과 같으면 right인가 down인가?
힌트: 조건은 <가 아니라 ≤입니다.
정답: right로 그 node에 이동하고 다음 loop의 equality 검사에서 FOUND를 반환합니다.
47@L2에서 바로 47@L0로 내려가도 경로 답이 맞나?
힌트: down pointer는 어느 level을 가리키는지 확인하세요.
정답: 아닙니다. down은 바로 아래 47@L1을 가리키므로 경로에 L1 node를 포함해야 합니다.
마지막에 쓰는 시험 답안 틀
18 검색: −∞₂↓−∞₁↓−∞₀→\(13₀\)13₀뒤 \(19>18\)19>18이므로 없음(NOT FOUND). 66 검색: −∞₂→19₂→47₂↓47₁↓\(47₀\to 66₀\)47₀→66₀에서 찾음(FOUND). 다음 키가 목표보다 크면 오른쪽으로 넘지 않고 아래로 간다.
자주 하는 실수
- 검색을 Level 0에서 시작한다.
- next.key가 목표보다 큰데도 오른쪽으로 이동한다.
- 18이 없다는 결론만 쓰고 실패 경로를 그리지 않는다.
- L2의 47에서 L0로 한 번에 내려가 중간 tower node를 생략한다.
- 66 대신 상위 Level의 67로 이동했다가 되돌아온다. Skip List search는 뒤로 가지 않습니다.
- 4(b) 이전 구조에서 검색해 19·67 tower를 누락한다.
근거와 정확성 범위
복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.
- \(\text{reconstructed}_{\text{exam}}\)
reconstructed(exam)AuD Gedächtnisprotokoll SoSe 2025.md· lines 226-244 and linked image · 신뢰도/범위: 복기 문언·이미지이며 공식 답안 아님초기 Skip List, p, 삽입 key, 난수열, 검색 target의 복기 문언
- \(\text{current}_{\text{lecture}}\)
current(lecture)Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 4-12 · 신뢰도/범위: 현재 강의 원문으로 검증정렬 리스트, express level, head/node pointer 모델, search pseudocode, 기대 level 크기
- \(\text{current}_{\text{lecture}}\)
current(lecture)Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 16-20 · 신뢰도/범위: 현재 강의 원문으로 검증삽입 predecessor 저장, 확률적 승격, 평균 검색·삽입·삭제 시간과 공간
- \(\text{official}_{\text{solution}}\)
official(solution)Übung\AuD26_Sheet08-Sol.pdf· pp. 8-10 · 신뢰도/범위: 공식 연습문제 풀이로 교차 검증\(r<p\)
r<p승격 convention, 첫 실패까지 난수 소비, 성공·실패 검색 path와 누적 삽입 예시
마지막 생성: 2026-08-02 08:51