6을 가진 노드를 삭제하려면 왼쪽 서브 트리의 가장 큰 데이터인 5를 가진 노드나 오른쪽 서브 트리에서 가장 작은 데이터인 8을 가진 노드로 대체해야 이진 탐색 트리를 유지할 수 있습니다.

코드 14-5를 보면 왼쪽 서브 트리에서 데이터가 가장 큰 노드를 찾습니다(#4). 우선 왼쪽 서브 트리의 루트 노드를 relpace에 할당한 후 오른쪽 자식 노드로 계속 내려오면 가장 큰 데이터를 가진 노드를 만날 수 있습니다. 이 노드는 왼쪽 자식 노드는 가질 수 있어도 오른쪽 자식 노드를 가질 수는 없습니다. 오른쪽 자식 노드가 있다면 자식 노드가 해당 노드보다 큰 데이터를 가질 테니까요.

대체 노드를 찾았으면 삭제 노드와 데이터를 교환합니다(#5). 실제 노드를 교체하지 않고 데이터만 교환해도 노드를 교체한 것과 같아집니다.

마지막으로 대체 노드를 이진 탐색 트리에서 삭제합니다(#6). 대체 노드는 삭제 노드의 왼쪽 서브 트리에 있으므로 인자로 cur.left를 전달해 __remove_recursion() 메서드를 호출합니다.