이진트리(Binary Tree) - 트리(Tree)의 기초

이진트리(Binary tree) - 트리(Tree)의 기초

알고리즘과 자료구조를 공부를 하다 보면 후반부에서 스슬 어려워 지기 시작하는 부분이 바로 Tree이다. 

트리의 종류도 이진트리, AVL트리, 레드블랙트리, 세그먼트 트리 등등 여러가지 트리의 종류가 있다.

이번 글에서는 트리의 기초 중 가장 간단하고 실제 많이 사용하는 이진트리에서 대해 알아보자.

본격적으로 이진트리에 대해서 살펴보기에 앞서, 간단하게 트리의 관련 용어부터 정리하고 시작하겠다.

0. 트리 용어 정리

그림에 중요한 용어들을 대충 정리를 해 보았다.

하나씩 설명을 하자면,

트리의 요소 하나 하나를 나타내는 동그라미를 노드(node)라고 한다.

트리는 이 노드들 끼리 부모와 자식의 관계를 형성을 하게 된다.

그 중 부모노드의 부모노드의 ....부모노드 즉 최상단의 노드를 루트노드(root node)라고 한다. 

또 그 중 자식이 없는 노드를 단말 노드(terminal node) 라고 한다.

트리안에 존재하는 트리를 서브트리(subTree)라고 한다.

트리의 높이를 측정하기 위해서 가장 최상단부터 레벨을 매겨 1, 2, 3, ,.....

가장 높은 레벨이 트리의 높이이다.

사실 용어만 보고보면 어려운 것이 없고 익숙해지는 것이 가장 중요할 것 같다.

1. 이진트리(Binary tree) 아이디어

위에서 가볍게 정의한 트리 중 가장 쉬운 트리중에 하나 인 이진트리에 대해서 알아보자.

이진트리는 각 노드가 자식을 최대 2명 가지는 트리를 의미한다.  상당히 간단하다.

하지만 이런 이진트리에는 꾀나 문제점이 발생하게 된다.

이상적으로 이렇게 하나하나 꽉차게 트리가 구성이 된다면 아주 좋은 징조이다.

이렇게 자식이 2개고 꽉찬 트리를 완전이진트리라고 부른다.

이런 완전이진 트리는 각 레벨당 2의 (레벨-1)승(2^level-1)만큼 노드를 가지게 된다.

다른 난이도가 있는 트리들 중 상당수는 완전이진트리 처럼 양쪽의 균형을 맞추는 것을 잘하기 위해서 여러 알고리즘을 사용한다.

이러한 최악의 경우 한쪽으로 계속 쏠리게 되는 형태 또한 이진트리이다. 이러한 경우 사실 트리를 쓰는 이유가 사라지게 된다. 

트리의 특정한 경우지만 이렇게 된다면, 탐색,삽입,삭제,메모리,성능 모든 면에서 배열에 비해 좋은 것이 없다.

수학적인 증명을 하지 않더라도, 저렇게 1자로 편향된 트리를 사용할 꺼면 그냥 배열을 쓰는것이 당연히 구현이나 성능면에서 좋을 것이다.

실제 효율적인 프로그램을 위해서  이진트리보다 좋은 자료구조가 많다. 대표로 들자면 레드블랙 트리가 있다.

하지만 알고리즘 대회등 간단히 트리를 구현해서 사용해야 할 경우에 완전이진트리만큼 좋은 것이 없다.

2. 이진트리 순회

이진트리를 만들었으면 트리에 뭐가있는지, 내가원하는 값이 있는지 확인해야한다.

이진트리의 경우 대표적인 순회 방법 3가지가 있다. 기준은 루트노드 기준이다.

2.1 전위순회(Preorder) - 루트 -> 왼쪽서브트리 -> 오른쪽 서브트리

2.2 중위순회(Inorder) - 왼쪽서브트리 ->루트 -> 오른쪽서브트리

2.3 후위순회(Postorder) - 왼쪽서브트리 -> 오른쪽서브트리 -> 루트

3가지 방법 모두 한가지만 이해를 하면  쉽게 이해 할 수 있다.

3가지 방법중 전위순회를 기준으로 설명을 하겠다.

주황색 : root

파랑색 : 왼쪽 서브트리

노랑색 : 오른쪽 서브트리

그림을 보면 쉽게 이해 할 수 있겠지만 보충설명을 하자면,

가장 처음에는 root노드인 1을 방문을 하게 된다.

그러면 왼쪽에는 2,4,5로 이루어진 서브트리와 오른쪽에는 3,6,7로 이루어진 서브트리가 존재한다.

우리의 순서는 [root -> 왼쪽 -> 오른쪽] 이다. 따라서 왼쪽서브트리로 이동한다.

왼쪽 서브트리로 이동을 하게 되면 2가 서브트리의 루트이고, 4가 왼쪽서브트리 5가 오른쪽 서브트리이다.

똑가시 왼쪽 서브트리로 이동하게 되고, 그 트리의 루트는 4이다.

이런식으로 그림과 같이 반복을 하게 되면 결국엔 모든 노드를 방문할 수 있게 된다.

과정을 이해하였다면, 전위,중위,후위순회 모두 다 재귀로 쉽게 구현 할 수 있다는 것을 알았을 것이다.

또한 추가적으로 전위,중위,후위 순회 중 한두개의 순회 결과를 주고 나머지 한개의 순회순서를 알아낼수 있는데

이것은 내용을 이해하였으면 쉽게 알수 있기 때문에 생략하겠다.

3. 이진트리 구현

이진트리에 대해 알아보았으니 코드를 필수적으로 구현할 줄 알아야 한다.

다른 여러 트리들이 최적화를 위해서 멋있는 스킬들을 사용해서 구현 할 수있지만,

구현할 이진트리의 경우는 쉽게 배열로 구현을 하여도 좋은 성능을 보일 수 있다. 물론 편향된 경우는 어쩔수 없지만.

구현 또한 정말 간단하다.

가장 직관적으로 구현을 하기 위해서 배열의 0번째 칸은 비워두고 구현을 하였다.

잘 보게 되면 , 재밌는 특징이 있는데

자식으로 이동하기위해서는 자신의 인덱스 곱하기 2 를 하면되고,

자신의 부모로 이동하기 위해서는 자신의 인덱스 나누기 2를 하면 된다.

아주 간단한 구현이지만 소스코드는 첨부해 두었다. 간단하게 짯기 떄문에 제대로된 트리를 원한다면 다른 종류의 트리를 이용하는 것을 추천한다.

#include <cstdio>
#define TREESIZE 100
 
class tree {
 
    private: int arr[TREESIZE];
             int size = 1;
 
    public: 
        tree() {
            for (int i = 0; i < TREESIZE; i++) {
                arr[i] = 0;
            }
        }
        void insert(int n) {
            if (size < TREESIZE) {
                arr[size++] = n;
            }
            else {
                printf("Tree is full!");
            }
        }
        void preorder(int root) {
            if (root <= 0 || root >= size) return;
            printf("%d ",arr[root]);
            preorder(root * 2);
            preorder(root * 2+1);
        }
        
};
 
 
 
int main() {
 
    tree sampleTree = tree();
    for (int i = 1; i <= 7; i++) sampleTree.insert(i);
    sampleTree.preorder(1);
 
 
    return 0;
}

깃허브 링크