반환 노드를 부모에 다시 연결
재귀 삭제는 `node.left`나 `node.right`에 반환값을 재대입해야 합니다.
BST 삭제는 반환 연결과 중위 순회 검증
삭제 대상의 자식 수를 나눈 뒤에도 부모 링크, 후속자 원본 삭제, 중복 키 정책, 편향 높이를 함께 확인해야 불변식과 성능 위험을 동시에 잡을 수 있습니다.
후속자 값 복사 후 원본 제거
오른쪽 서브트리 최소값을 복사했다면 그 최소 노드를 추가 삭제합니다.
오름차순과 중복 여부 확인
중위 순회 결과가 정렬되어 있고 삭제 키가 사라졌는지 비교합니다.
편향 입력에서 높이 H 측정
정렬 입력 테스트에서 `H`가 `N`에 가까우면 균형 구조를 검토합니다.
루트 삭제
대상: root
검증: 새 root 연결
루트가 바뀌는 케이스는 호출자가 반환값을 받아야 새 루트를 놓치지 않습니다.
리프 삭제
대상: 자식 없음
검증: 탐색 실패
가장 단순한 케이스에서 부모 포인터가 남아 있지 않은지 봅니다.
후속자 삭제
대상: 자식 2개
검증: 중복 제거
값 복사만 하고 원본 후속자를 남기는 실수를 바로 드러냅니다.