자식 노드를 두 개 가지고 있는 노드를 삭제하는 경우에도 삭제 노드 자리를 자식 노드에게 물려주는 후처리 작업을 해야 한다. 그런데 누구에게 물려줘야 할까? 이 경우에는 직계 자식 노드뿐만 아니라 전체 자손 노드 중에서 후계자를 찾는다. 노드가 삭제되고 자손 노드에게 자리를 물려준 후에도 이진 탐색 트리가 유지되어야 한다. 그러려면 이진 탐색 트리의 정의를 만족해야 하므로 후계자로 선택한 자손 노드의 키값은 왼쪽 서브 트리에 있는 노드들의 키값보다 커야 하고, 오른쪽 서브 트리에 있는 노드들의 키값보다는 작아야 한다. 그러므로 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 자손 노드를 후계자로 선택하거나, 오른쪽 서브 트리에서 가장 작은 자손 노드를 후계자로 선택해야 한다.

이진 탐색 트리의 정의를 생각해 봤을 때 왼쪽 서브 트리에서 가장 큰 키값의 노드를 탐색하는 작업은 왼쪽 서브 트리의 오른쪽 링크를 따라 계속 이동하여 오른쪽 링크 필드가 NULL인 노드, 즉 가장 오른쪽에 있는 노드를 찾는 작업이 된다. 그리고 오른쪽 서브 트리에서 가장 작은 키값의 노드를 탐색하는 작업은 오른쪽 서브 트리에서 왼쪽 링크를 따라 계속 이동하여 왼쪽 링크 필드가 NULL인 노드, 즉 가장 왼쪽에 있는 노드를 찾는 작업이 된다

예를 들어 [ 그림 7-42 ]에서 노드 8을 삭제할 경우에 후계자로 선택할 수 있는 자손 노드는 왼쪽 서브 트리에서 가장 오른쪽에 있는 노드 5와 오른쪽 서브 트리에서 가장 왼쪽에 있는 노드 10이 된다.

선택된 후계자 노드가 삭제된 조상 노드 자리로 올라가면 후계자 노드가 있던 자리는 공백이 되어 후계자의 자식 노드는 고아가 된다. 따라서 후계자 자식들이 고아가 되지 않도록 후계자가 있었던 자리에 자식 노드를 이동시켜 연결하는 2차 후속 처리 작업을 해야 한다. 이러한 재구성 작업은 자식 노드가 하나인 노드의 삭제 연산 후에 수행되는 [ 그림 7-39 ] 의 재구성 작업과 같다. [ 그림 7-42 ]에서 (c)-1은 자식 노드가 하나 있는 노드 5를 후계자로 선택한 경우로. ③ 노드 5를 후계자로 선택하여 노드 8의 자리로 보내고, ④ 후계자 노드 5의 원래 자리는 하나뿐인 자식 노드 4에게 물려주어 이진 탐색 트리를 재구성한다. (c)-2는 자식 노드가 한 개 있는 노드 10을 후계자로 선택한 경우로 ③ 노드 10을 후계자로 선택하여 노드 8의 자리로 보내고, ④ 후계자 노드 10의 원래 자리는 역시 하나뿐인 자식 노드 14에 물려주어 이진 탐색 트리를 재구성한다.

왼쪽 서브 트리에서 키값이 가장 큰 원소를 후계자로 선택하기로 하고, 삭제 연산에 대한 전체 알고리즘을 정의하면 [ 알고리즘 7-6 ] 과 같다.