BST에서 원소 삭제하기

이번에는 BST에서 원소를 삭제하는 방법에 대해 알아보겠습니다. 삭제 과정을 설명하기 위해 그림 2-7의 BST를 사용하겠습니다.

▲ 그림 2-7 루트 노드가 12인 이진 검색 트리

그림 2-7 트리에서 루트 노드 12를 삭제하려고 합니다. BST에서 원소를 삭제하는 작업은 단순히 노드를 삭제하는 것으로 끝나는 것이 아니라, 노드 삭제 후 전체 트리가 BST 속성을 만족하도록 다른 적절한 노드로 삭제된 노드를 대체해야 하기 때문에 삽입보다 좀 더 복잡합니다.