코드만 보아서는 이해하기 쉽지 않습니다. 먼저 삭제하려는 노드의 키가 현재 노드의 키보다 작을 때 혹은 클 때 재귀 함수를 호출하고 있군요. 그림으로 코드를 조금 뜯어보죠.

그림을 살펴봅시다.

▲ 그림 8-5 delete

그림 8-5는 BST의 삭제 과정을 보여 줍니다. 먼저 첫 번째 상황에서 타깃을 찾을 때까지 재귀 함수를 계속 호출하며 내려갑니다. 그러다가 cur의 키 값이 5인 노드를 찾았습니다. 노드 5를 보면 왼쪽 자식만 있는 경우입니다. 이때 cur=cur.left가 실행되면 오른쪽 그림()과 같이 됩니다. 그리고 마지막에 cur 노드를 반환하고 종료되므로 반환값은 노드 4입니다. 이제 다시 노드 6이 cur일 때로 돌아왔군요. 이때 이전에 반환받은 노드 4를 new_left에 받아 놓습니다.