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

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

•삭제 대상 노드가 부모 노드의 왼쪽 자식인 경우
부모의 왼쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 합니다.
•삭제 대상 노드가 부모 노드의 오른쪽 자식인 경우
부모의 오른쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 합니다.

자식 노드가 2개인 노드를 삭제하는 경우( a )
자식 노드가 2개인 노드를 삭제하는 과정은 앞의 두 과정보다 더 복잡합니다. 그림 10-16은

노드 5를 삭제하는 경우입니다. 노드 5의 왼쪽 서브 트리(노드 1이 루트)의 노드 가운데 키 값이
가장 큰 노드 4를 노드 5가 있는 곳으로 옮겨 삭제해야 합니다.

a 5를 삭제하는 경우

9 5의 왼쪽 서브 트리에서 가장 큰 키 값을 갖는
노드를 검색합니다. 현재는 4가 가장 큰 값을
5 10
가지는 노드이므로 여기에서 멈춥니다.
1 7 11
2 4 6 8 12
3
9 5가 있는 곳으로 4를 옮기면 삭제 과정이 끝납
5 10 니다. 4를 옮기려면 먼저 4의 데이터를 5의 위
치로 복사합니다.
1 7 11
2 4 6 8 12
3
9 그런 다음 원래의 4를 트리에서 떼어내면 됩
니다.
4 10
1 7 11
2 3 6 8 12
4

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

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

420 C 알고리즘