1. 이진 탐색 트리의 정의
컴퓨터 프로그램에서 쓰이는 탐색 용어는 다음과 같다
탐색: 레코드의 집합에서 특정 레코드를 찾는 작업
레코드: 하나 이상의 필드로 구성됨, key라 불리는 하나의 필드에 의해 식별 가능
테이블: 레코드들의 집합
주요키: 다른 키와 중복되지 않는 고유한 키
이진 탐색 트리의 정의는 다음과 같다.
- 모든 원소의 키는 유일한 키를 가짐
- 왼쪽 서브 트리 키들은 루트 키보다 작음
- 오른쪽 서브 트리의 키들은 루트의 키보다 큼
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리임
따라서 찾고자 하는 키값을 루트 노드의 키값과 비교하여, 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리에 가서 찾으면 된다.
2. 순환적인 탐색연산
루트값과 탐색키를 비교하면 다음과 같은 3가지 case가 나온다
루트값 == 탐색키: 탐색이 성공적으로 끝남
루트값 >= 탐색키: 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작
루트값 <= 탐색키: 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작
TreeNode *search(TreeNode *node, int key)
{
if(node == NULL) return NULL;
if(key == node->key) return node;
else if(key < node->key)
return search(node->left, key);
else
return serch(node->right, key);
}3. 반복적인 탐색연산
효율성을 따지면 순환보다 반복 탐색이 더 우수하다.
먼저 매개변수 node가 NULL이 아니면 반복을 계속한다. 반복 루프 안에서는 현재 node의 키값이 key와 같은지 검사한다. 만약 같으면 현재 노드 포인터를 반환, key값이 작으면 node변수를 node의 왼쪽 자식을 가리키도록, key값이 크면 node 변수를 node의 오른쪽 자식을 가리키도록 변경한다. 단말노드를 만나 NULL이 반환될때까지 계속 한다.
TreeNode *search(TreeNode *node, int key)
{
while(node != NULL){
if(key == node->key)
return node;
else if(key < node->key)
node = node->left;
else
node = node->right;
}
return NULL; //탐색에 실패했을 경우 NULL을 반환
}4. 이진탐색트리 프로그래밍
- 삽입 연산
삽입 전에 먼저 탐색을 수행해야 한다. 중복된 값 삽입을 피하고, 탐색에 실패한 위치가 바로 새로운 노드를 삽입해야 하는 위치이기 때문이다.
새로운 노드는 항상 단말노드에 추가된다. 단말노드를 발견하면 그 노드의 하위노드로 새로운 노드를 추가한다.
TreeNode *insert_node(TreeNode *node, int key) // key는 삽입할 탐색키값
{
//트리가 공백이면 새로운 노드를 반환
if(node == NULL)
return new_node(key);
//그렇지 않으면 순환적으로 트리를 내려간다.
if(key < node->key)
node->left = insert_node(node->left, key);
else if(key > node->key)
node->right = insert_node(node->right, key);
//변경된 루트 포인터를 반환한다.
return node;
}- 삭제 연산
가장 복잡한 연산이다. 총 3가지 경우가 있다-삭제하려는 노드가 단말 노드인 경우
-삭제하려는 노드가 하나의 서브트리만 갖고 있는 경우
-삭제하려는 노드가 두개의 서브트리를 갖고 있는 경우
-
삭제하려는 노드가 단말노드일 경우, 단순히 단말노드의 부모노드를 찾아 연결을 끊으면 된다.
-
삭제하려는 노드가 하나의 서브트리만 갖고 있는 경우, 해당 노드를 삭제하고, 서브트리를 부모노드에 붙여주면 된다.
-
삭제하려는 노드가 두 개의 서브트리를 갖고 있는 경우, 삭제노드와 가장 비슷한 값을 가진 노드를 삭제노드 위치로 가져온다. 왼쪽 서브트리의 가장 큰 값과 오른쪽 서브트리의 가장 작은 값이 후보가 된다. 즉, 선행노드와 후속노드에 해당한다.
어느 것을 골라도 상관없다. 만약 후속노드를 고른다고 하면, 왼쪽 자식 링크를 타고 NULL을 만날때까지 계속 진행하면 된다.
//이진 탐색 트리와 키가 주어지면 키가 저장되 노드를 삭제하고 새로운 루트 노드를 반환한다.
//p: 부모노드, t: 현재노드, succ: 후계자 노드, succ_p: 후계자 노드의 부모
TreeNode * delete_node(TreeNode * root, int key)
{
if(root == NULL) return root;
//만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것임
if(key < root->key)
root->left = delete_node(root->left, key);
//만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
else if(key > root->key)
root->right = delete_node(root->right, key);
//키가 루트와 같으면 이 노드를 삭제하면 됨
else{
//첫번째나 두번째인 경우
if(root->left == NULL){
Treenode * temp = root->right;
free(root);
return temp;
}
else if(root->right == NULL){
TreeNode * temp = root->left;
free(root);
return temp;
}
//세번째인 경우
TreeNode * temp = min_value_node(root->right);
//중위 순회 시 후계 노드를 복사한다.
root->key = temp->key;
//중위 순회시 후계 노드를 삭제한다.
root->right = delete_node(root->right, temp->key);
}
return root;
}// 이진 탐색 트리에서 최소 키값을 가지는 노드를 반환
TreeNode * min_value_node(TreeNode * node)
{
TreeNode * current = node;
//맨 왼쪽 단말 노드를 찾으러 내려감
while(current->left != NULL)
current = current->left;
return current;
}
- 전체 프로그램
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct TreeNode{
element key;
struct TreeNode *left, *right;
} TreeNode;
//순환적인 탐색 함수
TreeNode *search(TreeNode *node, int key)
{
if(node == NULL) return NULL;
if(key == node->key) return node;
else if(key < node->key)
return search(node->left, key);
else
return serch(node->right, key);
}
TreeNode * new_node(int item)
{
TreeNode *temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode *insert_node(TreeNode *node, int key) // key는 삽입할 탐색키값
{
//트리가 공백이면 새로운 노드를 반환
if(node == NULL)
return new_node(key);
//그렇지 않으면 순환적으로 트리를 내려간다.
if(key < node->key)
node->left = insert_node(node->left, key);
else if(key > node->key)
node->right = insert_node(node->right, key);
//변경된 루트 포인터를 반환한다.
return node;
}
TreeNode * min_value_node(TreeNode * node)
{
TreeNode * current = node;
//맨 왼쪽 단말 노드를 찾으러 내려감
while(current->left != NULL)
current = current->left;
return current;
}
//이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고 새로운 루트 노드를 반환한다.
TreeNode * delete_node(TreeNode * root, int key)
{
if(root == NULL) return root;
//만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것임
if(key < root->key)
root->left = delete_node(root->left, key);
//만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
else if(key > root->key)
root->right = delete_node(root->right, key);
//키가 루트와 같으면 이 노드를 삭제하면 됨
else{
//첫번째나 두번째인 경우
if(root->left == NULL){
Treenode * temp = root->right;
free(root);
return temp;
}
else if(root->right == NULL){
TreeNode * temp = root->left;
free(root);
return temp;
}
//세번째인 경우
TreeNode * temp = min_value_node(root->right);
//중위 순회 시 후계 노드를 복사한다.
root->key = temp->key;
//중위 순회시 후계 노드를 삭제한다.
root->right = delete_node(root->right, temp->key);
}
return root;
}
//중위 순회
void inorder(TreeNode * root){
if(root){
inorder(root->left); //왼쪽 서브트리 순회
printf("[%d] ", root->key); // 노드 방문
inorder(root->right); // 오른쪽 서브트리 순회
}
}
int main(void)
{
TreeNode * root = NULL;
TreeNode * tmp = NULL;
root = insert_node(root, 30);
root = insert_node(root, 20);
root = insert_node(root, 10);
root = insert_node(root, 40);
root = insert_node(root, 50);
root = insert_node(root, 60);
printf("이진 탐색 트리 중위 순회 결과 \n");
inorder(root);
printf("\n\n");
if(search(root, 30) != NULL)
printf("이진 탐색 트리에서 30을 발견함 \n");
else
printf("이진 탐색 트리에서 30을 발견못함 \n");
return 0;
}5. 이진 탐색 트리의 분석
이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때, O(h)가 된다.
따라서 n개의 노드를 가지는 이진 탐색 트리의 경우, 평균적인 시간복잡도는 최선의 경우 O(), 최악의 경우(경사이진트리인 경우) O(n)이다.
6. 이진 탐색 트리의 응용: 영어 사전
프로그램의 메뉴는 다음과 같다
i: 입력, d: 삭제, s: 탐색, p: 출력, q: 종료입력 기능은 insert_node()를 사용하여 이진 탐색 트리에 저장한다.
탐색 기능은 search()를 사용하여 탐색하고, 화면에 출력한다.
삭제 기능은 delete_node()를 사용하여 입력된 단어를 찾고 삭제한다.
여기에 저장되는 데이터는 단어와 단어뜻이다. 따라서 element타입을 구조체로 정의하고 두 개의 문자배열을 선언한다.
#define MAX_WORD_SIZE 100
#define MAX_MEANING_SIZE 200
//데이터 형식
typedef struct{
char word[MAX_WORD_SIZE];
char meaning[MAX_MEANING_SIZE];
} element;
//노드의 구조
typedef struct TreeNode{
element key;
struct TreeNode *left, *right;
} TreeNode;또한 두 개의 element 항목의 순서를 비교하는 compare()가 필요하다. e1과 e2를 알파벳 순서로 비교하여 e1이 작으면 -1, 같으면 0, 크면 1을 반환한다.
int compare(element e1, element e2)
{
return strcmp(e1.word, e2.word)
}다음은 전체 프로그램이다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#define MAX_WORD_SIZE 100
#define MAX_MEANING_SIZE 200
//데이터 형식
typedef struct{
char word[MAX_WORD_SIZE];
char meaning[MAX_MEANING_SIZE];
} element;
//노드의 구조
typedef struct TreeNode{
element key;
struct TreeNode *left, *right;
} TreeNode;
int compare(element e1, element e2)
{
return strcmp(e1.word, e2.word)
}
void display(TreeNode *p)
{
if(p != NULL){
printf("(");
display(p->left);
printf("%s:%s", p->key.word, p->key.meaning);
display(p->right);
printf(")");
}
}
//이진 탐색 트리 함수
TreeNode * search(TreeNode * root, element key)
{
TreeNode * p = root;
while(p != NULL){
if(compare(key, p->key) == 0)
return p;
else if(compare(key, p->key) < 0)
p = p->left;
else if(compare(key, p->key) > 0)
p = p->right;
}
return p;
}
TreeNode * new_node(element item)
{
TreeNode * temp = (TreeNode *)malloc(siezeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode *insert_node(TreeNode *node, int key) // key는 삽입할 탐색키값
{
//트리가 공백이면 새로운 노드를 반환
if(node == NULL)
return new_node(key);
//그렇지 않으면 순환적으로 트리를 내려간다.
if(compare(key, node->key) < 0)
node->left = insert_node(node->left, key);
else if(compare(key, node->key) > 0)
node->right = insert_node(node->right, key);
//변경된 루트 포인터를 반환한다.
return node;
}
TreeNode * min_value_node(TreeNode * node)
{
TreeNode * current = node;
//맨 왼쪽 단말 노드를 찾으러 내려감
while(current->left != NULL)
current = current->left;
return current;
}
//이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고 새로운 루트 노드를 반환한다.
TreeNode * delete_node(TreeNode * root, int key)
{
if(root == NULL) return root;
//만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것임
if(compare(key, root->key) < 0)
root->left = delete_node(root->left, key);
//만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
if(compare(key, root->key) > 0)
root->right = delete_node(root->right, key);
//키가 루트와 같으면 이 노드를 삭제하면 됨
else{
//첫번째나 두번째인 경우
if(root->left == NULL){
Treenode * temp = root->right;
free(root);
return temp;
}
else if(root->right == NULL){
TreeNode * temp = root->left;
free(root);
return temp;
}
//세번째인 경우
TreeNode * temp = min_value_node(root->right);
//중위 순회 시 후계 노드를 복사한다.
root->key = temp->key;
//중위 순회시 후계 노드를 삭제한다.
root->right = delete_node(root->right, temp->key);
}
return root;
}
void help()
{
printf("\n**** i: 입력, d: 삭제, s: 탐색, p: 출력, q: 종료 ****: ");
}
//이진 탐색 트리를 사용하는 영어 사전 프로그램
int main(void)
{
char command;
element e;
TreeNode * root = NULL;
TreeNode * tmp;
do{
help();
command = getchar();
getchar();
switch(command){
case 'i':
printf("단어: ");
gets_s(e.word, MAX_WORD_SIZE);
printf("의미: ");
gets_s(e.meadning, MAX_MEANING_SIZE);
root = insert_node(root, e);
break;
case 'd':
printf("단어: ");
gets_s(e.word, MAX_WORD_SIZE);
root = delete_node(root, e);
break;
case 'p':
display(root);
printf("\n");
break;
case 's':
printf("단어: ");
gets_s(e.word, MAX_WORD_SIZE);
tmp = search(root, e);
if(tmp != NULL)
printf("의미: %s\n", e.meaning);
break;
}
}while (command != 'q');
return 0;
}
피넛버터