그림 10-16을 보면 키 8을 가진 노드가 키 7을 가진 노드에 병합된 모습을 볼 수 있습니다. 그런데 부모 노드가 빈 노드입니다. 빈 노드는 왼쪽 노드에 donate 연산이 가능한지 질의합니다. 형제 노드도 키가 하나밖에 없군요. 다시 merge 연산을 해야만 합니다.

다음 그림과 같이 부모 노드의 키 4가 키 2를 가진 노드의 마지막에 삽입됩니다.

▲ 그림 10-17 merge 5

그림 10-17은 부모 노드에 있던 키 4가 키 2를 가진 왼쪽 자식 노드의 끝에 추가된 모습입니다. 이제 오른쪽 자식 노드를 병합하면 됩니다. 오른쪽 노드는 빈 노드이군요. 빈 노드가 병합되면서 키 2와 키 4가 있는 노드의 맨 마지막 자식 참조가 키 7과 키 8이 있는 노드를 가리키게 됩니다.

▲ 그림 10-18 merge 6