CH11-2 이진탐색트리(6)

11-2. 이진 탐색 트리 ⑥

이번에는… case3을 실제 코드레벨에서 구현해보자.

case3에서 핵심은 삭제되어야 하는 노드의 오른쪽 서브트리에서 가장 작은 값으로 삭제되어야 하는 노드를 대체한다는 것이다.

이때 코드레벨에서는 대체가 대입으로 이루어진다.

그리고 그 빈자리는 대체하는 노드의 항상 오른쪽 자식노드가 채운다.

이때 중요한건, 이 ‘채움’이란게, 사실은 원래 삭제된 노드의 자식으로 연결된다는 것임..

이제 위 코드를 분석해보자.

단계 1은 삭제 대상의 대체노드를 계속 찾는다. 이때 부모노드의 주소를 유지하기 위해서 포인터를 두개 사용한다! 하나는 내려가며 탐색하는 노드의 주소, 그리고 하나는 그 노드의 부모노드의 주소이다. 부모노드의 주소를 계속 기억하고 있다는게 중요하다. 나중에 연결할때 필요하다.

저 while문을 나왔다는건, mNode의 왼쪽 자식이 NULL, 즉 mNode는 오른쪽 서브트리에서 가장 작은 말단노드라는 것임. (이때 mNode의 오른쪽 자식이 있을 수도 있다.)

이때 mpNode가 mNode의 부모의 주소값을 가지고 있다.

이러고 while문을 나오면… 다음 스텝은 대입이다.

삭제할 노드에 mNode의 값을 새로 대입한다