이진 탐색 트리
이진 탐색 트리(binary search tree)
: 이진 트리 기반의 탐색을 위한 자료 구조
탐색(search)
: 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미
레코드(record)
: 하나 이상의 필드(field)로 구성
테이블(table)
: 레코드(record)들의 집합
주요 키(primary key)
: 각각의 레코드를 구별할 수 있는 키
- 탐색 작업을 할 때 주요 키가 입력이 되어 특정한 키를 가진 레코드를 찾게 됨
- 이진 탐색 트리는 이러한 탐색 작업을 효율적으로 하기 위한 자료구조
- 이진 탐색 트리의 정의
이진 탐색 트리: 이진 탐색 트리의 성질을 만족하는 이진 트리
<정의 7.7.1> 이진 탐색 트리
- 모든 노드 키는 유일함
- 왼쪽 서브 트리의 키들은 루트의 키보다 작음
- 오른쪽 서브 트리의 키들은 루트의 키보다 큼
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리임- 찾고자 하는 키 값 < 루트 노드의 키 값: 왼쪽 서브 트리에 존재 / 찾고자 하는 키 값 > 루트 노드의 키 값: 오른쪽 서브 트리에 존재
- 이진 탐색 트리를 중위 순회 방법으로 순회하면 숫자들이 크기 순이 됨
- 탐색 연산
탐색 연산
: 이진 탐색 트리에서 특정 키 값을 가진 노드를 찾는 것
주어진 탐색 키 값과 현재 루트 노드의 키 값 비교
- 비교한 결과가 같으면 탐색이 성공적으로 끝남
주어진 키 값이 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작
주어진 키 값이 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작
<알고리즘 7.7.1> 이진 탐색 트리 탐색 알고리즘(순환적)
search(x,k)
if x = NULL
then return NULL;
if k = x->key
then return x;
else if k < x->key
then return search(x->left,k);
else return search(x->right,k);
이진 탐색 트리가 공백 상태이면
그냥 복귀
탐색 키가 현재 트리의 루트 키 값과 같으면
루트를 반환
탐색 키가 루트 키 값보다 작으면
왼쪽 서브 트리를 순환 호출을 이용하여 계속 탐색
그렇지 않으면 오른쪽 서브 트리를 순환 호출을 이용하여 계속 탐색typedef struct TreeNode{
int key;
struct TreeNode *left, *right;
} TreeNode;
<프로그램 7.7.1> 순환적인 탐색 함수
// 순환적인 탐색 함수
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 search(node->right, key); // 오른쪽 자식 노드를 매개변수로 넣어 함수 순환 호출
}
}
<프로그램 7.7.2> 반복적인 탐색 함수
// 반복적인 탐색 함수
TreeNode *search(TreeNode *node, int key){
while(node != NULL){
if(key == node->data) return node;
else if(key < node->data){
node = node->left;
}else{
node = node->right;
}
}
return NULL; // 탐색에 실패했을 경우 NULL 반환
}==> 반복적인 방법이 더 효울적임
- 이진 탐색 트리에서 삽입 연산
탐색 먼저 수행 -> 이진 탐색 트리에서 같은 키 값을 가진 노드가 없어야 하기 때문 + 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치가 됨
- 탐색이 성공하면 탐색 키가 중복되는 것이므로 삽입이 불가능
- 탐색이 실패하면 실패로 끝난 위치에 새로운 키 삽입
<알고리즘 7.7.2> 이진 탐색 트리 삽입 알고리즘(자연어 버전)
insert_node(T, z)
1. 트리 T에서 z에 대한 탐색을 먼저 수행
2. 탐색이 실패하면 탐색이 띁난 지점에 노드 z를 삽입
<알고리즘 7.7.3> 이진 탐색 트리 삽입 알고리즘(유사 코드)
insert_node(T, key)
p <- NULL;
t <- T;
while t != NULL do // 탐색을 수행
p <- t;
if key < p->key
then t <- p->left
else t <- p->right
z <- make_node(key);
if p = NULL
then T <- z; // 트리가 비어 있음
else if key < p->key
then p->left <- z
else p->right <- z
p는 부모 노드 포인터
t는 탐색을 위한 포인터
t가 NULL이 될 때까지 탐색을 수행함
현재 탐색 포인터의 값을 부모 노드 포인터에 복사
삽입할 키 값이 t의 키 값보다 작으면 왼쪽 자식 노드로 탐색 진행
삽입할 키 값이 t의 키 값보다 크면 오른쪽 자식 노드로 탐색 진행
key를 포함하는 트리 노드 생성
반복이 끝났고, 만약 부모 노드가 NULL이면 현재 트리가 공백 상태. 따라서, 새로운 노드를 루트로 설정
부모 노드의 키 값과 비교하여 작으면 왼쪽 자식으로 연결함. 그렇지 않으면 오른쪽 자식으로 연결
<프로그램 7.7.3> 이진 트리 삽입 프로그램
// key를 이진 탐색 트리 root에 삽입
// key가 이미 root 안에 있으면 삽입되지 않음
void insert_node(TreeNode **root,int key){
TreeNode *p, *t; // p는 부모 노드, t는 현재 노드
TreeNode *n; // n은 새로운 노드
t = *root;
p = NULL;
// 탐색을 먼저 수행
while(t != NULL){
if(key == t->data){
return; // 이미 존재
}
p = t;
if(key < p->key) t = p->left;
else t = p->right;
}
// key가 트리 안에 없으므로 삽입 가능
// 트리 노드 구성
n = (TreeNode *)malloc(sizeof(TreeNode));
if(n == NULL) error("memory allocate error");
// 데이터 복사
n->key= key;
n->left = n->right = NULL;
// 부모 노드와 연결
if( p!= NULL){
if(key < p->key){
p->left = n;
}else{
p->right = n;
}
}else{
*root = n;
}
}- 이진 탐색 트리에서 삭제 연산
탐색 먼저 수행 -> 삭제하려는 키 값이 트리 안에 어디 있는지를 알아야 삭제할 수 있음
- 삭제하려는 노드가 단말 노드일 경우
- 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
- 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우
첫 번째 경우: 삭제하려는 노드가 단말 노드일 경우
- 단말 노드의 부모 노드를 찾아서 부모 노드 안의 해당 링크 필드를 NULL로 만들어 연결을 끊으면 됨
- 다음으로 만약 노드를 동적을 생성했다면 동적 메모리 해제시키면 됨
두 번쨰 경우: 삭제하려는 노드가 하나의 서브 트리만 가지고 있는 경우
- 자기 노드는 삭제
- 그 서브 트리를 자기 노드의 부모 노드가 가리키게하면 됨
세 번째 경우: 삭제하려는 노드가 두 개의 서브 트리를 가지고 있는 경우
- 왼쪽 자식과 오른쪽 자식 중 어떤 노드를 삭제 노드 위치로 가져와야 하는지 생각해야 함 -> 삭제되는 노드와 값이 가장 비슷한 노드를 선택해야 함
- 왼쪽 서브 트리에서 가장 큰 값(왼쪽 서브 트리의 가장 오른쪽)이나 오른쪽 서브 트리에서 가장 작은 값(오른쪽 서브 트리의 가장 왼쪽)이 삭제되는 노드와 가장 가깝기 때문에 후계자 대상 노드가 됨
- 후계장 대상 노즈 중에서는 어느 노드를 선택해도 상관 없음
<프로그램 7.7.4> 이진 탐색 트리에서의 삭제 함수
// 삭제 함수
// 루트 노드 포인터의 포인터로 전달한 이유는 루트 노드가 삭제되거나 변경될 수 있기 때문
void delete_node(TreeNode **root, int key){
TreeNode *p, *t, *succ, *succ_p; // 부모 노드, 현재 노드, 후계자 노드, 후계자 노드의 부모
TreeNode *child;
// key를 갖는 노드 t를 탐색, p는 t의 부모
p = NULL;
t = *root;
// key를 갖는 노드 t를 탐색
while(t!=NULL && t->key != key){
p = t;
t = (key < p->key) ? p->left : p->right;
}
// 탐색이 종료된 시점에 t가 NULL이면 해당 key가 이진 트이 안에 없는 것을 의미
if(t == NULL){
printf("key is not in the tree\n");
return;
}
// 첫 번째 경우: 단말 노드의 경우
if((t->left == NULL) && (t->right == NULL)){
if(p!=NULL){
// 부모 노드의 자식 필드를 NULL로 만듦
if(p->left == t){
p->left = NULL;
}else{
p->right = NULL;
}
}else{ // 만약 부모 노드가 NULL이면 삭제되는 노드가 루트
*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{ // 부모 노드가 NULL이면 삭제되는 노드가 루트
*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);
}- 이진 탐색 트리의 분석
- 이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 라고 했을 때 가 됨 -> 노드가 n개일 때 평균적인 시간 복잡도는
- 이진 탐색 트리에서 한쪽으로 치우치는 경사 이진 트리일 경우에는 의 시간 복잡도를 가짐(== 선형 탐색)
- 따라서 이 경우 선형 탐색에 비해 전혀 시간적 이득이 없으므로, 최악의 경우를 방지하기 위해서 트리의 높이를 으로 한정시키는 균령 기법이 필요(트리를 균형 있게 만드는 기법으로 AVL 트리를 비롯한 여러 기법들이 개발됨)
이진 탐색 트리의 응용: 영어 사전
- 영어 단어와 그 의미가 저장된 구조체 필요
// 데이터 타입
typedef struct{
char word[MAX_WORD_SIZE]; // 키 필드
char meaning[MAX_MEANING_SIZE];
} element;
// 노드의 구조
typedef struct TreeNode{
element item;
struct TreeNode *left, *right;
}TreeNode;- 두 개의 element를 항목 순서를 비교하는 compare 함수가 필요함
- compare(e1,e2) 함수는 e1과 e2를 알파벳 순서로 비교하여 e1이 e2보다 작으면 -1, 같으면 0, 크면 1을 반환시킴
// 만약 e1 < e2 -> -1 반환
// 만약 e1 = e2 -> 0 반환
// 만약 e1 > e2 -> 1 반환
int compare(element e1, element e2){
return strcmp(e1.word, e2.word);
}<프로그램 7.8.1> 이진 탐색 트리를 이용한 영어 사전 프로그램
// 이진 탐색 트리를 사용한 영어 사전
#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;
// 만약 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){
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; // 탐색에 실패했을 경우 NULL 반환
}
// key를 이진 탐색 트리 root에 삽입함
// key가 이미 root안에 있는 경우 삽입되지 않음
void insert_node(TreeNode **root, element key){
TreeNode* p, *t; // p는 부모 노드, t는 자식 노드
p = NULL;
t = *root;
// 탐색을 먼저 수행
while(t!=NULL){
p = t;
if(compare(key, t->key) == 0 )
return; // 이미 존재
else if(compare(key,t->key) < 0)
t = t->left;
else
t = t->right;
}
// item이 트리 앖에 없으므로 삽입 가능
TreeNode* n = (TreeNode*)malloc(sizeof(TreeNode)); // n은 새로운 노드
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, *t;
p = NULL;
t = *root;
while(t != NULL){
p = t;
t = (compare(key, t->key) < 0) ? t->left : t->right;
}
// 탐색 트리에 없는 키
if(t == NULL){
printf("key is not in the tree\n");
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)) {
TreeNode* 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 {
// 오른쪽 서브 트리의 후속자를 찾음
TreeNode *succ, *succ_p;
succ_p = t;
succ = t->right;
// 후속자를 찾아서 계속 왼쪽으로 이동
while (t->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: input\n");
printf("d: delete\n");
printf("s: search\n");
printf("p: print\n");
printf("q: quit\n");
printf("*****************\n");
}
// 이진 탐색 트리를 사용하는 영어 사전 프로그램
int main(){
char command;
element e;
TreeNode* root = NULL;
TreeNode* tmp;
do{
help();
command = getchar();
fflush(stdin);
switch (command)
{
case 'i':
printf("Word: ");
gets(e.word);
printf("Meaning: ");
gets(e.meaning);
insert_node(&root, e);
break;
case 'd':
printf("Word: ");
gets(e.word);
delete_node(&root, e);
break;
case 's':
printf("Word: ");
gets(e.word);
tmp = search(root, e);
if( tmp != NULL){
printf("Meaning: %s\n", e.meaning);
}
break;
case 'p':
display(root);
printf("\n");
break;
}
} while (command != 'q');
}
'자료구조와 알고리즘 ft. 수업 > 알고리즘 정리' 카테고리의 다른 글
| 8. 연결 리스트로 구현한 큐 (0) | 2023.04.20 |
|---|---|
| 7. 연결 리스트로 구현한 스택 (0) | 2023.04.20 |
| 5. 덱의 응용 : 미로 탐색 프로그램 ft. C++ (0) | 2023.04.18 |
| 4. 큐의 응용 (0) | 2023.04.18 |
| Array (배열) (0) | 2023.04.09 |