1. 이진 탐색 트리란?
모든 노드가 아래의 조건을 만족하는 트리 자료구조이다.
key(왼쪽서브트리)≤key(루트노드)≤key(오른쪽서브트리)
- 따라서 이진 탐색 트리를 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.
1) 기본 코드
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct TreeNode {
element key;
struct TreeNode *left, *right;
} TreeNode;
TreeNode * search(TreeNode * node, element key)
{
if (node == NULL) return NULL;
if (key == node->key) return node;
else if (key < node->key)
return search(node->left, key);
else
return search(node->right, key);
}
TreeNode * new_node(element item)
{
TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode * insert_node(TreeNode * node, element key)
{
if (node == NULL) return new_node(key);
if (key < node->key)
node->left = insert_node(node->left, key);
else if (key > node->key)
node->right = insert_node(node->right, key);
return node;
}
TreeNode * min_value_node(TreeNode * node)
{
TreeNode * current = node;
while (current->left != NULL)
current = current->left;
return current;
}
TreeNode * delete_node(TreeNode * root, element key)
{
if (root == NULL) return root;
if (key < root->key)
root->left = delete_node(root->left, key);
else if (key > root->key)
root->right = delete_node(root->right, key);
else {
if (root->left == NULL) {
TreeNode * temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
TreeNode * temp = root->left;
free(root);
return temp;
}
TreeNode * temp = min_value_node(root->right);
root->key = temp->key;
root->right = delete_node(root->right, temp->key);
}
return root;
}
void preorder1(TreeNode * root) {
if (root) {
printf("%d ", root->key);
preorder1(root->left);
preorder1(root->right);
}
}
int max(int a, int b){
if(a >= b)
return a;
else
return b;
}
int get_height(TreeNode *root){
int height = 0;
if(root != NULL){
height = 1 + max(get_height(root->left), get_height(root->right));}
return height;
}
int get_node(TreeNode *root){
int count=0;
if(root != NULL){
count = 1 + get_node(root->left) + get_node(root->right);
}
return count;
}
int get_max(TreeNode *root){
TreeNode * tmp = root;
while(tmp->right != NULL){
tmp = tmp->right;
}
return tmp->key;
}
int get_min(TreeNode *root){
TreeNode * tmp = root;
while(tmp->left != NULL){
tmp = tmp->left;
}
return tmp->key;
}
int main(void)
{
TreeNode * root = NULL;
char res;
int value;
printf("Enter i<nsert>,d<elete>,s<earch>,p<rint>,h<eight>,c<ount>,m<ax>,n<min>,q<uit>:");
scanf("%c", &res);
while(res != 'q'){
switch (res) {
case 'i':
printf("삽입할 값 입력:");
scanf("%d", &value);
root = insert_node(root, value);
break;
case 'd':
printf("삭제할 값 입력:");
scanf("%d", &value);
root = delete_node(root, value);
break;
case 's':
printf("탐색할 key값 입력:");
scanf("%d", &value);
if(search(root, value) == NULL)
printf("없음\n");
else
printf("있음\n");
break;
case 'p':
preorder1(root);
printf("\n");
break;
case 'h':
printf("트리의 높이는 %d\n", get_height(root));
break;
case 'c':
printf("노드의 개수는 %d\n", get_node(root));
break;
case 'm':
printf("가장 큰 값은 %d\n", get_max(root));
break;
case 'n':
printf("가장 작은 값은 %d\n", get_min(root));
break;
default:
break;
}
fflush(stdin);
printf("Enter i<nsert>,d<elete>,s<earch>,p<rint>,h<eight>,c<ount>,m<ax>,n<min>,q<uit>:");
scanf("%c", &res);
}
return 0;
}
2) 삽입 연산
TreeNode * new_node(element item)
{
TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode * insert_node(TreeNode * node, element key)
{
if (node == NULL) return new_node(key);
if (key < node->key)
node->left = insert_node(node->left, key);
else if (key > node->key)
node->right = insert_node(node->right, key);
return node;
}
- 삽입하려는 값이 기준 노드의 값보다 작으면 기준 노드를 왼쪽으로, 크면 기준 노드를 오른쪽 노드로 이동한다.
- 그러다가 트리의 끝에 도달하면 new_node(); 함수를 사용하여 노드를 삽입해준다.
- 만약, 이미 똑같은 값이 있다면 기존의 트리를 반환할 것이다.
3) 삭제 연산
삭제하려는 노드의 상황은 세 가지가 있다.
① 삭제하려는 노드가 단말 노드인 경우
② 삭제하려는 노드가 하나의 왼쪽 혹은 오른쪽 서브 트리 중 하나만 갖고 있는 경우
③ 삭제하려는 노드가 두 개의 서브 트리를 모두 갖고 있는 경우
CASE ①
: 단말 노드이기 때문에 자기 자신과 부모 트리에만 조치를 해 주면 된다.
CASE ②
: 삭제되는 노드가 왼쪽이나 오른쪽 서브 트리 하나만 가지고 있을 때, 그 노드는 삭제하고 서브 트리를 부모 노드에 붙여준다.
case ③
: 삭제 노드와 가장 비슷한 값을 가진 노드를 삭제 위치로 가져온다. 여기서 비슷한 값은 아래 트리에서 12나 22처럼 왼쪽 서브트리에서 가장큰 수이거나 오른쪽 서브트리에서 가장 작은 수이다.
TreeNode * delete_node(TreeNode * root, element key)
{
if (root == NULL) return root;
if (key < root->key)
root->left = delete_node(root->left, key);
else if (key > root->key)
root->right = delete_node(root->right, key);
else {
if (root->left == NULL) { // 단말노드, 오른쪽만 있는 노드
TreeNode * temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) { // 왼쪽만 있는 노드
TreeNode * temp = root->left;
free(root);
return temp;
}
TreeNode * temp = min_value_node(root->right);
root->key = temp->key;
root->right = delete_node(root->right, temp->key);
}
return root;
}
- 기준 노드의 값보다 작으면 왼쪽 노드를, 크면 오른쪽 노드를 반환한다.
- 그러다가 기준 노드의 값과 삭제할 값이 같으면 !
① 단말노드, 오른쪽 서브트리만 있는 노드는
해당 노드는 삭제하고 오른쪽 서브트리를 부모에게 전달한다.
② 왼쪽 서브트리만 있는 노드는
해당 노드는 삭제하고 왼쪽 서브트리를 부모에게 전달한다.
③ 왼쪽, 오른쪽 서브트리가 모두 있는 노드는
오른쪽 서브트리에서의 제일 작은 값을 현재 노드 값으로 설정하고,
오른쪽 서브트리에 내려가서 제일 작은 값을 가지는 노드를 삭제한다.
4) 검색 연산
TreeNode * search(TreeNode * node, element key)
{
if (node == NULL) return NULL;
if (key == node->key) return node;
else if (key < node->key)
return search(node->left, key);
else
return search(node->right, key);
}
- 기준 노드의 값보다 찾는 값이 작으면 왼쪽 서브트리를 반환, 크면 오른쪽 서브트리를 반환한다.
- 값이 같으면 해당 노드를 반환한다.
5) 기타 연산
: 전위 순회, 트리의 높이 구하기, 노드의 개수, 제일 큰 값, 제일 작은 값
void preorder1(TreeNode * root) {
if (root) {
printf("%d ", root->key);
preorder1(root->left);
preorder1(root->right);
}
}
int get_height(TreeNode *root){
int height = 0;
if(root != NULL){
height = 1 + max(get_height(root->left), get_height(root->right));}
return height;
}
int get_node(TreeNode *root){
int count=0;
if(root != NULL){
count = 1 + get_node(root->left) + get_node(root->right);
}
return count;
}
int get_max(TreeNode *root){
TreeNode * tmp = root;
while(tmp->right != NULL){
tmp = tmp->right;
}
return tmp->key;
}
int get_min(TreeNode *root){
TreeNode * tmp = root;
while(tmp->left != NULL){
tmp = tmp->left;
}
return tmp->key;
}- 트리의 높이 구하기 : 왼쪽 서브트리와 오른쪽 서브트리 중 더 높이가 높은 길이를 반환한다.
- 노드의 총 개수 구하기 : 루트에서 오른쪽, 왼쪽 내려가면서 NULL 이 아니면 1씩 더해서 총 노드의 개수를 구한다.
2. 이진 탐색 트리 성능 분석
1) 연산의 속도는 트리의 높이 h에 비례한다.
2) 최선의 경우 시간 복잡도 : O(log n)
3) 최악의 경우 시간 복잡도 : O(n)
3. 이진 트리의 성질
1) 노드의 개수가 n개이면, 간선의 개수는 n-1개 이다.
2) 높이가 h인 이진트리의 경우,
최소 h개의 노드를 가지며, 최대 2^h - 1 개의 노드를 가진다.
3) n개의 노드를 가지는 트리의 높이는
최대 n이고, 최소 [log(n+1)] 이다. -> 올림 기호
4) 포화 이진 트리(각 레벨에 노드가 꽉 차있는 이진트리)의 전체 노드 개수는
2^k - 1
-> k 는 높이
4. 트리의 용어
1) 단말 노드 : 자식이 없는 노드
2) 비단말 노드 : 적어도 하나의 자식을 가진 노드
3) 레벨 : 트리 각 층의 번호
4) 높이 : 트리의 최대 레벨
5) 차수 : 노드가 가지고 있는 자식 노드의 개수
5. 쓰레드 이진 트리란?
: NULL 링크에 중위 순회 시에 후속 노드인 중위 후속자를 저장시켜 놓은 트리이다.
-> 중위순회 순서 ACBGDFE
#include <stdio.h>
#define TRUE 1
#define FALSE 0
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
int is_thread; // 스레드이면 TRUE
} TreeNode;
// G
// C F
// A B D E
TreeNode n1 = { 'A', NULL, NULL, 1 };
TreeNode n2 = { 'B', NULL, NULL, 1 };
TreeNode n3 = { 'C', &n1, &n2, 0 };
TreeNode n4 = { 'D', NULL, NULL, 1 };
TreeNode n5 = { 'E', NULL, NULL, 0 };
TreeNode n6 = { 'F', &n4, &n5, 0 };
TreeNode n7 = { 'G', &n3, &n6, 0 };
TreeNode * exp = &n7;
TreeNode * find_successor(TreeNode * p)
{
// q는 p의 오른쪽 포인터
TreeNode * q = p->right;
// 만약 오른쪽 포인터가 NULL이거나 p가 스레드이면 오른쪽 포인터를 반환
if (q == NULL || p->is_thread == TRUE)
return q;
// 쓰레드가 아니면, 오른쪽 노드 -> 다시 가장 왼쪽 노드로 이동
while (q->left != NULL) q = q->left;
return q;
}
void thread_inorder(TreeNode * t)
{
TreeNode * q;
q = t;
while (q->left) q = q->left;// 가장 왼쪽 노드로 간다.
do {
printf("%c -> ", q->data);// 데이터 출력
q = find_successor(q); // 후속자 함수 호출
} while (q); // NULL이 아니면
}
int main(void)
{
// 스레드 설정
n1.right = &n3;
n2.right = &n7;
n4.right = &n6;
// 중위 순회
thread_inorder(exp);
printf("\n");
return 0;
}
- thread_inorder(); 에서 가장 왼쪽 노드로 간다.
- 노드의 값을 프린트하고
- find_successor(); 함수로 쓰레드이면 그 다음 포인터를 반환, 쓰레드가 아니면 오른쪽 -> 왼쪽 가장 밑으로 간다.
6. 완전 이진트리
: 레벨 1부터 k-1까지는 노드가 모두 채워져 있고, k레벨에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리이다.
'Computer Science > Data Structure' 카테고리의 다른 글
| 자료구조 3 - 4) 그래프 최단경로 : 다익스트라, 플로이드 / 위상 정렬 (0) | 2020.12.10 |
|---|---|
| 자료구조 3 - 3) 그래프 MST : 크루스칼, 프림 (0) | 2020.12.05 |
| 자료구조 3 - 2) 그래프 BFS, DFS (0) | 2020.12.05 |
| 자료구조 3 - 1) 그래프 (0) | 2020.12.04 |
| 자료구조 2. 우선순위 큐 & 힙(Heap) (0) | 2020.12.04 |
