[자료구조] 트리? + 이진 트리 (Binary Tree)

728x90

1. 트리

1.1 트리란?

트리(Tree)란 계층적인 구조를 나타내는 자료구조이다.

이전에 다룬 스택(Stack)과 큐(Queue)와 같은 선형 구조와 달리 트리는 비선형 구조이며, 나무를 거꾸로 그린 형태이다.

1.2 트리 용어

노드(node): 트리를 구성하는 기본 원소
루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
리프 노드(leaf (node))/단말 노드(terminal node): 자식이 없는 노드
간선(edge): 노드간의 연결
레벨(level): 루트 노드(level=1)부터 노드까지 연결된 링크 수의 합
높이(height): 가장 긴 루트 경로의 길이
차수(degree): 각 노드의 자식의 개수
트리의 차수(degree of tree): 트리의 최대 차수 = max[deg1, deg2, ..., degn]
경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
길이(length): 출발 노드에서 도착 노드까지 거치는 노드의 개수
깊이(depth): 루트 경로의 길이
크기(size): 노드의 개수
너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기

1.3 트리 구현의 문제점

만약 하나의 노드가 여러개의 자식노드를 가지는 불규칙한 트리의 경우 node를 구현하기가 상당히 복잡해진다.

이러한 이유로 실제로는 하나의 노드가 2개의 자식노드만 가지는 이진트리가 많이 사용된다.

2. 이진트리

2.1 이진트리란?

이진트리(Binary Tree)란 모든 노드의 차수가 최대 2인 형태의 트리이다.

서브트리는 공집합일 수 있으며 반드시 왼쪽 서브트리와 오른쪽 서브트리가 서로 구별되어야 한다.

2.2 이진트리 ADT

객체

노드와 간선의 집합
노드는 공집합이거나 공집합이 아닌 경우 루트노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성됨
모든 서브트리도 이진트리임

연산

create() : 이진트리 생성
insertNode(n) : 이진트리에 노드 n 삽입
deleteNode(n) : 이진트리에서 노드 n 삭제
isEmpty() : 이진트리가 공백 상태인지 확인
getRoot() : 이진트리의 루프노드 반환
getCount() : 이진트리의 노드 개수 반환
getHeight() : 이진트리의 높이 반환
display() : 이진트리의 내용 출력

2.3 일반트리 → 이진트리 변환

그렇다면 자식노드의 개수가 2개 이상인 트리는 구현이 불가능한 것일까?

아니다. 대부분의 트리는 이진트리로 변환이 가능하다.

예를 들어 아래의 그림에서 왼쪽 트리는 오른쪽 이진트리로 변환이 가능하다.

이해가 되는가?

일반트리에서 첫 번째 자식노드를 이진트리에서는 왼쪽 서브트리에 위치시킨다.

나머지 형제노드는 이진트리에서 오른쪽 서브트리에 위치된다.

위와 같은 방법을 통해 이진트리로 변환하여 구현하면 보다 간단하게 구현이 가능하다.

2.4 이진트리 종류

포화 이진트리 (Full Binary Tree)

트리의 각 레벨에 노드가 완전히 채워져있는 이진트리를 뜻한다.

모든 leaf 노드는 같은 level에 있어야하며, 마지막 level의 노드의 개수는 최대가 되어야 한다.

완전 이진트리 (Complete Binary Tree)

마지막 level을 제외한 모든 level의 노드가 완전히 채워져 있으며, 마지막 level의 노드들은 왼쪽부터 순차적으로 채워져 있는 이진트리를 뜻한다.

2.5 이진트리의 성질

이진트리에서의 edge 개수

이진트리에서 루트 노드를 제외하고 모든 노드가 하나의 부모 노드를 가지고 있다.
∴ n개의 노드의 이진트리에서 간선(edge)의 개수는 n-1개이다.

같은 높이의 이진트리에서 노드의 최소·최대 개수

이진트리에서 하나의 레벨에는 최소한 하나의 노드가 존재해야 한다.
또한 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 level $i$에서의 노드의 최대 개수는 $2^{i-1}$이다.
즉 높이가 h인 이진트리의 최대 노드 개수는이다.
∴ 높이가 h인 이진트리에서 최소 노드의 개수는 h개이며,최대 노드의 개수는 $\sum_{i=1}^{h}{2^{i-1}} = 2^h-1$ 개이다.

노드의 개수가 동일한 이진트리의 최소·최대 높이

하나의 레벨에서 최소한 하나의 노드는 있어야 하므로 최대 높이는 n을 넘을 수 없다.
또한 $n ≤ 2^h - 1$ 이므로 $h ≥ log_2(n+1)$ 이다. (h가 정수이므로 올림 처리를 해야 함)
∴ n개의 노드를 가지는 이진트리에서 최소 높이는 $h ≥ \lceil{log_2(n+1)}\rceil$ 이며, 최대 높이는 n이다.

2.6 이진트리 구현 (Array? Link?)

아래와 같이 배열을 이용해 이진트리를 구현할 수 있다.

특정한 상황에서 완전 이진트리 또는 포화 이진트리의 경우 배열을 이용하면 효과적으로 구현할 수 있다.

하지만 일반적으로 배열로 이진트리를 구현하는 경우 메모리 낭비가 심할뿐더러 배열에 크기에 따라 트리의 높이가 제한된다.

따라서 대부분의 경우 Link를 이용하여 이진트리를 구현한다.

Link를 이용하여 이진트리를 구현하는 방법은 LinkedList를 구현하는 방법과 유사하다.

각 노드는 data 속성과 2개의 Link 속성을 가진다.

여기서 Link 속성은 각각 왼쪽 서브트리와 오른쪽 서브트리의 노드 주소를 가리키는 2개의 포인터 변수를 뜻한다.

따라서 한 노드를 root 노드로 지정하면, 노드간의 Link를 통해 이진트리가 구성되는 것이다.

2.7 Link를 이용한 이진트리 구현 (C++)

#include <iostream>
using namespace std;

template <typename T>
struct Node{
private:
    T data;
    Node* left;
    Node* right;
public:
    Node(T _data, Node* _left, Node* _right){
        data = _data;
        left = _left;
        right = _right;
    }
    ~Node(){}

    // getter/setter
    T getData(){
        return data;
    }
    void setData(T _data){
        data = _data;
    }
    Node* getLeft(){
        return left;
    }
    void setLeft(Node* _left){
        left = _left;
    }
    Node* getRight(){
        return right;
    }
    void setRight(Node* _right){
        right = _right;
    }

    // is leaf node?
    bool isLeaf(){
        return left==nullptr && right==nullptr;
    }
};

template <typename T>
class BinaryTree{
private:
    Node<T>* root;
public:
    BinaryTree(){
        root = nullptr;
    }
    ~BinaryTree(){}

    void setRoot(Node<T>* _root){
        root = _root;
    }

    Node<T>* getRoot(){
        return root;
    }

    bool isEmpty(){
        return root == nullptr;
    }

};

int main(){
    BinaryTree<char> tree;

    // Create Node
    Node<char> *d = new Node<char>('D', nullptr, nullptr );
    Node<char> *e = new Node<char>('E', nullptr, nullptr );
    Node<char> *b = new Node<char>('B', d, e );
    Node<char> *f = new Node<char>('F', nullptr, nullptr );
    Node<char> *c = new Node<char>('C', f, nullptr );
    Node<char> *a = new Node<char>('A', b, c );

    // Create Tree
    tree.setRoot(a);

    return 0;
}

main() 에서 위 그림과 같은 이진트리를 생성하였다.

2.8 이진트리 순회

트리는 선형 구조의 자료구조가 아니기 때문에 노드들을 방문할 규칙을 선택해야 한다.

표준적인 방법에는 전위, 중위, 후위 순회 방법이 있으며 재귀호출을 통해 이를 구현한다.

대부분의 경우 위 3가지 방법으로 트리를 순회하며 문제를 해결할 수 있다.

하지만 이외의 경우 개발자는 각각의 상황에 맞게 트리를 순회하는 알고리즘을 작성하여 이용하면 된다. (레벨 순회 등)

전위 순회(Pre-order Traversal)

루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문하는 순회 방법

void preorder(Node<T>* node){
    if(node != NULL){
        cout << node->getData() << " ";
        preorder(node->getLeft());
        preorder(node->getRight());
    }
}

중위 순회(In-order Traversal)

왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 방문하는 순회 방법

void inorder(Node<T>* node){
    if(node != NULL){
        inorder(node->getLeft());
        cout << node->getData() << " ";
        inorder(node->getRight());
    }
}

후위 순회(Post-order Traversal)

왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순서로 방문하는 순회 방법

void postorder(Node<T>* node){
    if(node != NULL){
        postorder(node->getLeft());
        postorder(node->getRight());
        cout << node->getData() << " ";
    }
}

레벨 순회(Level-order Traversal)

레벨 순서로 방문하는 순회 방법

너비 우선 순회(Breadth-First traversal)라고도 함

void levelorder(){
    cout << "Levelorder: [ ";
    if(!isEmpty()){
        queue<Node<T>*> q;
        q.push(root);
        while(!q.empty()){
            Node<T>* node = q.front();
            q.pop();
            if(node != NULL){
                cout << node->getData() << " ";
                q.push(node->getLeft());
                q.push(node->getRight());
            }
        }
    }
    cout << "]" << endl;
}

위에서 구현한 이진트리를 각각의 순회 방법으로 출력한 결과이다.