Tree

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

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


1. 용어 개념 (설명)

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

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

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

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


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

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


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

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

https://www.gowoonsori.com/images/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://www.gowoonsori.com/images/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://www.gowoonsori.com/images/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

표준 입출력

표준 입출력

GoLang의 표준 입출력은 다른 언어와 같이 터미널이 기본이며, 파일등으로 수정이 가능하고 fmt패키지에서 제공을 한다. 입출력은 BitStream형태로 되어있다. 1. 표준 출력 1) 함수 함수 기능 Print() 입력값들을 출력 Println() 마지막에 개행문자를 포함한 입력값들을 출력 Printf() c의 printf와 같이 특정 포맷에 맞게 출력 2) 포맷 서식 포맷형태 설명 %d 정수 %f 실수(소수점 6자리까지 표현) %v 기본형태(자동으로 맞는 값으로 변경) %g 길이에 맞는 실수형태로 변경해서 출력(%v로 사용시 실수의 경우 %g로 바뀜) %3d 3자리 칸에 맞춰 오른쪽 정렬해 출력 %03d 3자리 칸에 맞춰 출력하는데 빈칸을 0으로 채움 %-3d 3자리 칸에 맞춰 왼쪽정렬해 출력...

Read More
최장 증가 수열

최장 증가 수열

주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열이다. 예를 들어, 341256784134라는 수열에서 LIS는 345678 or 125678 이 된다. 1. 찾는 방법 LIS의 크기 구하는 방법은 dp와 이분탐색에 따라 방법이 나뉘며 경로 추적(trace) 방법은 두 방법 모두 인덱스를 가리키는 배열을 하나 추가하여, 탐색하면서 해당 값의 앞의 수열 인덱스를 저장하는 방법으로 구현한다....

Read More
요청 Environment 접근

요청 Environment 접근

이번에는 Spring Boot GraphQL 환경변수(쿼리명, 파라미터명, 값, 받고자하는 데이터명 등)들을 Controller에서 접근하는 방법을 포스팅하려고 한다. 보통 Rest한 서버의 Controller에서는 @PathVariable , @RequestBody 등과 같은 어노테이션을 이용해서 파라미터들에 접근할 수 있는데 요청자체가 body안에 json형태로 들어오는 graphQL은 위와 같은 어노테이션을 사용하기에 다소 무리가 있다....

Read More