BST 삭제 구현은 케이스 처리와 검증 루틴을 같이 통과해야 한다
삭제 코드는 실행만 된다고 맞는 것이 아닙니다. 부모 링크, 후속자 제거, 중위 순회, 삭제 키 탐색 실패까지 함께 확인해야 합니다.
자식 수별 코드 분기
0 child
리프라면 부모 링크를 null로 바꾼다.
1 child
유일한 자식을 삭제 노드의 자리로 반환한다.
2 child
후속자 값으로 대체하고 원래 후속자 노드를 제거한다.
검증 루틴
중위 순회
결과가 오름차순인지 확인한다.
PASS
삭제 키 탐색
삭제한 값이 다시 발견되면 실패다.
반례 감지
중복 값
2자식 치환 후 후속자가 남아 있지 않은지 본다.
PASS
높이
정렬 입력에서 H가 N에 가까워지는지 측정한다.
주의
A급 기준: 삭제 분기, 반환 링크, 중위 순회 검증을 한 묶음으로 보면 “값만 바꿨는데 후속자가 남는” 버그를 바로 잡아낼 수 있습니다.