Minwoo Dev.
[자료구조] 이진 탐색 트리(Binary Search Tree) 본문
728x90
반응형
SMALL
이진 탐색 트리(Binary Search Tree)
- 한 노드를 기준으로 왼쪽 자식에 있는 트리는 해당 노드보다 작다
- 한 노드를 기준으로 오른쪽 자식에 있는 트리는 해당 노드보다 크다
위 그림처럼, 모든 각 노드들에 대하여 왼쪽은 더 작은 값이, 오른쪽은 더 큰 값이 위치해야한다.
위와 같은 이진탐색트리를 코드로 구현해보겠다.
구현할 기능은 아래와 같다.
- 이진탐색트리에서 가장 작은 값
- 이진탐색트리에서 가장 큰 값
- 이진탐색트리에서 주어진 키 값 찾기
- 이진탐색트리에서 새로운 키 삽입
- 이진탐색트리에서 주어진 키 값 삭제
이진탐색트리에서 가장 작은 값
해당 노드에서 왼쪽 트리가 더 작아야 하므로 왼쪽으로 쭉 내려가면 가장 작은 값이 나온다.
int min_BST(Node *root) {
Node *temp = root;
while(temp->left != NULL) {
temp = temp->left;
}
return temp->data;
}
이진탐색트리에서 가장 큰 값
해당 노드에서 오른쪽 트리가 더 커야하므로 오른쪽으로 쭉 내려가면 가장 큰 값이 나온다.
int max_BST(Node *root) {
Node *temp = root;
while(temp->right != NULL) {
temp = temp->right;
}
return temp->data;
}
주어진 키 찾기
재귀함수를 사용하여 탐색하도록 한다.
Node* search_BST(Node *root, int key) {
if(root == NULL)
return NULL;
if(key == root->data)
return root;
if(key < root->data)
return search_BST(root->left, key);
else
return search_BST(root->right, key);
}
키 값 삽입
가장 위에서부터 새로운 노드와 기존 노드를 비교하여 작으면 왼쪽, 크면 오른쪽으로 이동하여 위치를 찾는다
Node* insert_BST(Node* root, int key) {
Node *parent = NULL;
Node *node = root;
Node *newnode = (Node *)malloc(sizeof(Node));
newnode->data = key;
newnode->left = newnode->right = NULL;
if(node == NULL) {
root = newnode;
return root;
}
while(node != NULL) {
parent = node;
if(key < node->data) {
node = node->left;
} else {
node = node->right;
}
}
if(key < parent->data)
parent->left = newnode;
else
parent->right = newnode;
return root;
}
키 값 삭제
아마 가장 까다로운 부분이 아닐까 싶다.
우선 키 값을 삭제하려고 하는 노드의 종류가 세 가지로 나눠질 것이다.
- 자식이 없는 노드(말단 노드)
- 자식이 하나만 있는 노드
- 자식이 둘 다 있는 노드
자식이 없는 노드(말단 노드) : 자식이 없는 노드는 해당 노드를 그냥 삭제처리한다.
자식이 하나만 있는 노드 : 삭제할 노드의 부모 노드와 자식 노드를 연결시키는 방식으로 처리
자식이 둘 다 있는 노드 : 삭제할 노드와 가장 비슷한 노드를 찾는다. (여기서는 오른쪽 자식의 가장 왼쪽 노드, 삭제하려던 노드보다 아주 조금 더 큰 노드를 찾는것임) , 그리고 비슷한 노드를 삭제할 노드의 위치로 바꾼다.
Node* BST_delete(Node* root, int key) {
Node *curr = root;
Node *parent = NULL;
// 키 값을 찾을 때까지 반복
while (curr != NULL && curr->data != key) {
parent = curr;
if (key < curr->data)
curr = curr->left;
else
curr = curr->right;
}
// 키 값이 발견되지 않음
if (curr == NULL) {
printf("Error: 키 값이 트리에 존재하지 않습니다.\n");
return root;
}
// 경우 1: 삭제할 노드가 단말 노드인 경우
if (curr->left == NULL && curr->right == NULL) {
if (curr != root) {
if (parent->left == curr)
parent->left = NULL;
else
parent->right = NULL;
} else
root = NULL;
free(curr);
}
// 경우 2: 삭제할 노드가 하나의 자식 노드를 가진 경우
else if (curr->left == NULL || curr->right == NULL) {
Node *child;
if (curr->left == NULL)
child = curr->right;
else
child = curr->left;
if (curr != root) {
if (curr == parent->left)
parent->left = child;
else
parent->right = child;
} else
root = child;
free(curr);
}
// 경우 3: 삭제할 노드가 두 개의 자식 노드를 가진 경우
else {
Node *successor = curr->right;
Node *successorParent = curr;
// 오른쪽 서브트리에서 가장 작은 값을 찾음
while (successor->left != NULL) {
successorParent = successor;
successor = successor->left;
}
int k_value = successor->data;
// 후속 노드를 삭제
root = BST_delete(root, successor->data);
// 현재 노드의 값을 후속 노드의 값으로 대체
curr->data = k_value;
}
return root;
}
아마 키 값을 삭제하는 과정이 생각보다 더 어려워 당황할 수 있다. 하지만 이러한 개념을 익혀둔다면 자료구조, 더 나아가 알고리즘 공부를 하는데 많은 도움이 될거라 믿는다.
728x90
반응형
LIST
'자료구조' 카테고리의 다른 글
[자료구조] 최소비용 신장트리(MST), Prim 알고리즘 (0) | 2024.08.20 |
---|---|
[자료구조] 그래프(Graph), 인접 행렬, 인접 리스트 (0) | 2024.08.12 |
[자료구조] 이진트리(연결리스트), 전위순회, 중위순회, 후위순회 - C (0) | 2024.08.10 |
[자료구조] 완전 이진트리 구현 (배열) - C (0) | 2024.08.10 |
[자료구조] 원형 배열 큐를 이용해 전위식 계산하기 - C (0) | 2024.08.08 |