C언어 | 이진 탐색 트리( Binary Search Tree) 만들기 | 추가, 삭제, 검색
이진 탐색 트리 C언어
*이진검색트리 (Binary Search Tree)의 조건
- 이진 트리는 루트를 중심으로 노드가 왼쪽에 하나 오른쪽에 하나씩 연결된다.
- 노드 N(어느 한 노드)을 기준으로 왼쪽 트리의 키값은 노드 N보다 작아야 하고, 오른쪽 트리의 키 값은 노드 N보다 커야 한다.
- 같은 키값을 갖는 노드는 없다.
이 포스팅에서는 C언어로 이진 탐색 트리 자료형를 만들어 본다.
이진 탐색 트리는 값을 입력시 자동으로 정렬된다. 특히 이진 탐색 트리에는 중복된 값이 입력되지 않는다.
이진 검색이라는 용어가 있는데 엄밀히 말하면 이진 검색과 이진 탐색 트리는 같은 것이 아니다.
이진 검색은 오름차순으로 정렬된 숫자의 배열에서 검색하는 알고리즘이고, 이진 탐색 트리는 위와 같은 조건을 가진 자료 구조다. 당연히 다른 자료형 보다 이진 검색에 최적화 되어있다.
이진 탐색 트리의 구현
* 이진 탐색 트리 구현은 일단 좀 어렵다.
트리의 생성과 삭제 검색 시 포인터 연산과 재귀함수를 사용하기 때문에 포인터 사용에 능숙하지 않으면 코드를 읽기가 어렵다. 여기에 이중 포인터까지 사용하는 경우도 있어 거의 분석이 쉽지 않다. 진행이 안되면 포인터 연습을 더 해야 할 것이다.
* 우선 이진 트리의 노드를 정의한다. 중요한게 이진 트리는 두개 노드인 왼쪽, 오른쪽 노드가 있고 데이터가 있다. 데이터는 다른 구조체가 될 수도 있고 배열이 될 수도 있다. 기본인 정수형을 넣었으니 나중에 코드 확장시 필요한 데이터 형을 넣으면 된다.
* 동적 메모리 할당을 받아 노드를 생성하는 코드이다. get 에서 생성과 초기화를, 실제 데이터를 넣도록 했는데 과정을 보려고 동작을 세분화 시킨 것이고 둘을 합쳐도 된다. 초기값이 정해지면 하나로 합쳐도 된다.
* 노드를 추가하는 함수다. 새로운 값을 입력하면 스스로 정렬이 되는데 그것은 재귀함수를 통해서 작동한다.
1. 노드가 없다 (포인터가 NULL 은 참조만 있다는 것) 그럼 생성한다.
2. 입력하려는 키값(data)과 현재 노드의 키값이 같다. -> 중복은 허용이 안되므로 노드만 반환한다.
3. 키값이 노드의 키값보다 작다. 이때는 왼쪽으로 내려가야한다. (왼쪽이 더 작고 오른쪽이 더 크다) 내려가는 코드는
node->left 왼쪽 참조를 매개변수로, 키값과 내려보낸다. 그러면 왼쪽노드가 비어있을 경우 (NULL) 다시 1번으로 가서 노드를 생성하고 node->left 로 생성된 노드를(주소) 반환한다. 새로운 노드가 생성되서 나오면 NULL이었던 node->left 에 연결시킨다.
이 과정이 재귀적으로 반복하면 어떤 숫자도 정렬하여 입력된다.
4. 키값이 노드보다 크다. 오른쪽으로 내려간다. 3번의 반복이라 보면된다. 그리고 내려가다 보면 왼쪽으로 내려갔는데 오른쪽으로 다시 내려갈 수도 있고 내려가는 도중에는 방향을 여러번 바꿀 수 있다. 중요한 것은 내려가서 없으면(NULL) 생성하고 생성한 노드가 재귀함수를 탈출하면 오른쪽으로 붙일 것인지, 왼쪽으로 연결할 것인지 자동으로 결정된다는 것이다.
* 검색하는 원리가 노드를 추가하는 원리와 같다. 노드를 추가하면서 정렬한다는 것은 추가시에 이미 정렬에 대한 부분이 고려되어 데이터가 들어간다는 것을 의미한다.
여기서는 4개의 경우의 수를 처리한다.
1. 노드가 NULL 인 경우. 처음부터 NULL이면 비어있는 노드이다. 하위 트리로 내려가다가 키값을 못찾으면 마지막에 걸린다.
2. 키값이 노드의 키값과 같다. -> 결과를 반환한다.
3. 키값이 노드의 키값보다 작다. 왼쪽으로 내려간다. 추가할 때 처럼 노드를 연결시키지 않는다. 단순히 검색이 목적이기 때문이다. 하위 트리로 내려가다 보면 결국 끝을 만나도록 되어있다. 검색이 실패하던지 성공하던지 둘 중 하나이다.
4. 3번의 반대다. 오른쪽으로 내려간다.
* 노드의 데이터를 출력하는 함수이다.
매개변수로 노드를 입력받아서 노드가 NULL 이 아닌경우 노드의 데이터를 출력한다. 가운데 printf 함수가 있고 위 아래로 있는 것은 좌로 끝까지 같다 오고, 우로 끝까지 같다 오기 위해서 이다.
node->left로 가서 값이 있으면 출력하고 빠져나올 것이고 root 노드의 키값을 printf 로 찍고 node->right 로 다녀올 것이다. 순서가 왼쪽, 중앙, 오른쪽이라고 보면 된다. 이 세줄로 모든 노드를 출력할 수 있다.
(재귀함수는 코드가 짧아진다.)
* 모드 노드의 메모리를 해제하는 코드이다. 위의 노드 데이터를 출력하는 함수와 비교를 해보면 순서가 바뀌었다. 왼쪽 서브트리에서 시작해서 오른쪽 서브트리로 갔다가 다시 중앙의 루트노드로 온다. 왜냐하면 순서를 중앙의 루트먼저 해제하면 오른쪽의 서브트리에 있는 노드들의 메모리는 해제되지 않는다. 즉 메모리는 점유하는데 포인터가 사라진다. 이렇게 메모리를 운영하는 것은 잘못이다. 프로그램이 노드 몇개 생성하기를 반복하는 것만으로도 심각한 메모리오류에 걸릴 수 있다. 여기 예제는 단순한 데이터 하나지만. 예를 들어 1메가 정도의 이미지나 데이터를 이진 트리에 저장했다고 하면 기가단위의 메모리도 금방 바닥날 수 있다. 순서 하나도 중요하다는 것에 주의한다.
마지막으로 이진트리에서 특정 노드를 삭제하는 함수다. 이 부분이 가장 힘들고 난해하다. 네 가지 경우가 있다.
매개변수는 삭제하려는 노드와 삭제하려는 키값이다. (키값은 중복이 없으니까 유일하다)
1. 루트가 NULL 이면 -> 트리가 비어있으므로 그냥 노드를 반환한다.
2. 키가 노드의 키보다 작거나 큰 경우 재귀해야한다. 작으면 왼쪽 크면 오른쪽 이 개념은 이진 트리를 접하면서 익숙해진다.
3. 재귀를 반복하면서 키가 노드의 키 값과 일치하는 경우가 나온다. 삭제하려는 노드 아래 자식 노드가 한개인 경우가 있다. 왼쪽에 있거나 오른쪽에 있다. 판별은 왼쪽에 아무것도 없다면(NULL)이라면 오른쪽의 노드를 temp 에 저장해둔다. 그리고 현재 노드를 free 함수로 해제한다. 그리고는 temp 에 저장된 오른쪽 노드를 반환한다. 반환된 오른쪽 노드는 한 층이 올라간다. 즉 2번의 왼쪽이나 오른쪽에 연결된다.
반면 else if 오른쪽이 NULL 이라면 왼쪽의 노드를 temp 에 저장하고 현재 노드를 free 해제한 후 왼쪽의 노드를 리턴한다. 그런 다음 2번에서 root->left 나 root->right 에서 받아 연결한다.
그림으로 그려보면 아래와 같다. 삭제하려는 노드의 오른쪽이 NULL 이면 그대로 왼쪽 노드를 끌어오는 것이다. 오른쪽이 없으니 상관이 없기 때문이다. key가 매치되는 20이 삭제되면 그 아래 노드와 연결이 끓어지므로 temp 라는 임시 포인터에 주소를 저장한 후 root->right의 메모리를 해제시킨다. 여기서 temp 는 지역변수이기 때문에 반환되면 메모리에서 사라진다. 메모리를 동적할당 받은 root->right->left 는 여전히 유효한 것이다. free 함수로 사라지는 것은 root->right이다.
root->right 가 재귀로 내려가면 매개변수를 다시 root로 받기 때문에 읽기가 어려운 것이다. 계속 말이 반복되고 그게 그것인 것 처럼 보인다. 그럴때는 손으로 그림을 그려가면서 하는게 좋다. 공책에 그림을 그리거나 쓰는 것은 알고리즘을 풀때 유용한 방법이다. 타이핑만 하는 것보다 훨씬 수월하다.
4. 노드의 자녀가 두개 있는 경우
자녀가 두개 있는 노드를 삭제해야 하는 경우다. 이 경우 왼쪽과 오른쪽의 자녀 노드가 있고 그 둘다 왼쪽과 오른쪽 자녀 노드가 있다고 한다면 3번처럼 한쪽을 끌고 오면 나머지 한쪽의 노드가 사라지게 된다.(메모리 유실)
이런 경우는 left 노드나 right 노드에서 하나를 선택해야 한다. 어느 쪽을 선택해도 된다. 다만 left 노드를 선택시에는 서브트리에서 가장 큰 값을 right 노드 선택시에는 서브트리에서 가장 작은 값으로 대체해야 한다.
예제 코드에서는 오른쪽을 노드를 선택한다.
하위 노드에서 가장 작은 값을 찾는 함수는 아래와 같다. 커서 포인터를 사용하여 오른쪽 서브 트리중에서 가장 작은 키값의 노드를 찾는다. && 앤드 연산자는 자신이나 자신의 왼쪽의 포인터가 NULL인 경우 현재 위치를 반환한다.
찾은 값은 현재 노드의 키값과 바꾼다.
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);바꾼 후에는 다시 오른쪽돌아서 키값을 삭제하고 하위 노드를 연결한다. 재귀적으로 일어나기 때문에 레벨이 길어지면 사람이 이해하기에는 꽤 복잡해진다. 재귀에 재귀를 거듭하다 보면 이게 어디서 시작이고 끝인지 알기가 어려워진다. 이런 원리로 작동된다는 정도를 알아두기로 한다.
여기까지다. 다른 것 보다 삭제 프로세스가 간단하지 않다는 것을 알 수 있다. 현대의 프로그래밍에서는 STL 의 컨테이너와 자바의 컬렉션 프레임워크 등이 있기 때문에 직접 개발하는 수고는 없어도 되니 다행이다.
하지만 이런 자료형이 필요한 경우에 한 두가지 정도는 만들수도 있으니까 알아두면 나쁘지는 않을 것이다.
다만 위의 내용을 완벽하게 이해하고 응용하려면 많은 시간이 든다. 요즘 같이 빨리 결과물을 내놓아야 하는 세상에서는 너무 많은 시간을 뺏기는 것도 좋지 않다.
You don't need to reinvent the wheel. '수레바퀴를 다시 발명할 필요는 없다.' 는 교훈도 21세기를 살아가는 우리에게 필요한 자세다. 물론 수레바퀴가 어떻게 굴러가는지 원리를 안다고 나쁠 것은 없을 것이다.
#include <stdio.h>
#include <stdlib.h>
#define WELCOME printf("Hello World!\n\n")
#define LINE printf("\n\n<*--------------------------------------*>\n\n");
#define show(x) LINE; printf(" [이진 트리 출력]\n["); showTree(x); printf("]"); LINE;
typedef struct binary_node {
int data;
struct binary_node *left;
struct binary_node *right;
} BinNode;
BinNode *getBinaryNode(void);
void setBinNode(BinNode *ptr, int data, BinNode *left, BinNode *right);
BinNode *addNode(BinNode *ptr, int data);
void showTree(const BinNode *ptr);
void deleteTree(BinNode *ptr);
int getRandomInt(int from, int to);
BinNode *searchTree (BinNode *ptr, int key);
BinNode *deleteNode(BinNode *root, int key);
BinNode *minValueNode(BinNode * node);
int main(int argc, char const *argv[])
{
/* code */
WELCOME;
BinNode *root = NULL;
BinNode *search = NULL;
for (int i = 0; i < 5; i++)
{
root = addNode(root, i*2);
root = addNode(root, i*(-1));
}
show(root);
search = searchTree(root, 8);
(search != NULL) ? printf("*검색결과 값: %d, 주소: 0x%p", search->data, search):
printf("*검색결과 없음");
LINE;
deleteTree(root);
printf("\n\n");
/* code */
root = NULL;
for (int i = 0; i < 10; i++)
{
root = addNode(root, getRandomInt(1,50));
}
show(root);
deleteTree(root);
/* code */
root = NULL;
root = addNode(root, 5);
root = addNode(root, 1);
root = addNode(root, 8);
root = addNode(root, 4);
root = addNode(root, 2);
root = addNode(root, 6);
root = addNode(root, 9);
root = addNode(root, 7);
root = addNode(root, 3);
show(root);
// 키값을 삭제한다
root = deleteNode(root, 5);
root = deleteNode(root, 8);
root = deleteNode(root, 3);
show(root);
deleteTree(root);
return 0;
}
/*--- 하위 노드중 가장 작은 값을 찾아 준다. ---*/
BinNode *minValueNode(BinNode * node)
{
// 커서 노드
BinNode *cur = node;
while(cur && cur->left != NULL ){
cur = cur->left;
}
// printf("리턴한다 %d 0x%p\n", cur->data, cur);
return cur;
}
/*--- 특정 노드 삭제 일반 포인터로 ---*/
BinNode *deleteNode(BinNode *root, int key)
{
// root가 NULL 일 경우. 트리가 비어있을 경우.
if (root == NULL){
return root;
}
// key 가 노드의 키값보다 작거나 큰 경우[하위트리에 이동]
if (key < root->data){
root->left = deleteNode(root->left, key);
} else if (key > root->data){
root->right = deleteNode(root->right, key);
}
// 키가 노드의 키값과 같은 경우[삭제]
else {
// 노드의 자녀가 한개일 경우(왼쪽 아니면 오른쪽)
// 노드 자녀가 없는 경우도 if문에서 삭제된다.
if(root->left == NULL){
BinNode *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL){
BinNode *temp = root->left;
free(root);
return temp;
}
// 노드의 자녀가 두개일 경우(왼쪽 오른쪽 둘다)
// 오른쪽 서브트리에서 가장 작은 수를 선택한다.
// printf("여기\n");
BinNode *temp = minValueNode(root->right);
// LINE
// printf("root->data : %d, temp->data : %d at 0x%p\n", root->data, temp->data, temp);
root->data = temp->data;
// printf("root->data : %d, temp->data : %d\n", root->data, temp->data);
root->right = deleteNode(root->right, temp->data);
}
return root;
}
/*--- 키값으로 검색 ---*/
BinNode *searchTree (BinNode *ptr, int key)
{
if(ptr == NULL){
printf("키값이 (%d)인 노드는 없습니다. [검색실패]\n", key);
return NULL;
} else if (key == ptr->data){
printf("키값이 (%d)인 노드를 반환합니다. [검색성공]\n", key);
return ptr;
} else if (key < ptr->data){
searchTree(ptr->left, key);
} else {
searchTree(ptr->right, key);
}
}
/*--- 랜덤 생성 ---*/
int getRandomInt(int from, int to)
{
int random = rand() % (to-from+1) + from;
return random;
}
/*--- 모든 노드의 메모리 해제 ---*/
void deleteTree(BinNode *node)
{
if(node != NULL){
deleteTree(node->left);
deleteTree(node->right);
free(node);
}
}
/*--- 모든 노드의 데이터를 출력 ---*/
void showTree(const BinNode *node)
{
if(node != NULL){
showTree(node->left);
printf("%d, ", node->data);
showTree(node->right);
}
}
/*--- 바이너리 노드 동적할당 ---*/
BinNode *getBinaryNode(void)
{
BinNode *newNode = calloc(1, sizeof(BinNode));
newNode->data = 0; // 초기화 0
newNode->left = NULL; // 초기값 NULL
newNode->right = NULL; // 초기값 NULL
// printf("*[노드 초기화 완료]\n");
return newNode;
}
/*--- 노드 설정 (left노드, right노드) --*/
void setBinNode(BinNode *node, int data , BinNode *left_child, BinNode *right_child)
{
node->data = data;
node->left = left_child;
node->right = right_child;
}
int count = 0;
BinNode *addNode(BinNode *node, int data)
{
if (node == NULL){
node = getBinaryNode();
setBinNode(node, data, NULL, NULL);
printf("node 생성완료 (%2d), counter : %d\n",node->data, count++);
} else if (data == node->data){
printf("*[이진트리] - 중복된 값은 입력이 안됩니다...\n");
} else if (data < node->data){
node->left = addNode(node->left, data);
// printf("left tree 생성 완료 %d\n", node->left->data);
} else {
node->right = addNode(node->right, data);
// printf("right tree 생성 완료 %d\n", node->right->data);
}
// printf("[종료]\n");
return node;
}
