본문 바로가기

프로그래밍 언어들/알고리즘

C언어 이진 탐색 트리(Binary Search Trees in C)

C언어 이진 탐색 트리(Binary Search Trees in C)

- 이진 탐색 트리는 각 노드가 객체인 연결된 데이터 구조로 표현된다.

- 각 노드를 기준으로 노드의 키 값보다 작은 값은 좌측, 큰 값은 우측으로 보낸다.

- 각 노드는 키 값 외에도 left, right, p의 포인터 변수를 포함한다.

- left, right는 자신의 자노드들을, p는 상위 노드를 가르킨다.

- root 노드는 유일하게 상위 노드가 없는 노드이다.


 

 [ Fig. 1 ] 이진 탐색 트리


1. 동작 원리

(1) root 노드를 가르키는 root 포인터를 선언하고 초기화 한다.

(2 - 1) 노드 삽입 명령 시 새로운 노드를 생성하고, 키 값을 입력한다.

(2 - 2) 현재 트리를 구성하고 있는 노드들의 키 값과 비교하여 노드를 삽입할 위치를 탐색한다.

(2 - 3) 위치를 탐색한 후에 새로 생성한 노드가 상위 노드를 가르키게 한다.

(2 - 4) 상위 노드가 새로 생성한 노드를 가르키게 한다.

(3 - 1) 노드 삭제 명령 시 제거할 키 값을 가진 노드의 위치를 탐색한다.

(3 - 2) 제거하려는 키 값을 가진 노드가 없을 경우 리턴한다.

(3 - 3) 제거하려는 노드가 자식 노드를 하나도 가지고 있지 않을 경우, 상위 노드가 NULL을 가르키게 하고 해당 노드를 제거한다.

(3 - 4) 제거하려는 노드가 하나의 자식을 가지고 있을 경우, 자식 노드의 키 값을 제거하려는 노드의 키 값에 대입한 후에 자식 노드를 제거한다.

(3 - 5) 제거하려는 노드가 두 개의 자식 노드를 가지고 있을 경우, 우측의 노드 중 가장 작은 키 값(=이진 탐색 트리의 특성 유지를 위해)을 가진 노드를 탐색하여 제거하려는 노드의 키 값에 대입 한 후에 탐색한 노드를 제거한다.

(4) DFS 특성을 이용하여 모든 노드(키 값)들을 출력한다.


2. 함수 설명

NODE* search_node( NODE *, int) : 어떤 키 값을 가진 노드를 탐색하여 반환해주는 함수
void insert_node( NODE **, int) : 어떤 키 값을 가진 노드를 생성해주는 함수로 동작원리 (2)에 해당한다.
void delete_node( NODE **, int) : 어떤 키 값을 가진 노드를 제거해주는 함수로 동작원리 (3)에 해당한다.
void display_node( NODE *) : DFS 탐색을 기준으로 모든 노드(키 값)을 출력한다.


3. 함수 구현

 

#include <stdio.h>
#include <malloc.h>

#define MAX 100

typedef struct node{
    int key;
    struct node *left;
    struct node *right;
    struct node *p;
}NODE;

NODE* search_node( NODE *, int);
void insert_node( NODE **, int);
void delete_node( NODE **, int);
void display_node( NODE *);

int main( void)
{
    NODE *root  = NULL;

    insert_node( &root, 50);
    insert_node( &root, 30);
    insert_node( &root, 70);
    insert_node( &root, 25);
    insert_node( &root, 40);
    insert_node( &root, 60);
    insert_node( &root, 80);
    insert_node( &root, 15);
    insert_node( &root, 35);
    insert_node( &root, 45);

    delete_node( &root, 30);
    delete_node( &root, 50);

    display_node( root);
    return 0;
}

/*
    search_node( NODE *, int)
    find the node that has the key.
*/

NODE* search_node( NODE *t, int key)
{
    while( t != NULL && t->key != key)
    {
        if( t->key > key)
        {
            t   = t->left;
        }
        else
        {
            t   = t->right;
        }
    }

    return t;
}

/*
    insert_node( NODE **, int)
    Insert the key in the tree.
*/

void insert_node( NODE **t, int key)
{
    NODE *n     = (NODE *)malloc(sizeof(NODE));
    NODE *temp  = *t; // temporary node.

    n->key  = key;
    n->p    = NULL;
    n->left = NULL;
    n->right= NULL;

    // if there is not any node.
    if( temp == NULL)
    {
        *= n;

        return;
    }

    // find the position that new node will be inserted.
    while( temp != NULL)
    {
        n->p    = temp;
       
        if( temp->key > key)
        {
            temp    = temp->left;
        }
        else
        {
            temp    = temp->right;
        }
    }

    // insert new node in the tree.
    if( (n->p)->key > key)
    {
        (n->p)->left = n;
    }
    else
    {
        (n->p)->right = n;
    }

}

/*
    delete_node( NODE **, int)
    After finding the key that you want,
    remove that from the tree.
*/

void delete_node( NODE **t, int key)
{
    NODE *temp  = NULL;
    NODE *p     = NULL;
   
    // find the node that has the key.
    temp    = search_node( *t, key);

    // if there is not key.
    if( temp == NULL)
    {
        printf("Can't find the key!\n");

        return;
    }

    // if the node that has the key don't have children.
    if( temp->left == NULL && temp->right == NULL)
    {
        if( temp == *t)
        {
            *= NULL;
        }
        else if( (temp->p)->key > key)
        {
            (temp->p)->left = NULL;
        }
        else
        {
            (temp->p)->right= NULL;
        }

        free(temp);
    }
    // if the node don't have a left child.
    else if( temp->left == NULL)
    {
        temp->key   = (temp->right)->key;
       
        delete_node( &(temp->right), (temp->right)->key);
    }
    // if the node don't have a right child.
    else if( temp->right == NULL)
    {
        temp->key   = (temp->left)->key;
       
        delete_node( &(temp->left), (temp->left)->key);
    }
    else // if the node have children.
    {
        p   = temp;

        temp    = temp->right;

        while(temp->left != NULL)
        {
            temp    = temp->left;
        }

        p->key  = temp->key;

        delete_node( &(p->right), temp->key);
    }
}

/*
    display_node( NODE *)
    display all nodes in the tree by depth first search(DFS).
*/

void display_node( NODE *t)
{
    if( t == NULL)
    {
        return;
    }

    printf("NODE [%d] > ", t->key);

    if( t->left != NULL)
    {
        printf("LEFT [%d] ", (t->left)->key);
    }
    if( t->right != NULL)
    {
        printf("RIGHT [%d]", (t->right)->key);
    }
    printf("\n");

    if( t->left)
    {
        display_node( t->left);
    }
    if( t->right)
    {
        display_node( t->right);
    }
}


 

4. 실행 결과