Page 419 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

이 과정을 간단히 정리하면 다음과 같습니다.

• 삭제할 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터를 NULL로 합니다.
• 삭제할 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터를 NULL로 합니다.

이 작업이 끝난 다음에 삭제 대상인 노드 객체의 메모리 영역을 해제하면 됩니다. 만일 이런

순서로 삭제를 진행하지 않고 삭제할 노드의 메모리를 먼저 해제하면 부모는 해제한 메모리
의 주소를 가리킵니다. 이렇게 되면 프로그램에 치명적인 오류가 발생할 수 있습니다.

자식 노드가 1개인 노드를 삭제하는 경우( a , b )
그림 10-15의 a 는 자식 노드를 1개만 갖는 노드인 7을 삭제하는 경우입니다. 이런 경우에
는 원래 노드 7의 위치로 노드 8을 가져와야 삭제할 수 있습니다. 이런 과정을 거치면 ‘자식
노드 8을 루트로 하는 서브 트리의 모든 키 값은 부모 노드인 6보다 커야 한다’라는 조건을

유지할 수 있습니다. 삭제 노드의 부모 노드인 6의 오른쪽 포인터가 삭제 대상 노드인 7의 자
식 노드 8을 가리키도록 업데이트하면 됩니다. 그러면 7은 아무것도 가리키지 않기 때문에
이진검색트리에서 삭제됩니다.

a 7을 삭제하는 경우 b 1을 삭제하는 경우
검색과 마찬가지로 7을 찾아갑니다. 그런 다 검색과 마찬가지로 1을 찾아갑니다. 그런 다
음 삭제할 노드 7에서 멈춥니다. 음 삭제할 노드 1에서 멈춥니다.

6 6
2 7 2 7
1 4 8 1 4 8
3 5 9 0 3 5 9

부모 노드인 6의 오른쪽 포인터가 7의 자식 부모 노드인 2의 왼쪽 포인터가 1의 자식
노드인 8을 가리키도록 업데이트합니다. 노드인 0을 가리키도록 업데이트합니다.

6 6
7
2 8 1 2 7
1 4 9 0 4 8
3 5 3 5 9

[그림 10-15] 자식 노드가 1개인 노드를 삭제하는 과정

10•트리 419