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. 실행 결과
'프로그래밍 언어들 > 알고리즘' 카테고리의 다른 글
C언어 레드-블랙 트리 삭제 알고리즘(Red-Black Trees in C, deleting or removing algorithm) (0) | 2016.11.04 |
---|---|
C언어 레드-블랙 트리 삽입 알고리즘 (Red-Black Trees in C, insertion algorithm) (1) | 2016.11.04 |
C언어 원형 이중 연결리스트(Circular, doubly linked lists in C) (0) | 2016.10.27 |
C언어 이중 연결리스트(Doubly linked lists in C) (0) | 2016.10.27 |
C언어 단일 연결리스트(Singly linked lists in C) (0) | 2016.10.27 |