실행 결과를 보면 루트 노드 6은 지워졌고 그 자리를 5 노드가 채웠습니다. 이렇게 되면 이진 탐색 트리의 특징이 잘 유지됩니다. 어떻게 된 일일까요?

기본적인 실행은 이전 두 경우와 같으므로 중요한 부분의 코드만 설명하겠습니다. 삭제 노드의 자식 노드가 두 개일 때는 삭제 노드를 직접 지우지 않고 삭제 노드를 대체할 노드를 찾은 다음 대체 노드와 삭제 노드의 데이터를 교체합니다. 교체한 다음 대체 노드(리프 노드 혹은 자식이 하나인 노드)를 지우면 대상 데이터를 가진 노드를 삭제한 것과 같습니다. 이때 어떤 노드를 대체 노드로 할지가 매우 중요해집니다. 삭제 노드와 대체 노드의 데이터를 교환한 다음에도 이진 탐색 트리를 유지해야 하기 때문입니다.

노드를 교환한 다음에도 이진 탐색 트리를 유지하려면 두 가지 방법 중 하나를 선택해야 합니다.

1| 대체 노드를 삭제 노드의 왼쪽 서브 트리에서 가장 큰 데이터를 가지는 노드로 한다.

2| 대체 노드를 삭제 노드의 오른쪽 서브 트리에서 가장 작은 데이터를 가지는 노드로 한다.

예를 들어 그림 14-18의 트리에서 6을 가진 노드를 삭제하는 경우를 생각해 봅시다.

그림 14-18 대체 노드의 두 가지 경우