그림 10-11을 보면 먼저 새로운 노드를 생성한 후 키 5가 왼쪽 서브 트리로 내려옵니다. 그럼 부모 노드가 비게 됩니다. 이제 키 7이 부모 노드에 가면 됩니다. 마치 반시계 방향으로 회전하는 것 같군요.

그다음은 어떻게 될까요? 다음 그림으로 확인해 봅시다.

▲ 그림 10-12 donate 3

그림 10-12를 보면 키 7이 부모 노드로 가서 donate 연산이 종료됩니다. 모든 리프 노드는 같은 레벨에 있고, 어떤 노드를 기준으로 해도 왼쪽 서브 트리의 모든 키 값은 현재 노드보다 작고 오른쪽 서브 트리의 모든 키 값은 현재 노드보다 큽니다. 그리고 노드의 서브 트리 개수가 2 이상이어야 한다는 특징도 잘 유지하고 있군요.

그림 10-13에 표시된 키 5를 삭제해 보겠습니다.

▲ 그림 10-13 merge 1