사용 개념: 선형 탐사의 넣기와 지우기(뭉치 당기기), 체이닝의 정렬된 체인. 홈 버킷은 늘 키를 버킷 수로 나눈 나머지다.
“키를 넣고 하나를 지워라”는 문제는 같은 하위목표의 되풀이다. ① 홈 버킷 구하기 ② 넣기: 홈 버킷부터 오른쪽으로(끝에 닿으면 0번으로) 가서 처음 만난 빈 버킷에 넣는다 ③ 빈 자리 만들기: 지울 키의 버킷을 비운다 ④ 뭉치 훑기: 빈 자리의 오른쪽부터 빈 버킷이 나올 때까지 하나씩 본다. 그 키의 홈 버킷이 “빈 자리의 다음 칸부터 지금 칸까지” 사이에 있으면 그대로 두고, 없으면 빈 자리로 옮기고 그 칸을 새 빈 자리로 삼는다 ⑤ 확인: 남은 키마다 홈 버킷에서 그 키까지 빈 버킷이 없는지 본다.
문제 1 · 완전한 풀이
버킷 11개짜리 표에 키 1, 12, 3, 23, 4, 14를 차례로 넣고, 12를 지워라.
- 홈 버킷 구하기: 1 → 1, 12 → 1, 3 → 3, 23 → 1, 4 → 4, 14 → 3.
- 넣기: 1은 1번. 12는 1번이 차 있어 2번. 3은 3번. 23은 1, 2, 3번이 차 있어 4번. 4는 4번이 차 있어 5번. 14는 3, 4, 5번이 차 있어 6번.
버킷: 0 1 2 3 4 5 6 7 8 9 10
키: . 1 12 3 23 4 14 . . . .
- 빈 자리 만들기: 12가 있던 2번을 비운다.
- 뭉치 훑기:
| 보는 버킷 | 키 (홈 버킷) | 홈 버킷이 사이에 있는가 | 한 일 |
|---|---|---|---|
| 3 | 3 (3) | 3번 한 칸 사이에 3이 있다 | 그대로 둔다 |
| 4 | 23 (1) | 3, 4번 사이에 1은 없다 | 2번으로 옮긴다. 빈 자리는 4번 |
| 5 | 4 (4) | 5번 한 칸 사이에 4는 없다 | 4번으로 옮긴다. 빈 자리는 5번 |
| 6 | 14 (3) | 6번 한 칸 사이에 3은 없다 | 5번으로 옮긴다. 빈 자리는 6번 |
| 7 | 빈 버킷 | 끝 |
버킷: 0 1 2 3 4 5 6 7 8 9 10
키: . 1 23 3 4 14 . . . . .
- 확인: 23은 홈 버킷 1번에서 2번까지, 14는 3번에서 5번까지 빈 버킷이 없다. 4는 이제 자기 홈 버킷에 있다.
3을 그대로 두는 까닭: 3은 자기 홈 버킷 3번에 있다. 2번으로 옮기면 홈 버킷보다 앞에 놓여 찾기가 닿지 못한다.
문제 2 · 마지막 하위목표만 빈칸
문제 1의 처음 표(12를 지우기 전)에서 이번에는 1을 지워라.
- 빈 자리 만들기: 1이 있던 1번을 비운다.
- 뭉치 훑기: 2번의 12(홈 1)는 사이에 홈이 없어 1번으로 옮긴다. 빈 자리는 2번.
- 3번의 3(홈 3)은 3번 한 칸 사이에 홈이 있어 그대로 둔다.
- 4번의 23(홈 1)은 2번으로 옮긴다. 빈 자리는 4번. 5번의 4(홈 4)는 4번으로 옮긴다. 빈 자리는 5번.
- 6번의 14(홈 3)는? 그리고 끝난 뒤의 표는? __
답
14의 홈 버킷 3은 “6번 한 칸” 사이에 없으므로 5번으로 옮긴다. 빈 자리는 6번이 되고, 7번이 비어 있어 끝난다.
버킷: 0 1 2 3 4 5 6 7 8 9 10
키: . 12 23 3 4 14 . . . . .
문제 3 · 하위목표 절반이 빈칸
버킷 7개짜리 표에 키 5, 12, 0, 19, 8을 차례로 넣고, 5를 지워라. 뭉치가 6번을 넘어 0번으로 이어진다는 점에 주의한다.
- 홈 버킷 구하기: 5 → 5, 12 → 5, 0 → 0, 19 → 5, 8 → 1.
- 넣기: __
- 빈 자리 만들기: 5가 있던 5번을 비운다.
- 뭉치 훑기: 6번의 12(홈 5)는 5번으로 옮긴다. 빈 자리는 6번. 0번의 0(홈 0)은? __ 1번의 19(홈 5)는? __ 2번의 8(홈 1)은? __
- 끝난 뒤의 표: __
답
- 5는 5번. 12는 6번. 0은 0번. 19는 5, 6, 0번이 차 있어 1번. 8은 1번이 차 있어 2번.
버킷: 0 1 2 3 4 5 6 키: 0 19 8 . . 5 12
- 0의 홈 버킷 0은 “6번 다음부터 0번까지”, 곧 0번 한 칸 사이에 있다. 그대로 둔다. 19의 홈 버킷 5는 “0번, 1번” 사이에 없다. 6번으로 옮기고 빈 자리는 1번. 8의 홈 버킷 1은 “2번 한 칸” 사이에 없다. 1번으로 옮기고 빈 자리는 2번. 3번이 비어 있어 끝난다.
5.버킷: 0 1 2 3 4 5 6 키: 0 8 . . . 12 1919는 0을 건너뛰어 6번으로 간다. 0은 자기 홈 버킷에 있어 움직이면 안 되지만, 19는 홈 버킷이 5번이라 6번에 놓여도 찾기가 닿는다.
문제 4 · 독립 문제
버킷 13개짜리 표에 키 14, 27, 16, 40, 5, 29, 18, 6을 차례로 넣는다. (a) 선형 탐사 표를 그리고, 있는 키를 찾을 때 보는 버킷 수의 평균을 구하라. (b) 27을 지운 뒤의 표를 그려라. (c) 같은 키를 정렬된 체인으로 달면 어떻게 되는가? 있는 키를 찾을 때 보는 노드 수의 평균을 구하고 (a)와 견주라. 체인에서 27을 지우면 무엇이 바뀌는가?
답
(a) 홈 버킷은 14 → 1, 27 → 1, 16 → 3, 40 → 1, 5 → 5, 29 → 3, 18 → 5, 6 → 6이다.
버킷: 0 1 2 3 4 5 6 7 8 9 10 11 12
키: . 14 27 16 40 5 29 18 6 . . . .
본 버킷 수는 14: 1, 27: 2, 16: 1, 40: 4, 5: 1, 29: 4, 18: 3, 6: 3으로 합이 19, 평균 \(\frac{19}{8} = 2.375\)다.
(b) 빈 자리 2번에서 시작한다. 16(홈 3)은 그대로, 40(홈 1)을 2번으로, 5(홈 5)는 그대로, 29(홈 3)를 4번으로, 18(홈 5)을 6번으로, 6(홈 6)을 7번으로 옮긴다.
버킷: 0 1 2 3 4 5 6 7 8 9 10 11 12
키: . 14 40 16 29 5 18 6 . . . . .
(c) 체인은 [1] → 14 → 27 → 40, [3] → 16 → 29, [5] → 5 → 18, [6] → 6이다. 본 노드 수는 14: 1, 27: 2, 40: 3, 16: 1, 29: 2, 5: 1, 18: 2, 6: 1로 합이 13, 평균 \(\frac{13}{8} = 1.625\)다. 선형 탐사의 2.375보다 작다. 선형 탐사에서는 1번에서 넘친 40이 3번 쪽 키들 사이에 끼어 29, 18, 6까지 밀어냈지만, 체인에서는 버킷끼리 섞이지 않는다. 체인에서 27을 지우면 14의 link가 40을 가리키게 될 뿐, 다른 노드는 움직이지 않는다. 선형 탐사에서는 키 네 개를 옮겨야 했다.