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

선택한 노드의 키 값과 삽입할 키 값이 같은 경우( 3 )

값을 삽입할 수 없습니다. 삽입할 수 없다는 내용을 출력합니다.

삽입할 키 값이 선택한 노드의 키 값보다 작은 경우( 4 )
선택한 노드에 왼쪽 자식 노드를 대입합니다. 실제로는 Add 함수에 왼쪽 자식 노드를 전달하

며 재귀 호출합니다.

삽입할 키 값이 선택한 노드의 키 값보다 큰 경우( 5 )

선택한 노드에 오른쪽 자식 노드를 대입합니다. 실제로는 Add 함수에 오른쪽 자식 노드를 전
달하며 재귀 호출합니다.

노드를 삭제하는 Remove 함수

노드를 삭제하는 과정은 삽입하는 과정보다 복잡합니다. 노드를 삭제할 때는 ‘세 가지 서로
다른 상황’에 놓이기 때문입니다. 따라서 각각의 상황에 맞게 알맞은 처리를 해야 합니다.

자식 노드가 없는 노드를 삭제하는 경우( a , b )
그림 10-14의 a 는 자식 노드가 없는 노드 3을 삭제하는 경우입니다. 이런 경우에는 노드 3
을 가리키는 부모 노드 4의 왼쪽 포인터를 널로 업데이트하면 됩니다. 이렇게 하면 노드 3은
아무것도 가리키지 않기 때문에 이진검색트리에서 삭제됩니다. b 도 마찬가지입니다. 삭제

할 노드를 트리에서 떼어내면 삭제 과정이 끝납니다.

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

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

부모의 왼쪽 포인터에 NULL을 대입합니다. 부모의 오른쪽 포인터에 NULL을 대입합니다.

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

[그림 10-14] 자식 노드가 없는 노드를 삭제하는 과정
418 C 알고리즘