[자료구조] 이진탐색트리(Binary Search Tree)란? - 컴도리돌이

 

이진 탐색 트리(Binary Search Tree)란?

 

이진트리 기반의 탐색을 위한 자료 구조로 효율적인 탐색 작업을 할 때 사용하는 자료 구조입니다.

 

이진 탐색 트리(Binary Search Tree)의 정의

 

 

이진탐색트리(Binary Search Tree)의 정의

-모든 노드는 유일한 키를 갖는다.

-왼쪽 서브 트리 키들은 루트 키보다 작다.

-오른쪽 서브 트리의 키들은 루트의 키보다 크다.

-왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

-탐색작업을 효율적으로 하기 위한 자료구조

 

이진 탐색 트리(Binary Search Tree)의 탐색 그림 예시 && C언어 코드

 

 

이진탐색트리(Binary Search Tree)의 탐색 그림 예시

 

-비교한 결과가 같으면 탐색이 성공적으로 끝난다.

-키 값이 루트보다 작은면 왼쪽 자식을 기준으로 다시 탐색

-키 값이 루트보다 크면 오른쪽 자식을 기준으로 다시 탐색

 

이진탐색트리(Binary Search Tree)의 탐색 C언어 코드

 

이진 탐색 트리(Binary Search Tree)의 삽입 연산 그림 예시 && C언어 코드

 

 

이진탐색트리(Binary Search Tree)의 삽입 그림 예시

 

먼저 탐색을 수행하며 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치라고 생각하면 됩니다.

 

이진탐색트리(Binary Search Tree)의 삽입 C언어 코드

 

이진 탐색 트리(Binary Search Tree)의 삭제 연산 그림 예시 && C언어 코드

 

노드 삭제의 3가지 경우

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

case 1 : 단말 노드 삭제

이진탐색트리(Binary Search Tree)의 삭제 case 1 그림 예시

 

단말 노드의 부모 노드를 찾아서 연결을 끊으면 된다. 단말 노드를 가리키는 부모 노드의 링크를 null로 저장하면 됩니다.

 

 

case 2 : 자식이 하나인 노드 삭제

이진탐색트리(Binary Search Tree)의 삭제 case 2 그림 예시

 

노드는 삭제하고 서브 트리는 부모 노드에 붙여줍니다.

 

 

case 3 : 두 개의 자식을 가진 노드 삭제

이진탐색트리(Binary Search Tree)의 삭제 case 3 그림 예시

 

자식을 두 개를 가진 노드를 삭제할 경우 그림으로 보이는 것처럼 오른쪽 서브 트리에서 제일 작은 값이거나 왼쪽 서브 트리에서 제일 큰 값을 삭제할 노드에 덮어 씌어주고 그 값을 삭제를 합니다.

 

 

이진탐색트리(Binary Search Tree)의 삭제 C언어 코드

이진탐색트리(Binary Search Tree)의 삭제 C언어 코드

 

 

 

 

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

typedef int Telement;
typedef struct binaryTreeNode
{
    Telement data;
    struct binaryTreeNode *left;
    struct binaryTreeNode *right;
}TNode;


typedef struct LinkedNode
{
    TNode* data;
    struct LinkedNode* link;
}Node;

Node* front = NULL;
Node* rear = NULL;
TNode* ROOT;

void error(char* str)
{
    fprintf(stderr,"%s\n",str);
    exit(1);
}

int is_empty(){ return front == NULL;}
void init_queue() { front = rear = NULL;}

int size()
{
    Node *p;
    int count = 0;
    for(p = front; p!= NULL; p=p->link) count++;
    return count;
}

void enqueue(TNode* e)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->link = NULL;

    if(is_empty()) front = rear = p;
    else
    {
        rear->link = p;
        rear = p;
    }
}

TNode* dequeue()
{
    Node* p;
    TNode* e;

    if(is_empty())
        error("큐 공백 에러");
    p = front;
    front = front->link;
    if(front == NULL) rear = NULL;
    e = p->data;
    free(p);
    return e;
}

void init_tree(){ROOT = NULL;}
int is_empty_tree() { return ROOT == NULL;}
TNode* get_root() { return ROOT; }

TNode* create_tree(Telement val,TNode* left,TNode* right)
{
    TNode* n = (TNode*)malloc(sizeof(TNode));
    n->data = val;
    n->left = left;
    n->right = right;
    return n;
}

void preorder(TNode* n)
{
    if(n != NULL)
    {
        printf("[%d] ",n->data);
        preorder(n->left);
        preorder(n->right);
    }
}
void inorder(TNode *n)
{
    if(n != NULL)
    {
        inorder(n->left);
        printf("[%d] ",n->data);
        inorder(n->right);
    }
}
void postorder(TNode* n)
{
    if(n != NULL)
    {
        postorder(n->left);
        postorder(n->right);
        printf("[%d] ",n->data);
    }
}

void levelorder(TNode* root)
{
    TNode* n;
    if(root == NULL) return;
    init_queue();
    enqueue(root);
    while(!is_empty())
    {
        n = dequeue();
        if(n != NULL)
        {
            printf("[%d] ",n->data);
            enqueue(n->left);
            enqueue(n->right);
        }
    }
}

int count_node(TNode* n)
{
    if(n == NULL) return 0;
    return 1 + count_node(n->left) + count_node(n->right);
}

int count_leaf(TNode* n)
{
    if(n == NULL) return 0;
    if(n->left == NULL && n->right == NULL) return 1;
    else return count_leaf(n->left) +count_leaf(n->right);
}

int calc_height(TNode* n)
{
    int hleft,hright;
    if(n == NULL) return 0;
    hleft = calc_height(n->left);
    hright = calc_height(n->right);
    return (hleft > hright) ? hleft + 1 : hright + 1;
}

TNode* search(TNode *n, Telement key)
{
    if(n==NULL) return NULL; //key값을 가진 node를 찾지 못할경우 null 값을 반환한다.
    else if( key == n->data ) return n; //key값을 가진 노드를 발견할 경우 해당 노드를 반환한다.
    else if( key < n->data ) return search(n->left,key); //이진트리의 특성을 갖고 있으며 해당 노드의 key값보다 작으면 왼쪽 서브트리를 탐색
    else return search(n->right,key); //key값보다 클 경우 오른쪽 서브트리를 탐색
}

void search_BST(Telement key)
{
    TNode* n = search(ROOT,key); //root 부터 방문하여 key값을 가진 node를 찾는다.
    if( n!= NULL) printf("[탐색 연산] : 성공 [%d] = 0x%x\n",n->data,n); //탐색 성공
    else printf("[탐색 실패] : 실패 no %d\n",key); // 탐색 실패
}

void insert_BST(Telement key)
{
    TNode* node = create_tree(key,NULL,NULL); //key을 가진 새로운 노드를 동적할당하여 만들어 준다.
    if(is_empty_tree()) ROOT = node; //전역변수로 선언한 root가 null값일 경우 처음 삽입한 key을 가진 노드가 root노드가 된다.
    else if(insert(ROOT,node) == 0) free(node); //root노드를 가진 경우 insert 함수로 이동
}

Telement insert(TNode* root,TNode* insert_node)
{
    if(insert_node->data == root->data) return 0; //만약 이진트리에 key값을 가진 노드가 있을경우 반환값을 0으로 처리
    else if(insert_node->data < root->data) //삽입할 노드의 값이 루트노드보다 작을 경우
    {
        if(root->left == NULL) root->left = insert_node; //루트노드의 왼쪽 자식 노드가 비어있을 경우 왼쪽 자식 노드에 삽입
        else insert(root->left,insert_node); //왼쪽 노드가 있을 경우 다시 순환 재귀함수로 부모노드를 루트의 왼쪽노드로 설정한다.
    }
    else //삽입할 노드의 값이 루트노드보다 클 경우
    {
        if(root->right == NULL) root->right = insert_node; 
        else insert(root->right,insert_node);
    }
    return 1;
}




void delete(TNode *parent,TNode* delete_node)
{
    TNode *child, *succ, *succp;

    //case 1 : 삭제할 노드가 자식을 갖지 않는 단말 노드일 경우
    if((delete_node->left == NULL && delete_node->right == NULL))
    {
        if(parent == NULL) ROOT = NULL; //부모 노드가 null 값이란 뜻은 삭제할 노드가 루트 노드 또는 없을 경우이기 때문에 null값을 반환
        else
        {
            if(parent->left == delete_node) parent->left = NULL; //부모 노드의 왼쪽노드와 삭제할 노드가 같을 경우 null 값 처리
            else parent->right = NULL; // 오른쪽노드와 같을경우 null 값 처리
        } 
    }

    //case 2 : 삭제할 노드가 자식이 하나를 갖는 경우
    else if(delete_node->left == NULL || delete_node->right == NULL)
    {
        child = (delete_node->left != NULL) ? delete_node->left : delete_node->right; // 삭제할 노드가 가진 자식노드를 찾는다.
        if(delete_node == ROOT) ROOT = child; //삭제할 노드가 루트 노드일 경우 루트노드를 자식 노드로 설정
        else
        {
            if(parent->left == delete_node) parent->left = child; //자식이 하나밖에 없으므로 삭제할 노드를 해당 자식노드에 넣어준다.
            else parent->right = child;
        }
    }
    //case 3
    else
    {
        succp = delete_node; //삭제할 노드를 부모로 설정
        succ = delete_node->right; //삭제할 노드의 오른쪽 자식 노드로 설정
        while (succ->left != NULL) //오른쪽 자식노드의 왼쪽 자식노드를 찾는다.(그림예시참고)
        {
            succp = succ;
            succ = succ->left;
        }
        if(succp->left == succ) succp->left = succ->right; //삭제할 노드의 자식노드의 왼쪽 자식노드를 삭제과정
        else succp->right = succ->right;

        delete_node->data =succ->data; //삭제할 노드의 자식노드의 왼쪽 자식노드를 삭제할 노드로 설정(이진트리의 구조를 깨지 않기위해서 (그림예시참고))
        delete_node = succ;
    }
    free(delete_node);
}


void delete_BST(Telement key)
{
    TNode* parent = NULL; //삭제할 노드의 부모노드를 NULL값으로 할당
    TNode* node = ROOT; //삭제할 노드를 처음에 루트노드로 설정

    if(node == NULL) return; //만약 루트노드가 없을 경우 바로 null값을 반환
    while (node != NULL && node->data != key) //루트노드가 존재하고 삭제할 key값을 가진 노드를 찾을 때까지 반복
    {
        parent = node; //부모노드를 루트노드부터 시작
        node = (key< node->data) ? node->left :node->right; //해당 key값이 부모 노드기준으로 작을 경우 클 경우에 따라서 설정
    }
    if(node == NULL)
        printf("error : key is not in the tree \n");
    else delete(parent,node); //부모노드와 삭제할 노드를 delete 함수에 넣어준다.
}