자료구조 1. 이진 탐색 트리, 쓰레드 이진 트리

 

 

 

 

 

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레벨에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리이다.