BST 삭제 후에는 네 검증을 같은 루프로 확인한다
삭제 코드가 값을 반환했다면, 링크·후속자·중위 순회·높이 위험이 모두 같은 테스트 입력에서 맞아야 한다.
| 검증 | 통과 조건 | 대표 실패 |
|---|---|---|
| 부모 링크 | 반환 노드가 left/right/root에 다시 연결된다. | root 삭제 후 예전 root가 남음 |
| 후속자 제거 | 값을 복사한 원래 successor 노드를 삭제한다. | 중위 순회에 중복 값 |
| 중위 순회 | 오름차순이며 삭제 키가 없다. | 순서 깨짐 또는 삭제 키 재등장 |
| 높이 위험 | 정렬 입력에서 H가 N에 가까워지는지 추적한다. | 탐색·삭제가 O(N)에 가까워짐 |
핵심: 삭제 검증은 “검색 실패” 하나로 끝나지 않고 링크 반환과 중위 순서를 함께 봐야 한다.