트리의 개념과 구현

트리의 예

트리(tree)는 1:1 또는 1:N 계층적인 자료에 사용되는 자료구조이다.

​

​

트리의 예

트리를 구성하는 원소를 노드(node)라 하고, 노드를 연결하는 선을 간선(edge)이라고 한다. 트리의 구성 요소에 해당하는 A, B, C, D, E, F, G, H, I, I, J를 노드(node)라고 한다. B의 바로 아래에 있는 E, F, G를 B의 자식(children)노드라고 하며 B는 E, F, G의 부모(parent)노드라고 한다. 같은 부모 아래의 자식 사이는 서로 형제(sibling)노드라고 한다.

​

부모가 없는 노드를 루트노드라고 하며, 주어진 트리에는 여러 개의 서브트리가 존재할 수 있다.

이는, 자식 노드들은 각각 독립하여 새로운 트리를 구성할 수 있으므로 각 노드는 자식 노드 수만큼의 서브트리를 갖게 되는 것이다. 노드 A는 B, C, D 3개의 자식 노드가 있기 때문에 3개의 서브트리를 갖는다. 마찬가지로 B, E, F, G가 하나의 서브트리이며, 또한 C, H도 하나의 서브트리이다.

​

​

차수(degree)는 노드가 가지고 있는 자식 노드의 개수를 의미하며, 루트 노드인 A의 경우 자식 노드가 2개이기 때문에 차수도 2가 된다. E, F, G, H, I, J처럼 차수가 0인, 즉 차수가 없는 노드를 리프(leaf)노드 또는 단말(terminal) 노드라고 한다.

​

한 노드의 높이는 루트에서 노드까지 연결된 간순의 수가 되고, 노드의 높이 중에서 최대 레벨이 트리의 높이가 된다. 노드 B의 높이는 1, 노드 E의 높이는 2가되고, 트리의 전체 높이는 2다.

​

이진 트리의 개념

트리 중에서 가장 많이 쓰이는 트리가 이진 트리이다. 이진 트리는 한 노드가 최대 2개까지의 자식노드가 존재할 수 있고 모든 노드의 차수는 2 이하가 된다. 이진 트리는 좌, 우가 구별된 2개의 왼쪽 자식 노드가 오른쪽 자식 노드만 가질 수 있으며, 공백 노드도 이진 트리의 노드로 포함된다.

​

이진 트리는 노드 수와의 관계에 따라 포화 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree), 편향 이진 트리(Skewed Binary Tree)로 구분된다.

​

포화 이진 트리

포화 이진 트리는 모든 레벨에 노드가 꽉 차있는 이진트리를 말한다. 높이가 h인 이진 트리에서 모든 리프 노드가 레벨 k에 있는 트리이며, 리프 노드 위쪽의 모든 노드는 반드시 두 개의 자식 노드를 거느려야 한다. 포화 이진 트리는 2^k-1 개의 노드를 가지며, 루트 노드를 1번이고하고, 레벨별로 왼쪽에서 오른쪽으로 차례로 번호를 붙인다.

​

완전 이진 트리

완전 이진 트리는 높이가 k이고, 노드 수가 n개 일 때, 노드의 위치가 포화 이진트리에서의 노드 1번부터 n번까지의 위치와 완전히 일치하는 이진 트리이다. 마지막 레벨에서는 노드가 꽉 차있지 않아도 되지만 중간에 빈 공간이 있어서는 안 된다.

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

​

편향 이진 트리

편향 이진 트리는 이진 트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리를 편향 이진트리라고 한다.

왼쪽 편향 이진 트리

​

이진 트리의 구현

이진 트리를 구현하기 위한 방법으로는 배열을 이용하는 방법과 포인터를 이용하는 방법이 있다.

배열을 이용하는 방법은 주로 포화 이진 트리나 완전 이진 트리의 경우 많이 쓰인느 방법이다. 이 방법은 저장하고자하는 이진트리를 완전 이진 트리라 가정하고, 이진 트리의 높이가 k이면 최대 2^k -1개의 공간을 연속적으로 할당한 후, 완전 이진 트리의 번호대로 노드들을 저장한다. 완전 이진 트리의 경우 낭비되는 공간이 없으므로 매우 이상적이다.

완전 이진 트리의 배열 표현

​

하지만 편향 트리에서는 배열로 표현법은 가능하짐나 기억공간의 낭비가 심한걸 알 수 있다.

편향 이진 트리의 배열 표현

​

C++로 포화 이진 트리 구현

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
 
//포화 이진 트리 (0-base)
struct perfect_binary_tree {
    vi v;
    int n;
    perfect_binary_tree(int* arr, int arr_size) {
        v.assign(arr, arr + arr_size);
        n = arr_size;
    }
    perfect_binary_tree(vi& v) {
        this->v = v;
        n = (int)v.size();
    }
    vi preorder() {
        vi ret;
        function<void(int)> dfs = [&](int ix) {
            ret.push_back(v[ix]);
            int l = (ix+1) * 2-1;
            int r = (ix+1) * 2 ;
            if (l < n-1) dfs(l);
            if (r < n-1) dfs(r);
        };
        dfs(0);
        return ret;
    }
};
 
int32_t main()
{
    vi v = { 1,2,3,4,5,6,7,8 };
    perfect_binary_tree t(v);
    vi p = t.preorder();
    for(int a:p)cout << a << ' ';
    return 0;
}