이진탐색트리(Binary Search Tree)이란?
이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리)
1. 각 노드에 중복되지 않는 키(key)가 있다.
2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.
예를 들어 다음과 같은 트리가 이진탐색트리이다.
이진 탐색 트리의 특징
이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 이러한 효율적인 탐색이 가능한 이유는 탐색 과정에서 자세히 알아보자. 혹시라도 트리에 관한 용어가 헷갈린다면 다음 포스팅을 참고하자.
[자료구조] 트리(Tree)의 개념, 이해, 종류 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진
트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을
code-lab1.tistory.com
이진 탐색 트리 탐색(Search)
이진 탐색 트리의 탐색은 다음과 같은 과정을 거친다.
1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트노드의 키보다 크다면 오른쪽 서브트리로 탐색을 진행한다.
위 과정을 찾고자 하는 값을 찾을 때까지 반복해서 진행한다. 만약 값을 찾지 못한다면 그대로 종료한다.
이러한 탐색 과정을 거치면 최대 트리의 높이(h)만큼의 탐색이 진행되게 된다. 예를 들어보자.
위와 같은 트리에서 키가 5인 노드를 찾고자 한다면, 가장 먼저 루트 노드와의 비교가 이루어진다.
5가 7보다 작으므로 왼쪽 서브 트리로의 탐색이 이루어지고, 이후 5가 3보다 크므로 오른쪽 서브트리로 탐색이 이루어진다. 마지막으로 키가 5인 노드를 찾았으므로 탐색이 종료된다. 즉 트리의 높이인 3번 만큼의 탐색이 이루어졌다. 만약 8을 찾는다면 2번의 연산이 진행되었을 것이다. 즉, 트리 안의 값을 찾는다면 무조건 트리의 높이(h) 이하의 탐색이 이루어지게 된다.
트리 안에 찾고자 하는 값이 없더라도 최대 h 번 만큼만의 탐색이 진행된다. 예를 들어 위 트리에서 6이라는 값을 찾는다고 하면 위 그림과 같은 과정을 거치고 탐색이 종료된다. (직접 위 그림에서 과정을 생각해보자) 마지막으로 탐색하게 되는 5를 키로 갖는 노드에서 6은 5보다 크므로 오른쪽 서브트리로 탐색을 진행해야 하는데 오른쪽 서브 트리가 없으므로 탐색이 종료되는 것이다.
이진 탐색 트리 탐색 소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
TreeNode* search(TreeNode* root, int key){
if(root == NULL){ // 값을 찾지 못한 경우
return NULL;
}
if(key == root->key){ // 값을 찾음
return root;
}
else if(key < root->key){ // 왼쪽 서브트리 탐색
search(root->left, key);
}
else if(key > root->key){ // 오른쪽 서브트리 탐색
search(root->right, key);
}
}
|
cs |
이진 탐색 트리의 탐색을 C언어로 구현하면 재귀를 이용할 수 있다. 재귀가 아닌 for문을 통해서도 구현이 가능하지만 직관적으로 이해가 쉽게 재귀로 구현하였다.
이진 탐색 트리 삽입(insert)
이진 탐색트리의 삽입은 다음과 같은 과정을 거친다. 탐색과 과정이 비슷하다.
1. 삽입할 값을 루트 노드와 비교해 같다면 오류를 발생한다( 중복 값 허용 X )
2. 삽입할 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리를 탐색해서 비어있다면 추가하고, 비어있지 않다면 다시 값을 비교한다.
3. 삽입할 값이 루트노드의 키보다 크다면 오른쪽 서브트리를 탐색해서 비어있다면 추가하고, 비어있지 않다면 다시 값을 비교한다.
예를 들어 아래와 같은 트리에 6을 키로 가진 노드를 추가한다고 하자.
탐색과 비슷하게 삽입하고자 하는 값을 계속해서 비교해서 삽입할 위치를 찾는다.
삽입할 위치가 5의 오른쪽 서브 트리인 것을 찾았으므로, 5의 오른쪽 자식으로 6을 추가하면 된다.
이진 탐색 트리 삽입 소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
void insert(TreeNode** root, int key){
TreeNode* ptr; // 탐색을 진행할 포인터
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); // newNode 생성
newNode->key = key;
newNode->left = newNode->right = NULL;
if(*root == NULL){ // 트리가 비어 있을 경우
*root = newNode;
return;
}
ptr = *root; // root 노드부터 탐색 진행
while(ptr){
if(key == ptr->key){ // 중복값
printf("Error : 중복값은 허용되지 않습니다!\n");
return;
}else if(key < ptr->key){ // 왼쪽 서브트리
if(ptr->left == NULL){ // 비어있다면 추가
ptr->left = newNode;
return;
}else{ // 비어있지 않다면 다시 탐색 진행
ptr= ptr->left;
}
}else{ // key > ptr->key 오른쪽 서브트리
if(ptr->right == NULL){ // 비어있다면 추가
ptr->right = newNode;
return;
}else{ // 비어있지 않다면 다시 탐색 진행
ptr = ptr->right;
}
}
}
}
|
cs |
이진 탐색 트리의 삭제(delete)
이진탐색트리의 삭제는 삽입보다 조금 더 복잡하다. 이진 탐색 트리에서 특정 노드를 삭제할 때 아래와 같은 3가지 상황을 나누어 구현해야 한다.
1. 삭제하려는 노드가 단말 노드(leaf node) 일 경우
2. 삭제하려는 노드의 서브 트리가 하나인 경우(왼쪽 혹은 오른쪽 서브 트리)
3. 삭제하려는 노드의 서브 트리가 두 개인 경우
1. 삭제하려는 노드가 단말 노드(leaf node) 일 경우
자식이 없는 단말 노드의 삭제는 간단하다. 삭제할 노드의 부모 노드가 있다면 부모 노드의 자식 노드를 NULL로 만들고, 삭제할 노드를 삭제(메모리 해제) 해주면 된다.
2. 삭제하려는 노드의 서브 트리가 하나인 경우(왼쪽 혹은 오른쪽 서브 트리)
삭제하려는 노드의 서브 트리가 하나인 경우도 간단하다. 삭제할 노드의 자식노드를 삭제할 노드의 부모노드가 가리키게 하고 해당 노드를 삭제하면 된다.
3. 삭제하려는 노드의 서브트리가 두 개인 경우
삭제하려는 노드의 서브트리가 두 개인 경우는 가장 복잡하다. 이 경우 두 가지 방법을 사용할 수 있다.
1) 삭제할 노드 왼쪽 서브 트리의 가장 큰 자손을 해당 노드의 자리에 올린다.
위와 같이 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 자손을 해당 노드의 자리에 올리면, 이진 탐색 트리의 조건을 만족하면서 트리가 유지되는 것을 확인할 수 있다. 또한 자리를 옮기면서 다른 노드들(4번노드)도 자리가 적절히 이동한 것을 확인 할 수 있다.
2) 삭제할 노드 오른쪽 서브 트리의 가장 작은 자손을 해당 노드의 자리에 올린다.
위와 같이 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 자손을 해당 노드의 자리에 올리면, 이진 탐색 트리의 조건을 만족하면서 트리가 유지되는 것을 확인할 수 있다. 또한 자리를 옮기면서 다른 노드들(10번노드)도 자리가 적절히 이동한 것을 확인 할 수 있다.
이진 탐색 트리의 삭제 소스코드
그림으로 보면 이해가 쉬우나, 직접 구현하려면 헷갈리는 부분이 많을 것이다. 아래 코드를 보며 자세히 이해해 보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
TreeNode* delete_node(TreeNode* root, int key){
TreeNode* del = NULL; // 삭제할 노드
TreeNode* parent = NULL; // 삭제할 노드의 부모 노드
TreeNode* successor = NULL; // 삭제할 노드의 왼쪽 서브트리에서 가장 큰 노드
TreeNode* predecessor = NULL; // successor의 부모노드
TreeNode* child = NULL; // 삭제할 노드의 자식 노드
del= root;
while(del != NULL){ // 삭제할 노드 탐색
if(key == del->key){
break;
}
parent = del;
if(key < del->key){
del = del->left;
}else{
del = del->right;
}
}
if(del == NULL){
printf("Error : 존재하지 않는 키\n");
return root;
}
if(del->left == NULL && del->right == NULL){ // 삭제할 노드의 자식노드가 없는 경우
if(parent != NULL){ // 부모노드가 있는 경우
if(parent->left == del){ // 부모노드의 왼쪽노드가 삭제할 노드일 때
parent->left = NULL;
}else{ // 오른쪽 일 때
parent->right = NULL;
}
}else{ // 부모노드가 없는 경우 = root 노드
root = NULL;
}
}else if(del->left != NULL && del->right != NULL){ // 삭제할 노드의 자식 노드가 2개인 경우
predecessor = del;
successor = del->left;
while(successor->right != NULL){ // 왼쪽 서브트리에서 가장 큰 값 찾기
predecessor = successor;
successor = successor->right;
}
if(predecessor->left == successor){
predecessor->left = successor->left;
}else{
predecessor->right = successor->left;
}
del->key = successor->key;
del = successor;
}else{ // 삭제할 노드의 자식 노드가 1개인 경우
if(del->left != NULL){ // 왼쪽 노드
child = del->left;
}else{ // 오른쪽 노드
child = del->right;
}
if(parent != NULL){ // 부모노드가 있는 경우
if(parent->left == del){ // 부모노드의 왼쪽 노드로 삭제할 노드의 자식노드 연결
parent->left = child;
}else{ // 부모노드의 오른쪽 노드로 삭제할 노드의 자식노드 연결
parent->right = child;
}
}else{
root = child;
}
}
free(del); // 메모리해제
return root;
}
|
cs |
전체 소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
#include <stdio.h>
#include <stdlib.h>
typedef struct _TreeNode{
int key; // key 값
_TreeNode *left; // left child
_TreeNode *right; // right child
}TreeNode;
TreeNode* search(TreeNode* root, int key){
if(root == NULL){ // 값을 찾지 못한 경우
printf("Error : 값을 찾을 수 없습니다\n");
return root;
}
if(key == root->key){ // 값을 찾음
return root;
}
else if(key < root->key){ // 왼쪽 서브트리 탐색
search(root->left, key);
}
else if(key > root->key){ // 오른쪽 서브트리 탐색
search(root->right, key);
}
}
TreeNode* insert(TreeNode* root, int key){
TreeNode* ptr; // 탐색을 진행할 포인터
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); // newNode 생성
newNode->key = key;
newNode->left = newNode->right = NULL;
if(root == NULL){ // 트리가 비어 있을 경우
root = newNode;
return root;
}
ptr = root; // root 노드부터 탐색 진행
while(ptr){
if(key == ptr->key){ // 중복값
printf("Error : 중복값은 허용되지 않습니다!\n");
return root;
}else if(key < ptr->key){ // 왼쪽 서브트리
if(ptr->left == NULL){ // 비어있다면 추가
ptr->left = newNode;
return root;
}else{ // 비어있지 않다면 다시 탐색 진행
ptr= ptr->left;
}
}else{ // key > ptr->key 오른쪽 서브트리
if(ptr->right == NULL){ // 비어있다면 추가
ptr->right = newNode;
return root;
}else{ // 비어있지 않다면 다시 탐색 진행
ptr = ptr->right;
}
}
}
}
TreeNode* delete_node(TreeNode* root, int key){
TreeNode* del = NULL; // 삭제할 노드
TreeNode* parent = NULL; // 삭제할 노드의 부모 노드
TreeNode* successor = NULL; // 삭제할 노드의 왼쪽 서브트리에서 가장 큰 노드
TreeNode* predecessor = NULL; // successor의 부모노드
TreeNode* child = NULL; // 삭제할 노드의 자식 노드
del= root;
while(del != NULL){ // 삭제할 노드 탐색
if(key == del->key){
break;
}
parent = del;
if(key < del->key){
del = del->left;
}else{
del = del->right;
}
}
if(del == NULL){
printf("Error : 존재하지 않는 키\n");
return root;
}
if(del->left == NULL && del->right == NULL){ // 삭제할 노드의 자식노드가 없는 경우
if(parent != NULL){ // 부모노드가 있는 경우
if(parent->left == del){ // 부모노드의 왼쪽노드가 삭제할 노드일 때
parent->left = NULL;
}else{ // 오른쪽 일 때
parent->right = NULL;
}
}else{ // 부모노드가 없는 경우 = root 노드
root = NULL;
}
}else if(del->left != NULL && del->right != NULL){ // 삭제할 노드의 자식 노드가 2개인 경우
predecessor = del;
successor = del->left;
while(successor->right != NULL){ // 왼쪽 서브트리에서 가장 큰 값 찾기
predecessor = successor;
successor = successor->right;
}
if(predecessor->left == successor){
predecessor->left = successor->left;
}else{
predecessor->right = successor->left;
}
del->key = successor->key;
del = successor;
}else{ // 삭제할 노드의 자식 노드가 1개인 경우
if(del->left != NULL){ // 왼쪽 노드
child = del->left;
}else{ // 오른쪽 노드
child = del->right;
}
if(parent != NULL){ // 부모노드가 있는 경우
if(parent->left == del){ // 부모노드의 왼쪽 노드로 삭제할 노드의 자식노드 연결
parent->left = child;
}else{ // 부모노드의 오른쪽 노드로 삭제할 노드의 자식노드 연결
parent->right = child;
}
}else{
root = child;
}
}
free(del); // 메모리해제
return root;
}
void print_tree(TreeNode* root){
if(root == NULL){
return;
}
printf("%d\n", root->key);
print_tree(root->left);
print_tree(root->right);
}
int main(){
TreeNode* root = NULL;
TreeNode* ptr = NULL;
root = insert(root, 7);
root = insert(root, 3);
root = insert(root, 8);
root = insert(root, 1);
root = insert(root, 5);
root = insert(root, 4);
root = insert(root, 10);
print_tree(root);
printf("\n");
ptr = search(root, 7);
printf("%d\n", ptr->key);
root = delete_node(root,7);
ptr = search(root, 7);
return 0;
}
|
cs |
실행결과
'Computer Science > [자료구조]' 카테고리의 다른 글
| [자료구조] 그래프(Graph)의 개념과 이해, 용어 | 인접행렬 vs 인접리스트 그래프 구현 (3) | 2021.07.22 |
|---|---|
| [자료구조]Max Heap, Min Heap, Heap 이란? | C언어 Heap 구현 (0) | 2021.07.21 |
| [자료구조] 트리의 순회, 중위 순회, 전위 순회, 후위 순회 | C언어 트리 순회 구현 (4) | 2021.07.19 |
| [자료구조] 트리(Tree)의 개념, 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐색트리 (6) | 2021.07.16 |
| [자료구조] 큐(Queue)란? | c언어 큐 구현 (3) | 2021.07.15 |