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)     {         *t  = 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)         {             *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. 실행 결과