08 트리 (C언어로 쉽게 풀어쓴 자료구조)

8.1 트리의 개념

-계층적 자료구조

트리의 용어들

트리는 한 개 이상의 노드로 이루어진 유한집합이다. 루트-서브트리에서 서브트리는 또다시 루트-서브트리로 나눠질 수 있다.

조상노드(ancestor node): 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드를

후손노드(descendent node): 임의의 노드 하위에 연결된 모든 노드들을 의미한다

단말노드(terminal node, leaf node): 자식노드가 없는 노드(차수=0)

비단말노드(nonterminal node): 자식노드가 있는 노드

 

노드의 차수(degree): 어떤 노드가 가지고 있는 자식노드의 개수

트리의 차수: 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값

레벨(level): 트리의 각 층에 번호를 매기는 것. 루트노드가 1층이다

높이(height): 트리가 가지고 있는 최대 레벨

포리스트(forest): 트리들의 집합

 

트리의 종류

트리를 컴퓨터로 어떻게 표현할까?

데이터필드: 데이터를 저장(n=차수)

링크필드: 자식 노드를 가리킴

p.257 퀴즈

 

8.2 이진 트리 소개

이진트리의 정의

이진트리(binary tree): 모든 노드가 2개의 서브 트리를 가지고 있는 트리(이때, 서브트리가 공집합일 수 있다)

즉, 최대 2개의 자식노드를 가질 수 있다 = 모든 노드의 차수<=2

*공집합도 이진트리이다

이진 트리에는 서브 트리 간의 순서가 존재하기 때문에 왼쪽 서브트리/오른쪽 서브트리를 서로 구별한다.

<<이진트리의 정의>>

(1) 공집합이거나
(2) 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합으로 정의된다. 이진트리의 서브트리들은 모두 이진트리여야 한다.

 

이진트리의 서브트리도 이진트리의 성질을 만족해야 한다!!

 

이진트리와 일반트리의 차이점

• 이진트리의 모든 노드는 차수가 2이하이다. 즉, 자식 노드의 개수가 2이하이다. <-> 일반트리는 자식 노드의 개수에 제한이 없다
• 일반 트리와 달리 이진트리는 노드를 하나도 갖지 않을 수도 있다(공집합도 이진트리다)
• 이진트리에는 서브 트리간에 순서가 존재한다. 따라서 왼쪽 서브트리와 오른쪽 서브트리를 구별한다.

 

이진트리의 성질

• 노드 개수-1 = 간선 개수
  (이유: 이진트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모노드를 가진다. 그리고 부모와 자식 간에는 정확히 하나의 간선만이 존재한다.)
• 높이가 h인 이진트리는 최소 h개의 노드, 최대 2^h-1 개의 노드를 가진다.
  (이유: 한 레벨에는 적어도 하나의 노드가 존재해야 하니까 최소 h개 필요. 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i에서 노드의 최대 개수는 2^(i-1)개인데 걔네를 다 합해야하니까 시그마 해주면 2^h -1 이 최대 노드 개수가 된다)
• n개의 노드를 가지는 이진트리의 높이: 최대 n, 최소 log2(n+1)의 floor값
  (이유: 일단 최대는 각 각 레벨에 노드가 1개씩 있을 때/ 최소는 2^h -1 = n(h는 레벨,n은 노드 개수)이라고 할 때 일단 2^h -1은 최대 개수이므로 2^h -1 >= n이다. h기준으로 정리해보면 h>=log2(n+1). h는 정수값이므로 log값을 정수가 되도록 올림해준다!

 

이진트리의 분류 (포화 이진트리/완전 이진트리/기타 이진트리)

 

포화 이진트리(full binary tree)

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

-높이가 k이면 정확히 2^k -1개의 노드를 가진다

포화이진트리에서는 이렇게 노드에 번호를 붙일 수 있다. 항상 왼쪽->오른쪽으로 넘버링한다. 이 번호는 항상 일정하다.

 

완전 이진트리(complete binary tree)

:높이가 k일 때 레벨 1~k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽->오른쪽으로 노드가 순서대로 채워져 있는 이진트리

-마지막 레벨에서는 노드가 꽉차있진 않아도 되지만 중간에 빈곳이 있는 건 안된다

-포화이진트리는 항상 완전이진트리(O)

  완전이진트리는 항상 포화이진트리(X)

-포화이진트리의 노드번호와 완전이진트리의 노드번호는 1:1로 대응한다

 

기타 이진트리

:얘네 제외 이진트리

p.263 퀴즈

 

 

8.3 이진 트리의 표현

이진트리를 컴퓨터로 어떻게 표현할까?

• 배열로 표현
• 포인터로 표현

배열 표현법

-주로 포화이진트리,완전이진트리 에서 많이 쓰인다

-방법

1. 저장하고자 하는 이진 트리를 일단 완전이진트리라고 가정한다
2. 이진트리의 깊이가 k이면 최대 2^k -1개의 공간을 연속적으로 할당한다
3. 완전이진트리의 번호대로 노드들을 저장한다

-인덱스[0]은 사용하지 않는다

이렇게 트리들은 먼저 번호가 매겨진 다음, 이 번호에 따라 배열에 저장된다

완전이진트리가 아닌 일반적인 이진트리도 배열로 저장은 가능하지만 기억공간의 낭비가 심해진다

-배열표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다

노드 i의 부모 노드 인덱스: i/2
노드 i의 왼쪽 자식 노드 인덱스: 2i
노드 i의 오른쪽 자식 노드 인덱스: 2i+1

 

링크 표현법

-트리에서의 노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법

총 3개의 필드가 있다

왼쪽 자식노드를 가리키는 포인터 필드 / 데이터 저장필드 / 오른쪽 자식노드를 가리키는 포인터 필드

 

코드 구현

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

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

int main(void)
{
    TreeNode *n1, *n2, *n3;
    n1 = (TreeNode *)malloc(sizeof(TreeNode));
    n2 = (TreeNode *)malloc(sizeof(TreeNode));
    n3 = (TreeNode *)malloc(sizeof(TreeNode));

    n1->data = 10;
    n1->left = n2;
    n1->right = n3;
    n2->data = 20;
    n2->left = NULL;
    n2->right = NULL;
    n3->data = 30;
    n3->left = NULL;
    n3->right = NULL;
    free(n1); free(n2); free(n3);
    return 0;
}

p.266 quiz

8.4 이진 트리의 순회

순회(traversal): 이진트리에 속하는 모든 트리를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것

트리의 목적=노드에 자료를 저장하고 필요에 따라서 이 데이터를 처리<-이므로 순차적으로 순회하는 것은 중요하다.

지금까지 우리가 했던 스택, 큐 이런 애들은 데이터를 선형으로 저장하고 있어서 자료에 순차적으로 순회하는 방법은 하나뿐이었는데, 트리는 아니어서 여러가지 순서로 접근 가능하다. 

이진트리 순회방법

전위순회: VLR
중위순회: LVR
후위순회: LRV

-순환을 사용하면 문제의 크기가 작아지기 때문에 이진트리의 서브트리에도 동일하게 적용할 수 있다

 

전위순회: VLR

중위순회: LVR

후위순회(LRV)

 

 

8.5 반복적 순회

이 경우 스택을 사용한다. 스택에 자식노드들을 저장하고 꺼내면서 순회

8.6 레벨 순회

레벨순회(level order): 각 노드를 레벨순으로 검사하는 순회방법

-동일한 레벨의 경우 좌->우로 방문

-얘는 큐를 사용한다!

-큐에 하나라도 노드가 있으면 계속 반복하는 코드(노드가 하나도 없으면 중단)

 

어떤 순회를 선택해야 할까?

순서는 중요하지 않고 노드를 전부 방문하기만 하면 된다면 아무거나 ㄱㅊ

후위 순회(LRV): 자식 노드를 처리한 다음에 부모노드를 처리해야 할 때

전위 순회(VLR): 부모 노드를 처리한 다음에 자식 노드를 처리해야 할 때

8.7 트리의 응용: 수식 트리 처리

-이진트리는 수식처리(expression tree)를 처리하는데 사용될 수 있다

-피연산자: 단말노드 / 연산자: 비단말노드

-후위순회(LRV)를 사용

-서브트리의 값을 순환호출로 계산

8.8 트리의 응용: 디렉토리 용량 계산

-이진트리 순회는 컴퓨터의 디렉토리 용량을 계산하는데도 사용된다

-후위트리순회 사용

8.9 이진 트리의 추가 연산

노드의 연산

-탐색트리 안의 노드의 개수를 세어 표시한다

-각각의 서브트리에 대하여 순환 호출 -> 반환되는 값에 1을 더하여 반환

 

단말노드 개수 구하기

-전체 노드들을 순환하면서 if(왼쪽 자식==오른쪽자식==0) 이면 단말노드이므로 1을 반환한다

-else 비단말 노드이므로 각각의 서브트리에 대하여 순환호출한 다음, 반환되는 값을 서로 더하면 된다

 

높이 구하기

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

 

8.10 스레드 이진 트리

순회를 순환호출 없이, 즉 스택의 도움 없이 할 수 있을까?

스레드 이진트리: NULL 링크에 중위 순회 시에 선행노드인 중위선행자나 중위순회시에 후속노드인 중위후속자를 저장시켜놓은 트리

 

①단말노드와 비단말노드의 구별을 위하여 is_thread 작성

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

이게 뭔말이냐! 만약 is_thread가 TRUE야. 그 말은 단말노드다~라는 말이다. 이 경우 중위순회에서 다음순위로 찾아갈 애로 넘어간다

근데 만약 is_thread가 FALSE야. 그말은 오른쪽 자식이 있다는 거야! 이 경우에는 오른쪽 자식으로 가면 된다

②중위후속자를 찾는함수

TreeNode * find_successor(TreeNode *p)
{
    //q는 p의 오른쪽 포인터
    TreeNode *q = p->right;
    //만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
    if (q==NULL || p->is_thread == TRUE)
        return q;
    
    //만약 오른쪽 포인터가 자식이면 다시 가장 왼쪽 노드로 이동
    while (q->left != NULL) q=q->left;
    return q;
}

 

 

스레드 이진 트리에서 중위 순회를 하는 함수 thread_inorder

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);
}

 

8.11 이진 탐색 트리

이진탐색트리(binary search tree): 이진트리 기반의 탐색을 위한 자료구조

 

이진탐색트리의 정의

이진탐색트리란 이진탐색 트리의 성질을 만족하는 이진트리를 말한다

• 모든 원소의 키는 유일한 키를 가진다
• 왼쪽 서브 트리 키들은 루트 키보다 작다
• 오른쪽 서브 트리의 키들은 루트 키보다 크다
• 왼쪽과 오른쪽 서브 트리도 이진탐색트리이다

-이진탐색트리를 중위순회방법으로 순회하면 숫자들의 크기순이 된다.

key(왼쪽 서브트리)<=key(루트노드)<=key(오른쪽 서브트리)

 

탐색 방법

주어진 탐색키 vs 루트노드

• 탐색키==루트노드 -> 성공! 탐색 끝
• 탐색키 < 루트노드 -> 탐색키의 왼쪽 자식노드를 기준으로 다시 비교 시작
• 탐색키 > 루트노드 -> 탐색키의 오른쪽 자식노드를 기준으로 다시 비교 시작

 

순환적인 탐색연산

//순환적인 탐색 함수
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; //탐색에 실패했을 경우 NULL 반환
}

반복적인 탐색함수는 매개변수 node가 NULL이 아니면 반복을 계속한다.(=단말노드까지 내려감을 의미)

 

이진트리에서의 삽입연산

원소 삽입을 위해서는 먼저 탐색이 필요하다.(1.이진탐색트리에서는 같은 값을 갖는 노드가 없어야 한다 2.탐색에 실패한 위치=삽입위치)

-새로운 노드는 항상 단말 노드에 추가된다

//새로운 노드를 생성하여 반환
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;
}

 

이진트리에서의 삭제연산

노드와 마찬가지로 먼저 탐색을 진행해야 한다.

 

세 가지 경우를 고려해보자:

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

2.삭제하려는 노드가 왼쪽/오른쪽 서브트리 중 하나만 가지고 있는 경우

3.삭제하려는 노드가 두 개의 서브트리 모두 가지고 있는 경우

 

case 1: 삭제하려는 노드가 단말 노드인 경우

단말노드만 지우면 된다! = 단말노드의 부모를 찾아 부모노드 안의 링크필드를 NULL로 바꾸기 -> 지우려는 노드 free()

 

case 2: 삭제하려는 노드가 하나의 서브트리만 가지고 있는 경우

자기 노드는 삭제, 서브트리는 자기 노드의 부모노드에 붙여준다

 

case 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(root->right, key);
    
    else {//키가 루트와 같으면 이 노드를 삭제하면 됨
        //case 1 & case 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;
        }
        //case 3
        TreeNode * temp = min_value_node(root->right);

        //중위 순회시 후계노드를 복사한다
        root->key = temp->key;
        //중위 순회시 후계노드를 삭제한다
        root->right = delete_node(root->right, temp->key);
    }
    return root;
}

 

이진 탐색 트리의 분석

트리의 높이를 h라고 했을 때 탐색,삽입,삭제 연산의 시간 복잡도는 O(h)

n개의 노드를 가지는 이진탐색 트리의 경우 일반적인 이진트리의 높이는 log2(n)이므로 평균적인 경우의 시간복잡도는 O(log2(h))

 

최선: 좌우의 서브트리가 균형을 이룰 경우

 

최악: 한쪽으로 치우치는 경사트리가 되어 트리의 높이=노드개수n

이 경우 탐색, 삭제, 삽입 시간이 거의 선형 탐색과 같이 O(n)이 된다. 따라서 선형탐색에 비해 전혀 시간적 이득X

8.12 이진 탐색 트리의 응용: 영어사전