첫 번째 단계는 삭제할 노드를 찾는 것입니다. 그 후에는 다음과 같은 세 가지 경우를 따져봐야 합니다.

여기서 후속 노드란 현재 노드 다음으로 큰 숫자를 가진 노드를 말합니다. 즉, 현재 원소보다 큰 원소들 중에서 가장 작은 원소를 의미합니다. 따라서 현재 노드의 오른쪽 서브 트리로 이동한 후, 여기서 가장 작은 값의 노드를 찾으면 됩니다. 가장 작은 노드를 찾으려면 서브 트리에서 가장 왼쪽에 위치한 노드로 이동하면 됩니다. 그림 2-7에 나타난 트리에서 12의 오른쪽 서브 트리는 18 아래 부분의 트리입니다. 그러므로 여기부터 시작해서 왼쪽 자식 노드로 이동하면 15가 나타납니다. 15 위치의 노드는 왼쪽 자식이 없고, 오른쪽 자식 노드는 16을 가지고 있으므로 15보다 큽니다. 그러므로 12의 후속은 15가 됩니다.

12를 15로 교체하려면, 먼저 12를 지우고 후속 노드의 값으로 덮어씁니다. 이 과정을 그림 2-8에 나타냈습니다.

▲ 그림 2-8 후속 노드 값을 루트 노드에 복사