삽입
비교하며 한 경로만 내려가 빈 자리에 새 노드를 둔다.
BST는 모든 노드에서 왼쪽 < 현재 < 오른쪽을 지킨다
삽입, 탐색, 삭제는 모두 같은 순서 약속을 유지하는 작업입니다. 삭제가 어려운 이유도 노드를 지운 뒤 이 약속을 다시 맞춰야 하기 때문입니다.
8
3
10
1
6
14
왼쪽 서브트리
루트 8보다 작은 값만 온다.
8
오른쪽 서브트리
루트 8보다 큰 값만 온다.
탐색
작으면 왼쪽, 크면 오른쪽으로 이동해 후보 절반을 버린다.
삭제
자식 수를 세고 0/1/2자식 규칙으로 다시 연결한다.
검증
중위 순회가 정렬되고 삭제 키가 사라졌는지 확인한다.
핵심: BST 구현의 정답 여부는 “트리 그림이 그럴듯한가”가 아니라 모든 노드의 범위 약속과 중위 순회 정렬성이 유지되는가로 판단합니다.