left < node < right
모든 노드에서 왼쪽 값은 작고 오른쪽 값은 커야 합니다.
BST는 불변식, 삭제 분기, 높이 위험을 함께 관리한다
삽입과 탐색은 비교 경로를 따라가면 되지만, 삭제와 성능 판단은 별도 검증 기준을 붙여야 안정적인 구현이 됩니다.
0/1/2자식 분기
자식 수에 따라 null 반환, 자식 승격, 후속자 치환으로 나눕니다.
H가 비용을 결정
편향되면 평균 기대와 달리 탐색·삽입·삭제가 O(N)에 가까워집니다.
요구
BST로 충분한 경우
대안을 봐야 하는 경우
조회
정렬 순서와 predecessor/successor가 필요하다.
존재 여부만 빠르게 보면 hash가 더 단순하다.
삭제
0/1/2자식 테스트와 중위 순회 검증을 갖췄다.
후속자 중복, root 반환 누락 반례를 통과하지 못한다.
성능
입력이 충분히 섞여 있고 데이터 규모가 작다.
정렬 입력이나 장기 운용이면 균형 BST를 검토한다.
정리: BST를 안전하게 쓰려면 비교 규칙을 고정하고, 삭제 뒤에는 중위 순회와 삭제 키 탐색 실패를 확인하며, 편향 입력에서는 균형 구조를 고려해야 합니다.