BST 탐색 방향
균형이 좋으면 O(log N), 한쪽으로 치우치면 O(N)이 됩니다.
BST 중위 순회 불변식
삽입, 탐색, 삭제, 후속자, 중위 순회는 모두 left subtree < node < right subtree 규칙을 기준으로 움직입니다.
BST 삽입 위치
중복 값을 허용할지 한쪽으로 보낼지 정책이 필요합니다.
BST 삭제 분기
포인터 교체 후 부모 링크가 맞는지 살핍니다.
BST 삭제 후속자 선택
원래 후속자 노드를 다시 삭제하는 두 단계가 됩니다.
중위 순회
삭제 후 순회 결과가 오름차순이면 불변식이 유지된 것입니다.
높이 H
연산 비용은 노드 수보다 트리 높이에 직접 영향을 받습니다.
반례
후속자 값을 복사한 뒤 원래 노드를 남기면 중복 값이 생깁니다.