__make_left(cur, new_left) 메서드를 사용하여 cur의 왼쪽 자식 노드를 new_left로 만듭니다. 그럼 아래쪽 그림()과 같이 변경됩니다. 노드 5는 삭제된 것입니다. 이렇게 해서 노드가 하나일 때를 살펴보았습니다.

삭제하려는 노드가 리프 노드라면 어떨까요? 단순하게 반환하는 cur를 None으로 해서 반환합니다. 그럼 호출한 메서드 쪽에서 cur의 왼쪽 혹은 오른쪽 자식에 None을 할당할 것입니다. 즉, 리프 노드가 삭제된 것이지요.

마지막으로 자식 노드가 두 개일 때를 알아보겠습니다. 자식 노드가 두 개일 때는 그 노드를 직접 삭제하지 않습니다. 대체 노드를 찾아서 키 값을 교환한 후 대체 노드를 대신 삭제합니다. 대체 노드는 반드시 리프 노드이거나 지금 구현하려는 코드에서는 왼쪽 자식만 있는 노드입니다. 왜 그런지 그림으로 살펴볼까요? 그림 8-3에서 루트 노드인 6을 지운다고 합시다. 이때 대체 노드로 가능한 노드는 몇 개인가요? 두 개입니다. 첫 번째 노드는 노드 6의 왼쪽 서브 트리에서 가장 큰 노드고, 두 번째 노드는 노드 6의 오른쪽 서브 트리에서 가장 작은 노드입니다.

이 책에서는 왼쪽 서브 트리에서 가장 큰 노드를 대체 노드로 하겠습니다. 자식이 둘일 때 코드를 보면 먼저 replace가 삭제 노드의 왼쪽 서브 트리를 가리키게 합니다. 그리고 아직 구현하지는 않았지만 max 메서드를 사용하여 가장 큰 노드를 찾습니다. 그 후 cur와 replace의 키 값을 교환합니다.