이진 탐색 트리 에서는 데이터를 삽입할 때에 비해 여러가지 상황을 고려해야한다.

• 삭제하려는 데이터를 갖는 Node 를 먼저 찾아야함

만약 7을 삭제해야 한다고 가정하자

그러면 이 7 의 데이터를 가지고 있는 Node 를 찾아야 한다.

이 경우에서는 탐색 연산을 이용하여 찾으면 된다.

삭제하고 싶은 Node 를 이미 찾았다고 가정하자.

그러면 이제 몇 가지 경우가 있다.

이번 장에서는 간단한 2가지 경우에 대해서 알아보자.

조금 더 복잡한 경우는 다음 장에서 설명하겠다.

경우1 ) 삭제하려는 데이터가 Leaf Node 의 데이터일 때

예를 들어 아래 이진 탐색 트리 에서 7을 지울 때 같은 경우이다.

이때는 그냥 부모 6의 오른쪽 자식 레퍼런스를 None 으로 지정해 준다.

만약 4 를 지우고 싶으면 6 의 왼쪽 자식 레퍼런스를 None 으로 지정하면 된다.

경우2 ) 삭제하려는 데이터 Node 가 하나의 자식 Node 만 있을 때

예를 들어 Node 10 을 삭제하려는 경우이다.

이때는 자식 Node 가 부모 Node 의 자리를 차지하면 된다.

그러니까 그냥 여기서 14 를 8의 오른쪽 자식으로 지정하면 된다.

각 Node 는 부모 Node 에 대한 레퍼런스도 저장하니까 14의 부모 Node 도 8로 지정해 준다.