그림을 살펴봅시다.

▲ 그림 8-6 delete

그림 8-6을 보면 cur와 replace의 키를 교환하고 나면 BST의 특성이 깨집니다. 그림에서 루트 노드 5를 기준으로 보면 왼쪽 서브 트리에 5보다 큰 6이 있지요. 이래서야 대체 노드를 지울 수 없습니다. 이제 리프 노드이니까 지울 수 있을 줄 알았는데, 이대로는 6을 search로 찾을 수 없을 것입니다. 이때 유심히 살펴보면 cur 노드의 왼쪽 서브 트리는 아직 BST의 특성이 살아 있습니다. 그렇다면 cur의 왼쪽 서브 트리에서 노드 6을 지우면 됩니다. 이때 노드 6은 반드시 오른쪽 자식 노드가 없어야 하므로 리프 노드이거나 왼쪽 자식 노드만 있는 경우의 코드가 실행될 것입니다.