[자료구조] 트리

계층적 자료구조

 

edge(간선): 노드와 노드 사이 연결

node: 자료가 저장된 구조체

 

root node: 부모가 없는 최상위 조상 노드

parent/child node: 하나의 간선으로 직접 연결된 상위/하위 계층 노드

ancestor/descendent node: 상위/하위 계층 노드

terminal or leaf node: child가 없는 노드 (degree = 0)

internal node: 적어도 한 개의 child가 있는 노드

 

subtree: 하나의 노드와 그 자손들로 이루어진 트리

level: 트리의 각 층의 번호 (depth + 1)

height: 트리의 최대 레벨, root에서 leaf노드들 사이 가장 긴 경로상의 edge 개수 + 1

degree: 노드가 가지고 있는 자식의 개수 

depth: root노드와 node사이의 거리 (edge의 개수)

breadth: 트리의 leaf노드들의 개수

---

이진트리

모든 노드가 많아야 2 children을 포함하는 트리

(모든 노드가 2개의 sub 트리를 가지는 트리 - sub 트리는 공집합 가능)

 

• child를 left, right로 구분함
• 모든 노드의 degree가 2 이하 (구현이 편리)
• 노드의 개수가 n이면 edge의 개수는 n-1
• 높이가 h이면 최소 h개에서 최대 (2^h)-1개의 노드를 가짐
• n개의 노드를 가지면 높이가 최대 n, 최소 log2(n+1)

포화 이진 트리: 각 레벨에 노드가 꽉 차 있는 이진트리

 

완전 이진 트리: 왼쪽부터 빈 곳 없이 차 있음

---

배열 표현법

모든 이진 트리를 포화 이진 트리라 가정하고 각 노드에 번호를 붙여서 그 번호를 인덱스로 배열에 저장

인덱스 0은 사용 안 함

 

부모 노드 인덱스: i/2의 내림

left 자식 인덱스: 2i

right 자식 인덱스: 2i + 1

---

링크 표현법

포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법

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

---

이진 트리의 순회

Depth First Search (먼 것부터)

stack 사용

 

time complexity: O(n)

Auxiliary space(stack에 최대 얼마나 쌓이는가): O(h)

 

전위순회(VLR)

루트를 가장 먼저 방문

preorder(TreeNode *root){
    if(root){
        printf("%d",root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

 

응용

노드개수 구하기

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

int get_leaf_count(TreeNode* node){
    int count = 0;
    
    if(node != NULL){
        if(node->left == NULL && node->right == NULL) return 1;
        else
            count = get_leat_count(node->left) + get_leaf_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;
}

높이 구하기

---

중위순회(LVR)

루트를 중간에 방문

inorder(TreeNode *root){
    if(root){
        preorder(root->left);
        printf("%d",root->data);
        preorder(root->right);
    }
}

 

응용

Binary Search Tree

반복적인순회 코드

void inorder_iter(TreeNode *root){
    while(1){
        for(; root; root = root->left) push(root); //왼쪽 다 넣어
        
        root = pop(); //맨 위에 있는 친구가 새 root
        if(is_empty()) break; //비어있으면 break
        
        printf("[%d]", root->data);
        root = root->right; //왼쪽은 다 했으니 오른쪽으로 변경
    }
}

스레드 이진 트리

no stack, no recursion

right NULL 링크에 후속 중위 노드를 연결

typedef struct TreeNode{
    int data;
    TreeNode *left, *right;
    int is_thread; //오른쪽 링크가 스레드면 true
}TreeNode;

TreeNode* find_successor(TreeNode* p){
    TreeNode* q = p->right;
    
    //오른쪽이 NULL이거나 스레드면 그걸 그대로 반환
    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일 때까지 
}

---

후위순회(LRV)

루트를 마지막에 방문

postorder(TreeNode *root){
    if(root){
        preorder(root->left);
        preorder(root->right);
        printf("%d",root->data);
    }
}

 

응용

Deleting a Tree

디렉토리 용량계산

int calc_dir_size(TreeNode* root){
    int left_size, right_size;
    if(root == NULL) return 0;
    
    left_size = calc_dir_size(root->left);
    right_size = calc_dir_size(root->right);
    
    return (root->data + left_size + right_size);
}

 

 

---

Breadth First Search (가까운 옆 먼저)

Level order traversal

큐 사용 (먼저 읽은 left child를 먼저 처리해야함)

void levl_order(TreeNode *ptr){
    QueueType q;
    
    init_queue(&q);
    
    if(ptr == NULL) return;
    
    enqueue(&q, ptr);
    while(!is_empty(&q)){
        ptr = dequeue(&q);
        printf("[%d]", ptr->data);
        
        if(ptr->left) enqueue(&q, ptr->left);
        if(ptr->right) enqueue(&q, ptr->right);
    }
}

---

수식 트리

비단말노드: 연산자

단말노드: 피연산자

int evaluate(TreeNode *root){
    if(root == NULL) return 0;
    
    if(root->left == NULL && root->right == NULL) return root->data; //피연산자
    
    else{
        int op1 = evaluate(root->left);
        int op2 = evaluate(root->right);
        
        printf("%d %c %d을 계산합니다", op1, root->data, op2);
        
        switch(root->data){
            case '+': return op1+op2;
            case '-': reeturn op1-op2;
            case '*': return op1*op2;
            case '/': return op1/op2;
        }
    }
    return 0;
}

---

이진탐색트리(BST) - 중복 불가

중위순회하면 오름차순 정렬

key(왼쪽 sub 트리) < key(루트 노드) < key(오른쪽 sub 트리)

 

연산의 시간 복잡도는 트리의 높이 h에 비례

최선의 경우(균형적인): h = log2(n)

최악의 경우(sqwed): h = n

 

탐색연산 (같은 거 찾기)

key < root: 왼쪽 자식을 root로 다시 시작

key > root: 오른쪽 자식을 root로 다시 시작

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; //실패했을 때 
}

반복탐색

---

삽입연산

탐색에 실패한 위치에 새로운 노드 삽입

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; //변경된 노드 포인터 반환
}

---

삭제연산

1. 삭제하려는 노드가 단말 노드

단말노드의 부모 노드를 찾아서 연결 끊기

2. 삭제하려는 노드의 서브 트리가 하나

노드는 삭제하고 서브 트리는 부모 노드에 붙이기

3. 삭제하려는 노드의 서브 트리가 두 개

삭제하려는 노드와 가장 비슷한 (왼쪽에서 가장 크거나 오른쪽에서 가장 작은) 값을 가진 노드를 삭제 노드 위치로 옮기기

TreeNode* delete_node(TreeNode* root, int 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(roo->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(root->right, temp->key);
    }
    
    return root;
}

TreeNode* min_value_node(TreeNode* node){
    TreeNode* current = node;
    
    //맨 왼쪽 단말 노드를 찾아서
    while(current->left != NULL)
        current = current->left;
        
    return current;
}