BST 연산은 실행 후 순회와 탐색 결과로 되검산한다
삽입·삭제 후 반환 노드만 믿지 말고, 중위 순회와 search 결과가 같은 입력에서 맞는지 본다.
| 연산 | 순회 검증 | 탐색 검증 | 성능 신호 |
|---|---|---|---|
| insert x | inorder가 정렬 상태 | search(x) = true | 높이 증가 위치 확인 |
| delete x | 정렬 + 중복 없음 | search(x) = false | 후속자 중복 제거 확인 |
| search x | 순회는 변하지 않음 | 존재 여부와 일치 | H가 커지면 비용 증가 |
| 실패 예 | [1,4,4,6,7] | 삭제 키가 다시 발견 | 정렬 입력에서 H≈N |
핵심: BST 연산 검증은 “중위 순회 정렬”과 “search 결과”가 동시에 맞아야 통과다.