3. 이진 탐색 트리

이진 탐색 트리

이진 탐색 트리(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;
    }
}

---

- 이진 탐색 트리에서 삭제 연산

탐색 먼저 수행 -> 삭제하려는 키 값이 트리 안에 어디 있는지를 알아야 삭제할 수 있음

1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
3. 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우

 

첫 번째 경우: 삭제하려는 노드가 단말 노드일 경우

• 단말 노드의 부모 노드를 찾아서 부모 노드 안의 해당 링크 필드를 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);
}

---

- 이진 탐색 트리의 분석

• 이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 O(h)가 됨 -> 노드가 n개일 때 평균적인 시간 복잡도는 O(logn)
• 이진 탐색 트리에서 한쪽으로 치우치는 경사 이진 트리일 경우에는 O(n)의 시간 복잡도를 가짐(== 선형 탐색)
• 따라서 이 경우 선형 탐색에 비해 전혀 시간적 이득이 없으므로, 최악의 경우를 방지하기 위해서 트리의 높이를 ⌈logn⌉으로 한정시키는 균령 기법이 필요(트리를 균형 있게 만드는 기법으로 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');
}