B-Tree를 완벽히 이해했다고 생각하고 B-Tree를 만들어 테스트 하던 중
조금 복잡한 친구를 만났다.
일단 B Tree 삽입과 삭제의 기본 개념은 이렇다.
삽입
- 키 값의 삽입은 말단 노드에서 이루어진다.
- key값이 최대를 넘으면 가운데 키 값을 승진시키고 양쪽의 키 값을 분할한다.
//삭제
//- 말단 노드에서 삭제하고(중간 노드일 경우 최솟값 중 최대, 혹은 최댓값 중 최소 말단 노드와 교체)
//- 규칙에 어긋날 경우 회전하는 형태로 형제 노드에서 키 값을 가져온다.
//- 형제 노드가 키 값을 줄 수 없거나 Underflow가 발생할 경우, 부모 노드에서 키 값을 가져오고 //형제 노드와 병합한다. 만약, 부모 노드도 규칙에 어긋나면 다시 위의 규칙을 적용한다.삭제
- 삭제할 키가 리프(leaf) 노드에 있을 때
- 해당 키를 바로 삭제합니다.
- 삭제 후 노드의 키 개수가 최소 개수(t-1) 이상이면 추가 조치가 필요 없습니다.
- 만약 최소 개수 미만(underflow)이 되면, 형제 노드에서 키를 빌리거나 병합(merge)하여 균형을 맞춥니다.
- 삭제할 키가 내부(내부 노드, internal node)에 있을 때
- 해당 키를 바로 삭제할 수 없습니다. 대신 다음 중 하나로 대체합니다:
- 왼쪽 서브트리의 최대값(중위 전임자, inorder predecessor)
- 오른쪽 서브트리의 최소값(중위 후임자, inorder successor)
- 대체한 후, 실제 삭제는 리프 노드에서 일어나므로, 리프 노드에서 underflow가 발생할 수 있습니다. 이 경우에도 형제 노드에서 빌리거나 병합합니다.
- underflow(최소 키 개수 미만) 처리
- 형제 노드가 최소 개수보다 많은 키를 가지고 있으면: 형제 노드에서 키를 빌려와 재분배(rotate/redistribute)합니다.
- 형제 노드도 최소 개수만 있으면: underflow 노드와 형제 노드, 그리고 부모의 separator key를 합쳐 병합(merge)합니다. 이 과정에서 부모 노드의 키 개수도 줄어들 수 있으며, 필요하면 상위로 재귀적으로 병합이 전파됩니다
삭제 규칙이 복잡해서 그런지 인터넷에 확실하게 정리가 안된 것 같았다.
이걸 규칙을 막 적용해보다가 깨달았다.
몇 번의 헛발질 이후 AI에게 확실한 규칙을 물어보고 다시 적용해보고 있다.
따라서 '사건의 발단'부터 '적용'까지는 규칙을 제대로 사용하지 않았을 수도 있다.
규칙
에 대해서 먼저 설명하도록 하겠다.
- 삽입
삽입은 쉽다.
말단 노드(leaf node)에 먼저 추가하고 최대 키값을 넘으면 재구성한다.
재구성은 가운데 키 값을 부모 노드 쪽으로 올리고 양쪽 키 값을 자식 노드로 만들면 된다.
최대 키 값은 M차 트리라고 했을 때, M-1이다.
다음을 보자.
2,6
/ | \
1 3,4 8여기서 5를 추가하면
2, 6
/ | \
1 3,4,5 8이렇게 되고 키 값이 3개가 넘으므로
가운뎃 값을 위로 올리고 분할한다.
2,4,6
/ | | \
1 3 5 8마찬가지로 가운뎃 값을 올리고 분할.
4
/ \
2 6
/ \ / \
1 3 5 8- 삭제
삭제는 삭제하려는 노드를 말단 노드로 일단 옮기고 위쪽 방향으로 올라가며 규칙을 재귀적으로 적용하면 된다.
A) 말단 노드, 키의 개수가 최소 크기 초과
4
/ \
2 7
/ \ / \
1 3 5,6 83차 트리이므로 최소 키 값은 1개 이상이다.
여기서는 5, 6이 되겠다.
이런 경우에는 그냥 지우면 된다.
4
/ \
2 7
/ \ / \
1 3 6 8아주 그냥 후련하다.
B) 말단 노드, 키의 개수가 최소 크기
4
/ \
2 7
/ \ / \
1 3 5 8이 때는 일단 삭제하려는 노드에 언더플로우(Underflow)가 발생하고 이 경우 두 가지의 경우로 나눌 수 있다. 사실 이 규칙은 말단 노드가 아닐 때도 마찬가지로 적용되는 규칙이므로 여기서 확실하게 이해하자.
B-1) 형제 노드의 키의 개수가 Underflow를 발생시키지 않을 만큼 충분함.
4
/ \
2 7
/ \ / \
1 3 5 8, 9이 경우다. 우리는 5를 삭제하려고 하고, 형제 노드는 8, 9로 키 개수가 충분하다.
여기서 5를 삭제하면
4
/ \
2 7
/ \ / \
1 3 8, 9이렇게 되고
7 // 8, 9 노드에서는 회전이 일어난다.
'회전'이라는 표현을 사용하는 이유는 이게 레드블랙 트리의 회전과 상당히 유사하다.
4
/ \
2
/ \ / \
1 3 7 8,9부모는 해당 노드에게 키 값을 주고
4
/ \
2 8
/ \ / \
1 3 7 9형제 노드 중 삭제한 값에 가장 가까운 키 값을 부모 노드로 보낸다.
반대도 비슷하게 회전한다.
4
/ \
2 8
/ \ / \
1 3 5,6 99를 삭제하면
4
/ \
2 6
/ \ / \
1 3 5 8이렇게 된다.
B-2) 형제 노드의 키의 개수가 Underflow를 발생시킴
부실하기 때문에 부모님의 지원을 받으면서 합쳐야 한다.
4
/ \
2 6
/ \ / \
1 3 5 8여기서 5를 삭제해보자.
4
/ \
2 6
/ \ / \
1 3 8그럼 이제 부모님께 지원도 받고
4
/ \
2
/ \ / \
1 3 6 8형제와 합친다.
4
/ \
2
/ \ \
1 3 6,8엥 그럼 이 다음은 어떻게 하냐고?
마찬가지이다.
사실 이 규칙 때문에 결국 말단 노드를 삭제하든 중간 노드를 삭제하든 추가적으로 하는 일은 똑같다. 그래서 이 규칙을 이해하는 것이 중요하다.
먼저 부모님 지원
/ \
2 4
/ \ \
1 3 6,8그리고 합치기
2, 4
/ \ \
1 3 6,8C) 중간 노드
노드는 말단부터 제거돼야한다.
항상 중요한 것은 꼬리자르기이다.
따라서 중간노드는 말단과 교체된다.
해당 노드보다 작은 값 중 가장 큰 값(선임자)이나
해당 노드보다 큰 값 중 가장 작은 값(후임자)이다.
4
/ \
2 6
/ \ / \
1 3 5 84를 제거한다고 했을 때 4의 선임자는 3이고 후임자는 5이다.
따라서 이렇게 되거나
(선임자 교체)
'3'
/ \
2 6
/ \ / \
1 '4' 5 8이렇게 된다.
(후임자 교체)
'5'
/ \
2 6
/ \ / \
1 3 '4' 8그 다음에 제거되고
(선임자 교체)
'3'
/ \
2 6
/ \ / \
1 5 8이렇게 된다.
(후임자 교체)
'5'
/ \
2 6
/ \ / \
1 3 8나머지는 A 혹은 B와 똑같다.
사건의 발단
은 이렇다.(3차 B트리이다.)
트리가 좀 커서 복잡하게 그릴 수 밖에 없었다.
여백이 부족하다고 증명을 끝낼 수는 없지 않은가
7,15
/ | \
4 9,11 17,20
/ \ / | \ / | \
2 6 8 10 12,14 16 19 25복잡하지만 여기서 13을 넣었다. 오히려 복잡하기 때문에 13을 더 넣나 안넣나 큰 차이는 없다.
옷으로 어질러진 방에 옷 하나 더 둔다고 큰 차이가 없는 것과 마찬가지이다.
깨끗한 방은 옷 하나만 던져도 큰 차이가 생긴다.
마치 0에 아무리 많은 수를 곱해도 1이 될 수 없는 것과 같다.
아무튼 13을 넣는 과정은 다음과 같다.
7,15
/ | \
4 9,11 17,20
/ \ / | \ / | \
2 6 8 10 12,13,14 16 19 25괴물이 되어가고 있다.
규칙에 위배되기 때문에 분할 및 승진한다.
7,15
/ | \
4 9,11,13 17,20
/ \ / | / \ / | \
2 6 8 10 12 14 16 19 25규칙을 적용하는 과정이기 때문에 이상한 모양이 될 수도 있다.
마찬가지로 분할 및 승진한다.
7, 11, 15
/ / \ \
4 9 13 17,20
/ \ / \ / \ / | \
2 6 8 10 12 14 16 19 25또 다시 분할 및 승진한다.
이런걸 소위 초고속 승진이라고 한다.
11
/ \
7 15
/ \ / \
4 9 13 17,20
/ \ / \ / \ / | \
2 6 8 10 12 14 16 19 25완성.
삽입은 할만하다.
문제는 삭제다.
먼저 10을 뺐다.
11
/ \
7 15
/ \ / \
4 9 13 17,20
/ \ / \ / \ / | \
2 6 8 12 14 16 19 25부모님이 지원해주신다.
11
/ \
7 15
/ \ / \
4 13 17,20
/ \ / / \ / | \
2 6 8,9 12 14 16 19 25부모님 7이 다시 지원해준다.
11
/ \
15
/ / \
4, 7 13 17,20
/ \ \ / \ / | \
2 6 8,9 12 14 16 19 25부모님 11이 다시 지원해준다.
11, 15
/ \ \
4, 7 13 17,20
/ \ \ / \ / | \
2 6 8,9 12 14 16 19 25수정 완료
이번엔 13을 삭제해볼 예정이다.
이게 문제의 발단이었다.
11, 15
/ \ \
4, 7 13 17,20
/ \ \ / \ / | \
2 6 8,9 12 14 16 19 25우선 중간 노드를 삭제하면 작은 값 중 가장 큰 값과 교체 후
11, 15
/ \ \
4, 7 12 17,20
/ \ \ / \ / | \
2 6 8,9 13 14 16 19 25노드를 삭제한다.
11, 15
/ \ \
4, 7 12 17,20
/ \ \ / \ / | \
2 6 8,9 14 16 19 25그러면 이제 다시 형제 및 부모의 지원을 받는다.
11, 15
/ \ \
4, 7 17,20
/ \ \ | / | \
2 6 8,9 12,14 16 19 25여기서 어떻게 해야할 지 감이 안잡혔다.
다들 한 번 여기서 고민해보자.
처음에는
'형제 노드에서 키 값을 빌리고 빌릴 수 없으면 부모 노드에서 키를 가져온다'가 전부인 줄 알았다.
근데 정확한 규칙은 이거다.
'형제 노드의 키 값이 여유로울 경우 형제 노드의 키는 부모에게, 부모의 키는 나에게 온다.'
'형제 노드의 키 값이 여유롭지 못할 경우 부모에게 키를 받고 형제 노드와 병합한다.'
즉 부모에게 11을 받고 왼쪽 형제 노드와 합치거나
부모에게 15를 받고 오른쪽 형제 노드와 합친다.
여기선 부모에게 11을 받겠다.
15
/ \
4, 7, 11 17,20
/ \ \ \ / | \
2 6 8,9 12,14 16 19 25그럼 4, 7, 11이 규칙을 위배한다.
따라서 7을 승진시키고 분할한다.
7, 15
/ / \
4 11 17,20
/ \ / \ / | \
2 6 8,9 12,14 16 19 25드디어 해결이 된 것 같다.
다 없어질 때까지 해보자.
이번엔 11을 삭제한다.
7, 15
/ / \
4 9 17,20
/ \ / \ / | \
2 6 8,11 12,14 16 19 25리프 노드 9랑 바꾸고
7, 15
/ / \
4 9 17,20
/ \ / \ / | \
2 6 8 12,14 16 19 2511을 삭제한다.
이상 없다.
이번에는 17을 삭제한다.
7, 15
/ / \
4 9 17,20
/ \ / \ / | \
2 6 8 12,14 16 19 25선임자랑 바꾸고
7, 15
/ / \
4 9 16,20
/ \ / \ / | \
2 6 8 12,14 17 19 2517을 삭제한다.
7, 15
/ / \
4 9 16,20
/ \ / \ / | \
2 6 8 12,14 19 25적용
여기부터 제대로 해보겠다.
7, 15
/ / \
4 9 16,20
/ \ / \ / | \
2 6 8 12,14 19 25형제 키가 언더플로우를 발생시킬 수 있으므로
부모 지원 -1
7, 15
/ / \
4 9 20
/ \ / \ / | \
2 6 8 12,14 16 19 25형제 병합 -2
7, 15
/ / \
4 9 20
/ \ / \ / \
2 6 8 12,14 16,19 25자 이제 본격적으로 지워보자.
어려워보이는 걸 지우는 게 맞다.
9나 20은 말단 노드의 키가 많아서 지울 맛이 없다.
4를 지워보겠다. 그럼 우선 바꾼다.
7, 15
/ / \
2 9 20
/ \ / \ / \
4 6 8 12,14 16,19 25그리고 지운다.
7, 15
/ / \
2 9 20
/ \ / \ / \
6 8 12,14 16,19 25시작이다.
B-2) 형제 언더플로우
부모 지원 -1
7, 15
/ / \
9 20
/ \ / \ / \
2 6 8 12,14 16,19 25형제 합체 -2
7, 15
/ / \
9 20
/ / \ / \
2,6 8 12,14 16,19 25빈 노드도 역시
B-2) 형제 언더플로우
부모 지원 -1
15
/ / \
7 9 20
/ / \ / \
2,6 8 12,14 16,19 25형제 합체 -2
15
/ \
7,9 20
/ | \ / \
2,6 8 12,14 16,19 25계속 형제 언더플로우 하다보니 무슨 힙합 가수 이름같다.
진짜 펑 터지는 걸 보여주고 싶은데, 다들 잘 버틴다.
이번엔 15를 지워보겠다.
교체
14
/ \
7,9 20
/ | \ / \
2,6 8 12,'15' 16,19 25삭제
14
/ \
7,9 20
/ | \ / \
2,6 8 12 16,19 25이번에는 14를 지워보겠다.
교체
12
/ \
7,9 20
/ | \ / \
2,6 8 14 16,19 25삭제
12
/ \
7,9 20
/ | \ / \
2,6 8 16,19 25부모 지원
12
/ \
7 20
/ | \ / \
2,6 8 9 16,19 25형제 병합
12
/ \
7 20
/ \ / \
2,6 8,9 16,19 25- 삭제한다.
교체
12
/ \
6 20
/ \ / \
2,7 8,9 16,19 25삭제
12
/ \
6 20
/ \ / \
2 8,9 16,19 25- 삭제한다.
교체
12
/ \
8 20
/ \ / \
2 6,9 16,19 25삭제
12
/ \
8 20
/ \ / \
2 9 16,19 25- 삭제한다.
교체
12
/ \
2 20
/ \ / \
8 9 16,19 25삭제
12
/ \
2 20
/ \ / \
9 16,19 25큰게 올 것 같다.
부모 지원
12
/ \
20
/ \ / \
2 9 16,19 25병합
12
/ \
20
/ / \
2,9 16,19 25부모지원
/ \
12 20
/ / \
2,9 16,19 25병합
12,20
/ | \
2,9 16,19 25이쯤되면 식상하다.
이제 그만하자
트리 퍼가요