경우 3) 삭제하려는 데이터의 Node 가 두개의 자식이 있을 때

만약 아래의 사진에서 2개의 자식이 있는 12 를 지우고 싶다고 하자.

자식이 2개가 있는 Node 를 삭제하려면 다른 Node 가 자리를 메꿔줘야한다.

그 자리에 들어갈 Node 를 어떻게 정하는지 알아보자.

우선 지우려는 Node 의 오른쪽 자식으로 간다.

16 이다.

16 을 root 로 갖는 부분 트리에서 가장 작은 데이터 Node 를 찾는다.

이전에 만든 find_min 메서드의 root 대신 이 Node 16 을 넣는다.

여기서 가장 작은 Node 는 14 이다.

이 Node 가 어떻게 이진 탐색 트리 속성을 어기지 않고, 12 의 위치를 대체할 수 있는지 생각해 보자.

일단 12 의 오른쪽 부분 트리 에 있는 모든 데이터는 왼쪽 부분 트리에 있는 모든 데이터보다 크다.

그렇기 때문에 12 를 14 로 바꿔도 왼쪽 부분 트리 에 있는 데이터들은 14 보다 작을 수 밖에 없다.

이진 탐색 트리 속성을 깨트리지 않는 것이다.

마찬가지로 14 는 12의 오른쪽 부분 트리에서 가장 작은 Node 를 찾은 것이다.

그래서 14 는 12 보다 큰 데이터 중 가장 작은 데이터이다.

즉, 14 가 12 의 위치를 대체해도 오른쪽 부분 트리 에 있는 모든 데이터는 14 보다 크다.

이진 탐색 트리 속성이 유지된다.

이진 탐색 트리 에서는 어떤 Node 보다 큰 모든 Node 중 가장 작은 Node 를 successor 라고 부른다.

(간단하게 생각하면, 어떤 Node 보다 바로 한번만 큰 Node)

(생각해보면 successor 역할을 맡을 수 있는 것은 반대로 root Node 보다 작은 것 중에서 가장 큰 Node 또한 가능할 것 같다??)

(반대 경우 Predecessor 라고 한다)

여기서 14 는 12 보다 큰 데이터 중 가장 작기 때문에 successor 라고 부른다.

이제 지우려는 Node 를 어떻게 successor Node 로 대체할 수 있는지 알아보자.

먼저 successor Node 의 데이터를 지우려는 Node 의 데이터에 저장한다.

Node 자체를 대체하는 것이 아니라 Node 안의 데이터만 대체해 준다.

그 다음에는 successor Node 를 삭제해준다.

이때 지우려는 successor Node 는 왼쪽 자식이 있을 수 없다.

Leaf Node 이거나 오른쪽 자식만 있을 수 있다.

이유는 successor 는 가장 작은 Node 이기 때문이다.

Leaf 나 하나의 자식만 갖고 있는 Node 들의 경우 Node 를 지우는 경우들은 이전에 해보았다.

전에 했던 것과 똑같이 삭제하면 된다.