BST의 3가지 연산 中 삭제 - sihyun10/data_structures_docker GitHub Wiki
노드의 삭제 후에도 트리의 구성을 유지해야하기에
이진 탐색 트리(BST)에서의 삭제 연산은 3가지 경우로 나뉜다.
- 삭제할 노드가 자식이 없는 경우 (Leaf Node)
1-1. 단순히 그 노드를 트리에서 제거. 부모 노드의 해당 자식 포인터를NULL로 설정 - 삭제할 노드가 하나의 자식만 있는 경우 - 왼쪽 자식만 or 오른쪽 자식만
2-1. 그 자식 노드를 부모 노드가 가리키게 함
2-2. 삭제할 노드의 부모가 그 노드의 자식 노드를 가리키게 됨 - 삭제할 노드가 두 개의 자식을 가지고 있는 경우
3-1. 후속 노드(successor) or 선행 노드(predecessor)를 사용해 노드를 삭제함
3-2. 후속 노드 : 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값(왼쪽)을 가지는 노드
3-3. 선행 노드 : 왼쪽 서브트리에서 가장 큰 값(오른쪽)을 가지는 노드
1 ~ 2번은 잘 이해가 되지만, 3번은 이해가 잘 안간다.
그러므로 예제로 들어서 봐보자.
10
/ \
5 15
/ \ / \
3 7 12 20
이 트리에서 "노드 5"를 삭제해보자.
먼저, 후속 노드를 찾자.
- 5를 삭제할 노드는 자식이 2개 있음. 이때 5의 오른쪽 자식(7)이 있음
- 7은 왼쪽 서브트리가 없고, 더 이상 작은 값이 없으므로 7이 바로 후속 노드가 됨
- 후속 노드인 7을 삭제할 노드인 5의 자리로 이동 (=복사)
// 결과
10
/ \
7 15
/ / \
3 12 20
- 그 후에 후속 노드인 7을 삭제함
5의 자리에 7을 복사한다. 그러면 트리의 5의 자리에 7이 들어가게 된다.
이제 원래 7이 있었던 자리는 필요 없으므로, 그 자리에 있던 7을 삭제한다.
(즉 후속 노드가 트리에서 중복되지 않도록 하기 위해서)
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* left;
struct Node* right;
} Node;
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
//오른쪽 서브트리에서 가장 작은 값 (후속 노드 찾는 함수)
Node* findMin(Node* node) {
while (node && node->left != NULL) {
node = node->left;
}
return node;
}
Node* deleteNode(Node* root, int value) {
if (root == NULL) {
return root;
}
if (value < root->value) {
root->left = deleteNode(root->left, value);
} else if (value > root->value) {
root->right = deleteNode(root->right, value);
} else {
//삭제할 노드를 찾은 경우다!
// 1. 삭제할 노드가 자식이 없는 경우
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
}
// 2. 삭제할 노드가 하나의 자식만 있는 경우
else if (root->left == NULL) {
Node* temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL) {
Node* temp = root;
root = root->left;
free(temp);
}
// 3.삭제할 노드가 두 개의 자식을 가지고 있는 경우
else {
Node* temp = findMin(root->right);
root->value = temp->value; //후속 노드 값을 현재 노드에 복사
root->right = deleteNode(root->right, temp->value);
}
}
return root;
}int main() {
Node* root = createNode(10);
root->left = createNode(5);
root->right = createNode(15);
root->left->left = createNode(3);
root->left->right = createNode(7);
root->right->left = createNode(12);
root->right->right = createNode(20); 10
/ \
5 15
/ \ / \
3 7 12 20
위와 같은 트리가 만들어진다.
그럼 이제 3가지 경우로 삭제해보자!
Node* findMin(Node* node) {
while (node && node->left != NULL) {
node = node->left;
}
return node;
}
// 3.삭제할 노드가 두 개의 자식을 가지고 있는 경우
else {
Node* temp = findMin(root->right);
root->value = temp->value; //후속 노드 값을 현재 노드에 복사
root->right = deleteNode(root->right, tmep->value); //후속 노드 있었던 위치에서 해당 값 다시 재귀적으로 삭제
} root = deleteNode(root, 5); //5를 삭제- 오른쪽 서브트리에서 가장 작은 값(후속노드 = 7)을 찾는다
- 그 값을 현재 노드의 값으로 대체하고, 후속 노드 삭제한다
10
/ \
7 15
/ / \
3 12 20
// 1. 삭제할 노드가 자식이 없는 경우
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
}- 단순히 노드를 삭제하고 NULL로 설정해주면 된다.
root = deleteNode(root, 3); 10
/ \
7 15
/ \
12 20
12를 삭제했다는 가정 하에 아래 그림과 같다.
10
/ \
7 15
\
20
그 자식 노드를 삭제할 노드의 위치로 끌어올리는 방식으로 처리된다
else if (root->left == NULL) {
Node* temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL) {
Node* temp = root;
root = root->left;
free(temp);
} root = deleteNode(root, 15);- 현재 경우는 root->left == NULL 인경우
- 현재 삭제하려는 노드(root)를 임시 포인터 temp에 저장한다
- 왜 저장하냐? root를 다른 노드로 바꿀꺼라서 기존 노드를 free()로 삭제하려면 잠깐 저장해둬야한다
- root = root->right; (현재 노드인 root삭제하고, 그 자리에 오른쪽 자식이 대신 오게끔)
- root->20를 가리키게 된다
- free(temp); 아까 임시로 저장해뒀던 삭제할 노드를 메모리에서 해제(제거)
- 15를 메모리에서 해제
- 현재 삭제하려는 노드(root)를 임시 포인터 temp에 저장한다
//최종 결과
10
/ \
7 20