2. Binary Search Tree 만들기 - 삭제

아래 글을 이어서 진행해보자.

designatedroom87.tistory.com/14?category=869957

1. Binary Search Tree 만들기 - 삽입과 탐색

 

이진 탐색 트리의 삭제

먼저 노드를 삭제하기 위해서는 먼저 노드를 탐색하여야 한다는 것은 삽입과 마찬가지이다.

우리가 삭제하려고 하는 키값이 트리 안에 어디 있는지를 알아야 삭제할 수 있다.

노드를 탐색하였으면, 아래의 3가지 경우를 고려하여야 한다.

 

1. 삭제하려는 노드가 단말 노드일 경우

2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우

3. 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우

​

먼저, 이진 탐색 트리부터 보자.

[그림1 ]

첫 번째 경우 : 삭제하려는 노드가 단말 노드일 경우​ 

단말노드 아래에 더 이상의 노드가 없으므로, 단말노드만 지우면 된다.

단말노드를 지운다는 것은 단말노드의 부모노드를 찾아서

부모노드안의 링크필드를 NULL로 만들어서 연결을 끊으면 된다.

다음으로 만약 노드를 동적으로 생성하였다면 이 단말노드를 동적메모리 해제시키면 된다.

위의 그림에서 30을 지우려고 하는 경우를 생각해보자.

30의 부모 노드와 30을 찾는다.

그리고, 부모 노드 안의 링크 필드를 NULL로 만들어서 연결을 끊는다.

그리고 동적할당을 해제한다.

아래의 그림이 된다.

그러면, 30이 들어있는 노드는 삭제가 된다.

 

두 번째 경우 :  삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리중 하나만

                    가지고 있는 경우

 

삭제되는 노드가 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우에는

자기 노드는 삭제하고 서브 트리는 자기 노드의 부모 노드에 붙여주면 된다.

[그림 1]에서 68을 제거하려는 경우로 보면 된다.

[삭제 전]

[삭제 후]

 

세 번째 경우 :  삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우

[그림 1]에서 18을 삭제하려고 가정해보자.

18을 삭제하고 자식 노드인 7이나 26을 그대로 연결하면

이진 탐색 트리의 조건이 만족되지 않는다.

그러면 어떤 노드를 가져와야만 다른 노드들을 변경시키지 않고,

이진 탐색 트리의 조건을 만족시킬지 생각하여야 한다.

이진 탐색 트리에서도 삭제되는 노드와 가장 값이 비슷한 노드를 선택하여야 한다.

그래야만 다른 노드를 이동시키지 않아도 이진 탐색 트리가 그대로 유지된다.

그러면 삭제할 노드의 값과 가장 가까운 노드는 어디에 있을까?

삭제할 노드의 왼쪽 서브 트리에서 가장 큰 값이나 오른쪽 서브 트리에서 가장 작은 값이

삭제할 노드와 가장 가깝다는 것을 알 수 있다.

왼쪽 서브 트리에서 가장 큰 값은 왼쪽 서브 트리의 가장 오른쪽에 있는 노드이며,

오른쪽 서브 트리에서 가장 작은 값은 오른쪽 서브 트리의 가장 왼쪽에 있는 노드가 된다.

또한, 이들 노드는 이진 탐색 트리를 중위순회하였을 경우, 각 각 후속 노드와 선행 노드에 해당한다.

위에서 삭제 노드가 18이라고 하였을 때, 후계자가 될 수 있는 대상 노드는 아래의 그림과 같이

12와 22가 된다.

위의 그림에서 보다시피, 12는 왼쪽 서브 트리에서 가장 큰 값이며,

22는 오른쪽 서브 트리에서 가장 가장 작은 값이다.

이들 두 개의 노드 중에서 어떤 노드를 선택할지는 알아서 하면 된다.

우리가 구현할 것에서는 오른쪽 서브 트리에서 가장 작은 값을 선택하자.

( 오른쪽 서브 트리에서 가장 작은 값인 22를 후계자로 정하자. )

그러면, 오른쪽 서브 트리에서 가장 작은 값을 가진 노드는 어떻게 찾을까?

삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 갖는 노드는

오른쪽 서브 트리에서 왼쪽 자식 링크를 타고 NULL을 만날 때까지 계속 진행하면 된다.

아래의 그림을 보자.

최종적으로 아래의 그림처럼 22가 후계자가 되고, 22가 18 자리로 이동하게 된다.

그리고 마지막 그림이 아래의 그림

 

아래는 이진 탐색 트리의 삭제 함수의 구현

 

그리고 아래는 메인 함수

 

아래는 프로그램 실행 결과

 

아래는 헤더 파일과 소스 파일

BinarySearchTree.c

0.00MB

BinarySearchTree.h

0.00MB

BinaryTree.c

0.00MB

BinaryTree.h

0.00MB

common.h

0.00MB

main.c

0.00MB