BST 불변식

삽입과 삭제 뒤 중위 순회로 불변식 확인

BST의 연산은 왼쪽, 현재, 오른쪽 순서가 항상 오름차순인지로 검증할 수 있다.

0 child

리프 삭제

부모 연결에서 대상 노드를 제거하고 끝낸다.

1 child

자식 승격

남은 자식을 대상 위치로 올려 순서 범위를 유지한다.

2 child

후속자 치환

오른쪽 최소값으로 바꾸고 원래 후속자 노드를 삭제한다.

검증 루틴

연산 수행

삽입, 탐색, 삭제 이후 같은 기준으로 트리를 다시 읽는다.

중위 확인

결과 배열이 오름차순이고 중복 정책과 맞으면 구조가 유지된 것이다.