find target
삭제할 키를 BST 탐색으로 찾습니다.
Algo · BST
BST 삭제 3분기 시각화
삭제할 노드의 자식 수에 따라 링크 재연결 방식과 후계자 선택이 달라집니다.
삭제 케이스 판단
treeleaf case
자식이 없으면 부모의 링크만 끊습니다.
one child
유일한 자식이 삭제 노드 자리를 대신합니다.
successor
오른쪽 서브트리의 최소값을 찾습니다.
relink
후계자 이동 후 모든 부모 링크를 정리합니다.
search
→
count children
→
leaf/one/two
→
successor
→
relink
BST 삭제 3분기 시각화 정리
BST 삭제의 핵심은 값을 지우는 순간보다 삭제 후에도 탐색 순서 불변식이 깨지지 않게 링크를 다시 잇는 것입니다.