자료구조 공부 #18 (트리연산)

2021.05.16 - [이론공부/자료구조] - 자료구조 공부 #13 (트리순회)

---

이진트리 노드 갯수 연산

 

• 탐색 트리안의 노드의 개수를 계산
• 각각의 서브트리에 대하여 순환 호출만 한다음, 반환되는 값에 1을 더하여 반환

int get_node_count(TreeNode* node){
    int cout = 0;
   	if (node != NULL)
   		count = 1 + get_node_count(node->left) + get_node_count(node->right);
    return count;
}

 

 

이진 트리 높이 연산

• 서브 트리에 대하여 순환 호출하고 서브트리들의 반환값 중에서 최대값을 구하여 반환

 

 

int get_height(TreeNode* node){
	int height = 0;
    if (node != NULL)
    	height = 1 + max(get_height(node->left), get_height(node->right));
    return height;    
}

 

이진 트리 단말노드 갯수 연산

int get_leaf_count(TreeNode* node){
	int count = 0;
    if (node != NULL){
    	if (node->left == NULL && node->right == NULL)
        	return 1;
        else
        	count = get_leaf_count(node->left) + get_leaf_count(node->right);
    }
    return count;
}

 

 

스레드 이진 트리

• 이진 트리의 NULL 링크를 이용하여 순환 호출 엇이도 트리의 노드들을 순회
• NULL 링크에 중위 순회 시에 후속 노드인 중위 후속자를 저장시켜 놓은 트리가 스레드 이진 트리

 

다시 부모로 올라갈 수 있는 링크가 존재

스레드 이진 트리 구현

 

• 단말노드와 비단말노드의 구별을 위해 is_thread 필드 구현

typedef struct TreeNode{
	int data;
    struct TreeNode*left, * right;
    int is_thread;
}TreeNode;

 

• 중위 후속자를 찾는 함수 구현

TreeNode* find_successor(TreeNode* p){
    TreeNode q = p->right;
    
    if(q==NULL || p->is_thread == true)
    	return q;
    
    while(p->left != NULL) q= q->left;
    return q;
}

 

 

이진탐색 트리

• 탐색 작업 효율적으로 하기 위한 구조
• 왼쪽 key ≤ 루트 key ≤ 오른쪽 key
• 이진 탐색을 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있음

데이터 자체를 정렬을 잘하여 저장해야된다.

 

탐색 연산

1. 비교한 결과 같으면 탐색 성공
2. 비교한 결과가 주어진 키 값이 루트 노드의 키값 보다 작으면 탐색을 왼쪽 서브트리 기준으로 다시시작
3. 비교한 결과가 주어진 키 값이 루트 노드의 키값 보다 크면 탐색을 오른쪽 서브트리 기준으로 다시시작

 

• 순환으로 탐색 구현

TreeNode* search(TreeNode* node, int 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* search(TreeNode* node, int key){
	while(node != NULL){
    	if(key == node->key) return node;
        else if(key < node->key)
        	node = node->left;
        else
        	node = node->right;
    }
    return NULL;
}

 

이진 탐색트리 삽입 연산

• 이진탐색 트리에 원소를 삽입하기 위해서 탐색을 먼저 수행
• 탐색에 실패한 위치가 바로 노드 삽입하는 위치

C 구현 코드

TreeNode *insert_node(TreeNode* node, int 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 *new_node(int item){
	TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

 

이진탐색 트리 삭제연산

• 3가지 경우
  • 삭제하는 노드가 단말 노드인 경우
  • 삭제하는 노드가 하나의 왼쪽이나 오른쪽 서브트리중 하나만 가지고 있는 경우
  • 삭제하는 노드가 두개의 서브 트리 모두 가지고 있는 경우

단말 노드인 경우

 

하나만 있는 경우

 

둘다 있는 경우

TreeNode* delete_node(TreeNode* root, int key){
	if (root == NULL) return NULL;
    
    if(key < root->key)
    	root->left = delete_node(root->left,key);
    else if (key > root-key)
    	root->right = delete_node(root->right,key);
    else{
    	//1 and 2
    	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;
        }
        
        //3
        Treenode* temp = min_value_node(root->right);
        root->key = temp->key;
        root->right = delete_node(root->right,temp->key);
    }
	return root;
}

 

트리연산 전체 C 구현코드

#include <stdio.h>
#include <stdlib.h>


typedef struct TreeNode {
	int key;
	struct TreeNode* left, * right;
}TreeNode;


TreeNode* search(TreeNode* node, int 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(int item) {
    TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

TreeNode* insert_node(TreeNode* node, int 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, int key) {
    if (root == NULL) return NULL;

    if (key < root->key)
        root->left = delete_node(root->left, key);
    else if (key > root -> key)
        root->right = delete_node(root->right, key);
    else {
        //1 and 2
        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;
        }

        //3
        TreeNode* temp = min_value_node(root->right);
        root->key = temp->key;
        root->right = delete_node(root->right, temp->key);
    }
    return root;
}

//중위순회
//LVR
void inorder(TreeNode* root) {
    if (root) {
        inorder(root->left);
        printf("[%d]", root->key);
        inorder(root->right);
    }
}


//전위 순회
//VLR
void preorder(TreeNode* root) {
    if (root) {
        printf("[%d]", root->key);
        preorder(root->left);
        preorder(root->right);
    }
}

// 후위 순회
//LRV 
void postorder(TreeNode* root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        printf("[%d]", root->key);
    }
}

int main(void) {
    TreeNode* root = NULL;
    TreeNode* tmp = NULL;

    root = insert_node(root, 30);
    root = insert_node(root, 20);
    root = insert_node(root, 10);
    root = insert_node(root, 40);
    root = insert_node(root, 50);
    root = insert_node(root, 60);

    printf("이진 탐색 트리 중위 순회 결과 \n");
    inorder(root);

    printf("\n\n");

    if (search(root, 30) != NULL)
        printf("이진 탐색 트리에서 30을 발견함\n");
    else
        printf("이진 탐색 트리에서 30을 발견못함\n");

    printf("\n\n");

    delete_node(root, 40);
    printf("이진 탐색 트리에서 40을 삭제\n");
    printf("이진 탐색 트리 중위 순회 결과 \n");
    inorder(root);

    printf("\n\n");

    if (search(root, 40) != NULL)
        printf("이진 탐색 트리에서 40을 발견함\n");
    else
        printf("이진 탐색 트리에서 40을 발견못함\n");

    printf("\n\n");

    root = insert_node(root, 39);
    printf("이진 탐색 트리에서 39을 삽입\n");
    printf("이진 탐색 트리 중위 순회 결과 \n");
    inorder(root);

    printf("\n\n");



    return 0;
}

이진 트리 성능 분석

• 이진 탐색 트리에서 탐색, 삽입, 삭제, 연산의 시간 복잡도는 트리의 높이를 h 라고 했을때 h에 비례함

 

2021.05.04 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부 #12 (탐색 트리)

화일 처리 및 응용에서도 다룬 내용이니 참고하자

 

---

탐색트리의 연산 알고리즘, 구현코드를 살펴보자, 복잡도의 비례관계도 알아두자