Tree

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

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


1. 용어 개념 (설명)

  • Node (노드): 트리를 구성하고 있는 각각의 요소를 의미한다.
  • Edge (= link, 간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
  • Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
  • Sibling (형제 노드) : 같은 부모를 갖는 노드
  • Degree (차수) : 해당 노드의 자식노드 개수
  • Depth (깊이) : 루트 노드 부터 현재 노드까지의 간선의 개수
  • Level (레벨) : 같은 깊이를 갖는 노드들의 집합
    루트 노드의 레벨을 1이 아닌 0으로 시작할 수도 있다. 편한대로 하면 된다.
  • Height (높이) : 트리의 최대 레벨
  • Terminal Node (= leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
  • Internal Node (내부노드, 비단말 노드) : 노드를 제외한 모든 노드로 루트 노드를 포함한다.

https://gowoonsori.comimages/datastructure/tree/perfect2.png does not exist

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

  • 노드 : 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



2. 종류

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

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

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


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

https://gowoonsori.comimages/datastructure/tree/complete.png does not exist 위 그림과 같이 마지막 레벨을 제외한 모든 서브트리의 레벨이 같아야 하고, 마지막 레벨은 왼쪽부터 채워져 있어야 한다.

그렇다면 아래의 트리는 완전 이진 트리일까? https://gowoonsori.comimages/datastructure/tree/not_complete.png does not exist

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


2) 정 이진 트리 (Full binary tree)

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


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

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

https://gowoonsori.comimages/datastructure/tree/perfect.png does not exist

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

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

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



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

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

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

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

예를 들어, 아래와 같은 트리가 있다고 한다면 https://gowoonsori.comimages/datastructure/tree/perfect2.png does not exist

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

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

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

의 순서로 순회하게 된다.



4. 이진 탐색 트리 ( Binary Search Tree )

Note

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

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

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


1) Skewed Tree

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

https://gowoonsori.comimages/datastructure/tree/skewd.png does not exist



2) 구현 방법

배열

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

연결 리스트

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

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



5. Tree의 단점

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

해결 방법 ➡ Rebalancing 기법 사용

Tags :

Related Posts

돈버는 말투, 돈 버리는 말투

돈버는 말투, 돈 버리는 말투

  • Books
  • 2021년 4월 23일

저자는 일본인으로 우리 한국과 일부 사회상이 안맞는 부분이 있긴 하지만 전체적으로 공감할 만한 부분들이 많았고 책도 양이 많지 않아 금방 읽힌 책이었으며, 책을 읽다보면 당연한 소리를 하고있는 것 같지만 그 당연한 것들을 지키기가 어려운 것이기에 공감한 부분들을 이곳에 정리해두려고 한다. 1. 자신의 업무 철학 확립 자신만의 업무 철학을 물었을때는 이것에 대...

Read More
리눅스 Timezone 설정하기

리눅스 Timezone 설정하기

1. 현재 서버 시간확인 $ date 리눅스를 설치할 때 timezone을 따로 설정하지 않으면 UTC 타임존으로 설치가 되고, date명령어로 현재 서버의 시간을 확인할 수 있다. 2. /etc/localtime 심볼릭 링크파일 수정 /usr/share/zoneinfo/에 여러 국가들의 정보가 존재하는데 바꾸고자 하는 지역을 /etc/localtime라는 이름으로 기존의...

Read More
Optional

Optional

  • Java
  • 2021년 12월 8일

Java 8에 새로 생긴 인터페이스로 라이브러리 메서드가 반환할 결과값이 없음을 명백하게 표현할 필요가 있는 곳에서 제한적으로 사용할 수 있는 메커니즘을 제공하기 위해 새로 생겨났다. Java api doc의 API 노트를 보면 다음과 같이 설명하고 있다. Optional은 주로 결과 없음을 나타낼 필요성이 명확하고 null을 사용하면 오류가 발생할 수 있는 메소드 반환...

Read More