BST 삭제는 자식 수로 분기하고, 두 자식이면 후속자를 옮긴다
삭제 노드의 자식 수가 0/1/2인지 먼저 세고, 2자식 삭제에서는 오른쪽 서브트리의 최소값으로 자리를 채운다.
8
3 삭제
10
14
1
6
4 후속자
7
| 자식 수 | 처리 | 검증 |
|---|---|---|
| 0 child | 부모 링크를 null로 바꾼다. | 삭제 키가 search에서 실패한다. |
| 1 child | 유일한 자식을 삭제 노드 자리로 올린다. | 부모가 새 자식을 가리킨다. |
| 2 children | 후속자 값을 복사하고, 원래 후속자 노드를 다시 삭제한다. | 중위 순회가 오름차순이고 중복이 없다. |
| root | 반환 노드를 root에 다시 대입한다. | 루트 삭제 후에도 전체 트리가 남는다. |
핵심: 값을 복사한 뒤 원래 후속자 노드까지 삭제해야 중위 순서에 중복 값이 남지 않는다.