탐색 - 레코드의 집합(테이블)에서 특정한 레코드를 찾아내는 작업
레코드 - 하나이상의 필드로 구성
키 - 레코드를 구별하기 위한 고유의 값
이진 탐색 트리
- 모든 원소의 키는 유일하다.
- 왼쪽 서브트리의 키들은 루트의 키보다 작다.
- 오른쪽 서브트리의 키들은 루트의 키보다 크다.
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
탐색 연산
- 비교결과가 같으면 탐색 성공
- 비교결과가 주어진 키값이 루트노드의 키값보다 작으면 왼쪽 자식을 루트로 다시 시작
- 비교결과가 주어진 키값이 루트노드의 키값보다 크면 오른쪽 자식을 루트로 다시 시작
- 순환의 개념
- 단말노드까지 내려가서 NULL값이 될때까지 반복.
삽입연산
- NULL값이 되고 반복이 종료되었는데도 리턴값이 없으면 탐색 실패
- 실패 지점에 새로운 노드 삽입
삭제연산
- 삭제할 노드가 단말노드일 경우 : 부모노드의 링크필드를 NULL로 바꾸고 연결 끊기
- 삭제할 노드가 하나의 서브트리를 가진 경우 : 서브트리를 부모노트의 링크에 붙이기
- 삭제할 노드가 드개의 서브트리를 가진 경우 :
왼쪽 서브트리에서 가장 큰값과 오른쪽 서브트리에서 가장 작은값 중에 하나를 골라
삭제 노트의 위치와 바꾼다.
//이진 탐색 트리를 이용한 영어 사전 프로그램
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#define MAX_WORD_SIZE 100
#define MAX_MEANING_SIZE 200
//데이터형식 <- key
typedef struct {
char word[MAX_WORD_SIZE];
char meaning[MAX_MEANING_SIZE];
} element;
//노드의구조
typedef struct TreeNode {
element key;
struct TreeNode *left, *right;
} TreeNode;
// 키값 비교
// e1 > e2 => -1 반환
// e1 == e2 => 0 반환
// e1 < e2 => 1 반환
int compare(element e1, element e2)
{
return strcmp(e1.word, e2.word);
}
//출력
void display(TreeNode *p)
{ //p가 null일때의 처리없음
if(p!=NULL) {
printf("(");
display(p->left); //왼쪽 서브 트리로 재귀
printf("%s", p->key.word);
display(p->right); //오른쪽 서브트리로 재귀
printf(")");
}
}
//탐색
TreeNode *search(TreeNode *root, element key)
{
TreeNode *p = root;
while(p!=NULL) {
switch(compare(key, p->key)) {
case -1:
p = p->left;
break;
case 0:
return p;
case 1:
p=p->right;
break;
}
}
return p;
}
//삽입
void insert_node(TreeNode **root, element key)
{
TreeNode *p, *t;
TreeNode *n;
t=*root;
p=NULL;
//탐색수행
while(t!=NULL) {
if(compare(key, t->key)==0) return;
p=t;
if(compare(key, t->key)<0) t=t->left;
else t=t->right;
}
//item이 없으므로 삽입가능
n=(TreeNode *)malloc(sizeof(TreeNode));
if(n==NULL) return;
//데이터 복사
n->key = key;
n->left = n->right = NULL;
//부모노드와 링크 연결
if(p!=NULL)
if(compare(key, p->key)<0)
p->left = n;
else p->right = n;
else *root = n;
}
//삭제
void delete_node(TreeNode **root, element key)
{
TreeNode *p, *child, *succ, *succ_p, *t;
p=NULL;
t=*root;
while(t != NULL && compare(key, t->key)!=0) {
p=t;
t=(compare(key, t->key)<0) ? t->left : t->right;
}
if(t==NULL) {
printf("key is not in the tree");
return;
}
//단말노드
if((t->left == NULL) && (t->right == NULL)) {
if(p!=NULL) {
if(p->left == t) p->left =NULL;
else p->right = NULL;
}
else *root = NULL; //부모노드가 없으면 노드
}
//하나의 자식노드
else if((t->left == NULL) || (t->right == NULL)) {
child = (t->left != NULL) ? t->left : t->right;
if(p != NULL) {
if(p->left == t) p->left = child; //부모노드를 자식노드와 연결
else p->right = child;
}
else *root = child;
}
//두개의 자식노드
else {
succ_p = t;
succ = t->right; //오른쪽 서브트리에서 후속자를 찾는다
while(succ->left !=NULL) {
succ_p = succ;
succ = succ->left; //후속자를 찾아서 왼쪽으로 계속 이동
}
//후속자의 부모와 자식을 연결
if(succ_p->left == succ) succ_p->left = succ->right;
else succ_p->right = succ->right;
//후속자를 현재 노드로 이동
t->key = succ->key;
t=succ;
}
free(t);
}
//목차
void help()
{
printf("***************\n");
printf("i : 입력 \n");
printf("d : 삭제 \n");
printf("s : 탐색 \n");
printf("p : 출력 \n");
printf("q : 종료 \n");
printf("***************\n");
}
//메인
void main()
{
char command;
element e;
TreeNode *root = NULL;
TreeNode *tmp;
do {
help();
command = getchar();
fflush(stdin); //버퍼에 남은 \n을 제거
//stdin : Standard Input ( 기본 입력 스트림 )
switch(command) {
case 'i':
printf("단어: ");
gets(e.word);
printf("의미: ");
gets(e.meaning);
insert_node(&root, e);
break;
case 'd':
printf("단어: ");
gets(e.word);
delete_node(&root, e);
break;
case 'p':
display(root);
printf("\n");
break;
case 's':
printf("단어: ");
gets(e.word);
tmp=search(root, e);
if(tmp!=NULL) printf("의미: %s\n", tmp->key.meaning);
break;
}
}while(command != 'q');
}
