merge 연산은 부모에 있는 키 하나가 왼쪽 자식 노드와 오른쪽 자식 노드의 가운데로 삽입되며 노드가 병합되는 것입니다. 다음 그림을 봅시다.

▲ 그림 10-15 merge 3

그림 10-15를 보면 먼저 부모 노드의 키 7이 왼쪽 자식 노드 끝에 추가됩니다. 왼쪽 서브 노드가 비어 있으므로 키 7이 붙으면 키 7만 있는 노드가 생성됩니다. 그림 10-15에서 이 과정을 볼 수 있습니다.

이제 키 7만 있는 왼쪽 자식 노드에 부모 노드가 병합될 차례입니다만 부모 노드는 비어 있지요. 다음 그림과 같이 빈 노드를 병합한 후 키 8만 있는 오른쪽 자식 노드를 병합합니다.

▲ 그림 10-16 merge 4