(22.08.27)자료구조 8 - 트리(Tree) 1

트리란?

계층적 구조를 나타내는 자료구조로, 부모-자식 관계의 노드들의 집합

 

대용량 데이터를 저장하기 용이한 자료구조다.

Why?

탐색이 아주 빠르기 때문이다.

선형 자료구조와 달리 탐색의 시간 복잡도를 O(log N)로 줄일 수 있다.

(단, 삽입 삭제의 최소 O(log N)의 시간 복잡도를 갖는다.)

 

트리의 구성요소

• Node
• Edge
• Sibling
• Subtree
• Root node
• Leaf Node(Terminal Node)
• Level
• Height, Degree

 

이진 트리(Binary Tree)

• 모든 노드가 최대 2개의 서브 트리를 갖는 트리
• 모든 노드의 차수가 2 이하인 트리
• 이진트리의 서브트리는 이진트리라는 재귀적 정의를 갖고 있다.

 

특징

• 노드 개수가 n이면 엣지의 개수는 n-1
• 높이가 h인 이진 트리는 최소 h개 ~ 최대 (2^h) -1개로 구성돼있다.

 

ADT

• BTree CreateBtree()
  트리를 생성해서 반환
  
  
• Boolean isEmpty(bt)
  트리가 비어 있는 지를 Boolean 값으로 반환
  
  
• void SetLeftSubTree(parent,LChild), void SetRightSubTree(parent,RChild)
  LChild, Rchild 를 각각 parent의 왼쪽, 오른쪽 서브트리로 만든다.
  
  
• BTree GetLChild(bt) , BTree GetRChild(bt)
  각각 bt의 왼쪽, 오른쪽 서브트리 주소값을 반환한다.
  
  
• element GetData(bt)
  bt의 값을 반환
  
  
• void SetData(bt,item)
  bt의 값을 item으로 바꾼다.

 

트리 순회 방식 3가지

• 전위 순회(preorder)
  Root -> Left -> Right
• 중위 순회(inorder)
  Left -> Root -> Right
• 후위 순회(postorder) 
  Left -> Right -> Root
  수식 트리의 계산에서 사용된다.

전위, 중위, 후위 순회는 모두 재귀호출 혹은 스택을 이용한다.

 

//중위 순회
void inOrderPrint(btree* bt){
    if(bt == NULL)
        return;

    inOrderPrint(GetLChild(bt));
    printf("%d ", GetData(bt));
    inOrderPrint(GetRChild(bt));

}

//전위 순회
void preOrderPrint(btree* bt){
    if(bt == NULL)
        return;
    printf("%d ", GetData(bt));
    preOrderPrint(GetLChild(bt));
    preOrderPrint(GetRChild(bt));
}

//후위 순회
void postOrderPrint(btree* bt){
    if(bt == NULL)
        return;

    postOrderPrint(GetLChild(bt));
    postOrderPrint(GetRChild(bt));
    printf("%d ", GetData(bt));
}

• 레벨 순회(level order)
  • 각 노드를 레벨 순으로 순회
  • 큐를 이용한다.

 

 

 

 

구현

구현은 연결리스트 기반으로 진행한다.

배열도 트리를 구현하는데에 사용 가능하지만 Heap에서 주로 사용한다.

 

 

In C

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

#define TRUE 1
#define FALSE 0

typedef int data;

typedef struct BTree {
    data value;
    struct BTree *left;
    struct BTree *right;
} btree;

btree *CreateBtree() {
    btree *root = (btree *) malloc(sizeof(btree));
    root->value = NULL;
    root->left = NULL;
    root->right = NULL;
    return root;
}

int isEmpty(btree *bt) {
    if (bt->value == NULL)
        return TRUE;
    else
        return FALSE;
}


void SetLeftSubTree(btree *parent, btree *LChild) {
    //자식이 이미 있으면 메모리 해제, 메모리 누수 가능성 존재
    if (parent->left != NULL)
        free(parent->left);
    parent->left = LChild;
}

void SetRightSubTree(btree *parent, btree *RChild) {
    //자식이 이미 있으면 메모리 해제, 메모리 누수 가능성 존재
    if (parent->right != NULL)
        free(parent->right);
    parent->right = RChild;
}

btree *GetLChild(btree *bt) {
    return bt->left;
}

btree *GetRChild(btree *bt) {
    return bt->right;
}

data GetData(btree *bt) {
    return bt->value;
}

void SetData(btree *bt, data item) {
    bt->value = item;
}

In TypeScript

class BinaryTree {
    data :number;
    left :BinaryTree;
    right :BinaryTree;
    constructor(data :number = NaN){
        this.data = data;
    }

    isEmpty() :boolean{
        if(this.data === NaN)
            return true;
        else
            return false;
    }

    SetLeftSubTree(LChild :BinaryTree){
         this.left = LChild;
    }

    SetRightSubTree(RChild :BinaryTree){
         this.right = RChild;
    }

    GetLChild() :BinaryTree{
        return this.left;
    }

    GetRChild() :BinaryTree{
        return this.right;
    }

    GetData() :number{
        return this.data;
    }

    SetData(data :number){
        this.data = data;
    }

    //중위 순회
    inOrderPrint(){

        if(this.GetLChild() !== undefined){
            this.GetLChild().inOrderPrint();
        }
        console.log(this.GetData() + " ")
        if(this.GetRChild() !== undefined){
            this.GetRChild().inOrderPrint();
        }
        
    }

    //전위 순회
    preOrderPrint(){       

            console.log(this.GetData() + " ");
            if(this.GetLChild() !== undefined){
                this.GetLChild().preOrderPrint();
            }
            if(this.GetRChild() !== undefined){
                this.GetRChild().preOrderPrint();
            }
    }

    //후위 순회
    postOrderPrint(){

        if(this.GetLChild() !== undefined){
            this.GetLChild().postOrderPrint();
        }
        if(this.GetRChild() !== undefined){
            this.GetRChild().postOrderPrint();
        }
        console.log(this.GetData() + " ");
    }
}

 

배열기반 트리의 특징

배열기반 트리의 인덱스는 기본적으로 0이 아니라 편의를 위해서 1부터 시작한다.

• 노드 i의 부모 노드 인덱스 = floor(i/2) (내림)
• 노드 i의 왼쪽 자식 노드 인덱스 = 2i
• 노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1

장점

• 각 자식, 부모 노드간의 접근이 용이하다.

단점

• 편향트리, 트리의 모양이 예측 불가능한 경우, 메모리 낭비가 발생한다.

결국, 이진트리에 들어갈 데이터 수의 상한선이 보장되어 있을 때만 사용한다.