[C언어] 이진 탐색 트리(Binary Search Tree, BST)

[C언어] 이진 탐색 트리(Binary Search Tree, BST)

 

이진 탐색 트리란 이진 탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조의 일종이다. 이진 탐색의 효율적인 탐색 능력(O(log n)은 유지하면서 자료 입력과 삭제가 효율적으로(O(1)) 가능하다.

 

 

이진 탐색 트리 특징

 

• 각 노드에 값이 있다.
• 값들은 전순서가 있다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

 

이진 탐색 트리 기능

 

• 검색, 추가, 삭제, 최솟값 찾기

 

코드

 

#include <stdio.h>
#include <stdlib.h>

typedef int key_t;

typedef struct node_t{ // 트리를 구성하는 노득 ㅜ조체
    key_t key; // 값
    struct node_t *left, *right; // 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드
} node_t;

typedef struct rbtree{
    node_t *t;
} rbtree;

// 재귀를 이용한 출력 함수
void show(node_t *t) // 중위 순회 출력하는 함수
{
    if (t == NULL){ // NULL인 경우 return
        return;
    }
    if (t->left != NULL){
        show(t->left);
    }
    printf("%d\n", t->key);
    
    if (t->right != NULL){
        show(t->right);
    }
}


node_t *newNode(int k){ // 노드 생성 함수
    node_t *t = malloc(sizeof(node_t));
    t->left = NULL;
    t->right = NULL;
    t->key = k;
    return t; 
}

void freeNode(node_t *t){ // 메모리 해제하는 함수
    if (t == NULL)
     {
         return;
         }

    freeNode(t->left);
    free(t);
    freeNode(t->right);    
}
 
//재귀를 이용한 삽입
node_t *insert(node_t *t, key_t k) // 트리에 삽입하는 함수, 트리의 root와 newNode 값 k를 받음
{
    if (t == NULL){
        return newNode(k);
        }
        
    if(t->key < k){ // k값이 더 클 때
        t->right = insert(t->right,k);
    } else if(t->key > k){ // k 값이 더 작을 때
        t->left = insert(t->left,k);
    }
    return t;
}


// // 반복문을 이용한 삽입, 추가 구조체 정의가 필요
// node_t *insert(node_t *t, key_t k){ // 트리에 삽입하는 함수, 트리의 root와 newNode 값 k를 받음
//     if (t == NULL){
//         return newNode(k);
//         }
        
//     node_t *curr = malloc(sizeof( node_t));
//     curr = t;
//     while (t != NULL){
//         if(t->key < k){ // k값이 더 클 때
//             if (t->right == NULL){
//                 t->right = newNode(k);
//                 t = t->right;
//             }
//             t = t->right;
//         } else if(t->key > k){ // k 값이 더 작을 때
//             if (t->left == NULL){
//                 t->left = newNode(k);
//                 t = t->left;
//             }
//             t = t->left;
//         }
//     } return curr;
// }

node_t *search(node_t *t, key_t k){ // 해당 key값을 가지는 노드 검색
    if (t == NULL) return t;
    if (t->key == k){
        printf("found!\n");
        return t;}
    if (t->key < k) return search(t->right, k);
    if (t->key > k) return search(t->left, k);
}

node_t *minnode(node_t *t){ // 해당 key값보다 작은 값을 가진 노드 찾기
    node_t *min = t;
    while (min->left != NULL) min = min->left; // 같은 줄이면 {}가 없어도 됨
    return min;
}


// 제거
node_t *deletenode(node_t *t, key_t k){
    if (t == NULL); return t; // return t 이해
    
    if (t->key < k){
        t->right = deletenode(t->right, k);
    } else if( t-> key > k){
        t->left = deletenode(t->left, k);
    }
    node_t *tmp = malloc(sizeof(node_t)); // 이거 위치 ...
    // 자식 노드가 1개 있는 경우
    if (t->right == NULL){ // 왼쪽 자식 o
        tmp = t->left;
        free(t); // target t node 제거
        return tmp;
    } else if(t-> left == NULL){ //오른쪽 자식 o
        tmp = t->right;
        free(t); // target t node 제가
        return tmp;
    }else{ // 자식 노드가 2개 있는 경우
        tmp = minnode(t->right);
        t->key = tmp->key;
        t->right = deletenode(t->right, tmp->key); // 이거 이해하기

    }
}

int main()
{
    // rbtree *head = malloc(sizeof(node_t)); // head로 트리와 연결하는 부분
    node_t *tree = NULL; // 트리부분
 
    tree = insert(tree, 10);
    tree = insert(tree, 7);
    tree = insert(tree, 50);
    tree = insert(tree, 30);
    tree = insert(tree, 40);
    tree = insert(tree, 15);
    tree = insert(tree, 55);

/////////////////////////
//
//          10
//         / \
//        7   50
//            / \
//          30   55
//         /  \
//       15    40
//
/////////////////////////

    show(tree);
    search(tree, 15);
    printf("min value : %d\n", minnode(tree->right)->key); // 최솟값 출력
    deletenode(tree, 10);
    show(tree);
}

 

감성코딩 블로그 참조