Tree


그래프의 일종으로, 여러 노드가 한개의 노드를 가리킬 수 없는 구조

선형구조가 아닌 (비선형), 부모자식의 관계를 가지는 계층형 구조


용어 개념 (설명)


◾ Node (노드)

트리를 구성하고 있는 각각의 요소를 의미한다.

◾ Edge (= link, 간선)

트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.

◾ Root Node (루트 노드)

트리 구조에서 최상위에 있는 노드를 의미한다.

◾ Sibling (형제 노드)

같은 부모를 갖는 노드

◾ Degree (차수)

해당 노드의 자식노드 개수

◾ Depth (깊이)

루트 노드 부터 현재 노드까지의 간선의 개수

◾ Level (레벨)

같은 깊이를 갖는 노드들의 집합
루트 노드의 레벨을 1이 아닌 0으로 시작할 수도 있다. 편한대로 하면 된다.

◾ Height (높이)

트리의 최대 레벨

◾ Terminal Node (= leaf Node, 단말 노드)

하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.

◾ Internal Node (내부노드, 비단말 노드)

단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.



ex 위의 트리로 예를 들어 설명하자면, 아래와 같이 된다.

  • 노드 : 10, 5, 15, 1, 7, 12, 20

  • 루트 노드 : 10

  • 차수

    • 10 : 2
    • 5,15 : 2
    • 1,7,12,20 : 0
  • 형제 노드

    • 5의 형제노드 : 15
    • 7의 형제노드 : 1
  • 레벨

    • 10의 레벨 : 1
    • 5,15의 레벨 : 2
    • 1,7,12,20의 레벨 : 3
  • 깊이

    • 5,15 의 깊이 : 1
    • 1,7,12,20의 깊이 : 2
  • 높이

    • 해당 트리의 높이 : 3
  • Terminal Node (단말 노드) : 1, 7, 12, 20

  • Internal Node (내부노드) : 10, 5, 15



종류


- Binary tree (이진 트리) : 부모 노드가 자식 노드를 최대 2개씩만 갖는 트리

- Ternary tree (삼항 트리) : 자식 노드를  이상 3개 갖고 있는 트리

위와 같은 종류가 있으며, 이진 트리를 기본으로 트리에 대해 설명하고자 한다.


◾ 완전 이진 트리 (Complete binary tree)

아래의 그림과 같이 마지막 레벨을 제외한 모든 서브트리의 레벨이 같아야 하고, 마지막 레벨은 왼쪽부터 채워져 있어야 한다.

complete binary tree



그렇다면 아래의 트리는 완전 이진 트리일까?

not_complete

마지막 레벨인 1,3,6 이 왼쪽부터 채워지지 않았기 때문에 완전이진 트리라고 할 수 없다.



◾ 정 이진 트리 (Full binary tree)

자식 노드가 없거나 2개인 트리



◾ 포화 이진 트리 (Perfect binary tree)

아래 그림과 같이 빈 공간이 없이 모든 노드2개의 자식을 갖고 있는 트리

perfect binary tree



◾ 이진 탐색 트리 (Binary search tree)

부모노드 보다 작은 값의 노드는 왼쪽 child, 큰 값의 노드는 오른쪽 child로 구성되어 있는 tree.

key값의 중복이 가능하게 구현을 할 수는 있으나 기본적인 개념은 중복허용하지 않는다.

아래 세 그림 중 BST가 아닌 것은 무엇일까??

bst1
bst2
bst3
답 보기



Tree 순회 (=탐색, Search) 방법


루트(root)를 시작으로해서 왼쪽 자식 들렸다가 오른쪽 자식 가는 방법으로 탐색을 한다.

이때, root( 부모 노드 )를 언제 탐색하냐에 따라서 3가지 방법으로 나뉘게 된다.

- 전위 순회 : root를 제일 먼저 순회
- 중위 순회 : root를 중간에 순회
- 후위 순회 : root를 제일 나중에 순회


예를 들어, 아래와 같은 트리가 있다고 한다면

perfect2

전위 순회 : 10, 5, 1, 7, 15, 12, 20

중위 순회 : 1, 5, 7, 10, 12, 15, 20

후위 순회 : 1, 7, 5, 12, 20, 15, 10

의 순서로 순회하게 된다.



이진 탐색 트리 ( Binary Search Tree )


위에 설명했듯이 BST는 key값은 중복되지 않으며, 부모의 키가 왼쪽 자식보다는 크며, 오른쪽 자식 보다는 작다.

왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

탐색 연산은 O(logn)을 갖으며, 한쪽으로 치우쳐진 편향 트리(Skewed Tree)가 되면 worst caseO(n)을 갖는다.


  • Skewed Tree

    계속 key값이 커지거나 반대로 계속 작아지는 경우에 아래와 같은 모양의 Skewed Tree가 된다.

    skewed



구현 방법

  • 배열
    트리는 일정한 규칙을 가지고 있기 때문에 배열을 이용해서도 쉽게 구현이 가능하다. - 루트노드를 배열의 인덱스 0으로 시작하는 경우 - 왼쪽 자식의 인덱스 = (부모노드의 인덱스 _ 2) + 1 - 오른쪽 자식의 인덱스 = (부모노드의 인덱스 _ 2) + 2 - 루트노드를 배열의 인덱스 1로 시작하는 경우 - 왼쪽 자식의 인덱스 = 부모노드의 인덱스 _ 2 - 오른쪽 자식의 인덱스 = (부모노드의 인덱스 _ 2) + 1

  • 연결 리스트

    • 연결리스트로 구현하면 왼쪽 자식,오른쪽 자식 가리킬 포인터를 하나씩 선언해서 가리키면 된다.



📃 BST 코드 예 (c++) ( 접기 / 펼치기 )
#include<iostream>
#include<Windows.h>

enum { _Preorder=1, _Inorder, _Postorder };

template<typename T>
class Node {
public:
    T key;
    Node* LNode;
    Node* RNode;
    Node(T key = 0, Node* LNode = NULL, Node* RNode = NULL) { this->key = key; this->LNode = NULL; this->RNode = RNode = NULL; }
};


template<typename T>
class BST {
private:
    Node<T>* root;

public:
    BST() : root(NULL){}
    void add(Node<T>* node);
    void Delete(T item);
    bool search_loop(T item);
    void Preorder(Node<T>* target);
    void Inorder(Node<T>* target);
    void Postorder(Node<T>* target);
    void showTree(int element);


};

template<typename T>

bool BST<T>::search_loop(T item) {
    Node<T>* s = this->root;
    while (s != NULL) {
        if (s->key == item) return true;   //key가 존재한다면 true
        else if (s->key > item) s = s->LNode; //key가 item보다 크다면 왼쪽으로 이동
        else s = s->RNode;                //key가 item보다 작다면 오른쪽으로 이동
    }
    return false;

}

template<typename T>
void BST<T>::add(Node<T>* node) {
    T item = node->key;
    /*트리가 비어있다면*/
    if (this->root == NULL) {
        this->root = node;
        return;
    }
    /*값이 존재하면*/
    if (search_loop(item)) {
        std::cout << "값이 이미 존재합니다" << std::endl;
        return;
    }
    /*item 삽입*/
    Node<T>* s = this->root;

    while (1) {
        /*item이 key값보다 크다면*/
        if (s->key < item) {
            if (s->RNode == NULL) {
                s->RNode = node;
                return;
            }
            s = s->RNode;
        }
        else {
            if (s->LNode == NULL) {
                s->LNode = node;
                return;
            }
            s = s->LNode;
        }
    }
}

template<typename T>
void BST<T>::Delete(T item) {
    Node<T>* t = this->root;
    Node<T>* parent = NULL;
    Node<T>* child, * succ, * succ_p;

    /*key값을 찾거나 없다면 break*/
    while (t != NULL && t->key != item) {
        parent = t;
        t = (item < parent->key) ? parent->LNode : parent->RNode;
    }

    /*-----탐색 종료------*/
    /*값이 없다면*/
    if (t == NULL) {
        std::cout << "해당 값이 존재 하지 않습니다." << std::endl;
        return;
    }

    /*자식노드가 없다면*/
    if (t->RNode == NULL && t->LNode == NULL) {
        if (parent != NULL) {
            /*부모노드의 왼쪽에 있다면*/
            if (parent->LNode == t) parent->LNode = NULL;
            else parent->RNode = NULL;
            delete(t);
        }
        else {
            delete(t);
            this->root = NULL;
        }
    }

    /*1개의 자식이 있다면 */
    else if (t->RNode == NULL || t->LNode == NULL) {
        child = (t->LNode == NULL) ? t->RNode : t->LNode;
        if (parent != NULL) {
            if (parent->LNode == t) parent->LNode = child;
            else parent->RNode = child;
            delete(t);
        }
        /*삭제할 노드가 root라면*/
        else {
            delete(t);
            this->root = child;
        }
    }

    /*2개의 자식이 있다면 오른쪽 child의 가장 작은 값을 attach*/
    else {
        succ_p = t;
        succ = t->RNode;

        /*오른쪽 child의 가장 작은 값 찾기*/
        /*succ_p == 가장 작은 값의 부모 노드*/
        /*succ 는 가장 작은 값의 노드*/
        while (succ->LNode != NULL) {
            succ_p = succ;
            succ = succ->LNode;
        }

        /*삭제하려는 노드의 오른쪽 child의 leftnode가 있다면
        succ_p leftnode의 rightnode를
        succ_p의 왼쪽에 연결*/
        if (succ_p->LNode == succ) {
            succ_p->LNode = succ->RNode;
        }
        /*삭제하려는 노드의 오른쪽child의 left node가 없다면
        오른쪽 child의 right node를 삭제할 노드의 오른쪽에 연결*/
        else succ_p->RNode = succ->RNode;

        /*삭제할 노드와 교환 후 삭제*/
        t->key = succ->key;
        t = succ;
        delete(t);
    }
    return;


}

//전위 순회
template<typename T>
void BST<T>::Preorder(Node<T>* target) {
    if (target == NULL)return;
    std::cout << target->key << " ";
    this->Preorder(target->LNode);
    this->Preorder(target->RNode);
}

//중위 순회
template<typename T>
void BST<T>::Inorder(Node<T>* target) {
    if (target == NULL)return;
    this->Inorder(target->LNode);
    std::cout << target->key << " ";
    this->Inorder(target->RNode);
}

//후위 순회
template<typename T>
void BST<T>::Postorder(Node<T>* target) {
    if (target == NULL)return;
    this->Postorder(target->LNode);
    this->Postorder(target->RNode);
    std::cout << target->key << " ";
}

template<typename T>
void BST<T>::showTree(int element) {
    switch (element) {
    case _Preorder:
        this->Preorder(this->root);
        std::cout << std::endl;
        break;
    case _Inorder:
        this->Inorder(this->root);
        std::cout << std::endl;
        break;
    case _Postorder:
        this->Postorder(this->root);
        std::cout << std::endl;
        break;
    default:
        break;
    }
}

int main() {
    BST<int> tree;
    tree.add(new Node<int>(35));
    tree.add(new Node<int>(18));
    tree.add(new Node<int>(68));
    tree.add(new Node<int>(99));
    tree.add(new Node<int>(26));
    tree.add(new Node<int>(7));
    tree.add(new Node<int>(12));
    tree.add(new Node<int>(3));
    tree.add(new Node<int>(30));
    tree.add(new Node<int>(22));
    tree.showTree(1);
    tree.showTree(2);
    tree.showTree(3);
    tree.Delete(18);
    tree.showTree(1);

    return 0;
}



Tree의 단점


위에 설명했던 skewed Tree형태가 된다면, 배열보다 많은 메모리를 사용했지만 시간복잡도가 같게되는 비효율적이 상황이 발생하기도 한다.

해결 방법Rebalancing 기법 사용



balanced Tree 등장