자료구조(7) : 트리(1) - 트리, 이진트리, 트리 순회

트리(Tree)란?

이번 포스트부터 알아볼 자료구조는 트리이다. 트리는 하나의 뿌리에서 데이터가 가지처럼 뻗어나가는 형식으로,

그 형태 때문에 트리라는 이름이 붙었다. 그림으로 알 수 있는 중요한 정보는, 모든 노드는 부모를 하나만 갖는다는 것이다.

이제 그 정의와 트리에서 자주 사용하는 용어에 대해 알아보자.

 

트리란, 하나 혹은 그 이상 노드들의 유한한 집합을 의미한다. 트리 구조에서는 루트라는 특별한 노드가 존재하고,

루트를 기준으로 배타적인 좌우측 집합을 잘라내면 그 모습도 트리와 똑같다는 특징이 있다. 트리의 분할도 트리란 뜻이다.

• 노드(Node) : 데이터와 함께 다른 노드로의 브랜치를 갖고 있는 요소
• 노드의 차수(Degree of node) : 노드에 연결된 자녀 노드의 개수
• 리프 노드(leaf, Terminal node) : 차수가 0인 노드
• 자녀 노드 : 어떤 노드 X로부터, 서브 트리를 만들었을 때 그 서브 트리의 루트(그냥 자기 자신에서 아래로 이어진 것)
• 형제 노드(Sibling) : 같은 부모 노드를 가진 노드를 sibling 관계라고 한다.
• 트리의 차수(Degree of tree) : max{degree of node}
• 노드 레벨(Node level) : root = level 1, children level = parent level + 1
• 트리의 높이(Height, depth of tree) : max{node level}

알아두면 편한 용어들은 저 정도가 있다. 많아보이지만, 간단한 용어들이니 알고 가도록 하자.

특히, 해당 포스트에서 트리를 다룰 때는 루트 노드의 레벨을 1로 지정할 것이다. 0으로하나 1로하나 큰 차이는 없지만,

미리 알려주어야 후에 레벨을 이용해서 나오는 식들을 이해할 때 헷갈리지 않을 것이다.

트리 표현의 변화

 

가장 처음에는 배열과 포인터를 사용해 시도했었다. 하지만 사진만 봐도 정말 비효율적이지 않은가?

매우 복잡하고 공간의 낭비도 심해 바로 폐기된 방법이다.

 

그 이후에 노드 구조를 사용한 트리의 표현이 시작되었는데, 

맨 처음 구조는, 차수가 k인 트리가 있다면 모든 노드가 k개의 포인터를 갖게끔 설계했다.

즉, 하나의 노드만 자녀가 k개고 나머지는 1개라면, 거의 $n(k-1)+1$개의 메모리를 낭비하게 된다.

 

이때 이런 문제들을 해결하며 등장한 방법이 Left Child-Right Sibling 방식으로 표현하는 것이다.

해당 방법은 노드의 구조가 데이터와, left child, right sibling 포인터 두 개로 구성되어 있다.

3개 필드로 트리 구현이 가능해진 것이다. 이름대로 항상 left 필드에는 자녀 노드로 가는 브랜치만 넣고,

right 필드에는 항상 형제 노드로 가는 브랜치만 연결해준다.

 

그럼 트리를 위의 사진처럼 그릴 수 있다. 형제 노드끼리 같은 레벨에 두어서 더 인식하기 편하게 해주었다.

이 상태에서, right 브랜치들을 시계방향으로 45도 돌려주면 마치 최대 차수가 2인 트리처럼 보이게 된다.

여기서 착안하여 이진 트리라는 개념이 생겨났다. 이진 트리는 기본적으로 Left child-Right child 트리이다.

이진 트리(Binary Trees)

이진 트리는 사실상 트리에서 가장 많이 보게 될 형태이다. 

앞서 이야기했듯이, 최대 두개의 브랜치(자녀 노드)를 가지는 트리이고, left와 right 두 개의 서브트리로 구분된다.

그리고 아무 노드가 없어도 이진 트리가 될 수 있다.(null tree 도 이진 트리라는 뜻이다)

 

엄밀한 정의는, 비어있거나 루트와 두 배타적인 이진 트리로 구성된 노드의 유한한 집합을 이진 트리라고 한다.

이진 트리와 그냥 트리의 차이점에는 크게 두 개가 있는데,

하나는 이진 트리에는 아무 노드도 없는 빈 트리가 존재할 수 있다는 것이고,

나머지는 이진 트리의 경우 자녀의 위치에 따라 트리의 의미가 달라진 다는 것이다.

위에서 left child-right sibling 트리에서 right를 45도 시계방향으로 돌린 것이 이진 트리의 출발이라고 했는데,

그렇기 때문에 밑의 사진과 같은 정리가 되는 것이다.

이진 트리의 특성

이진 트리는 자식 노드가 최대 두 개이기 때문에, 이를 이용해 몇 가지 공식을 만들어낼 수 있다.

예를 들어, level-i 에서 최대 노드 개수는 $2^{i-1}$개이다. 

또, 깊이가 k인 이진 트리의 최대 노드 개수는 $2^k-1$개이다. 이 두 가지는 수학적 귀납법을 통해 증명 가능하다.

 

1. 귀납의 기본 : 루트만 있는 트리, i = 1 일때, $2^0$이므로 1개로 만족한다.
2. 귀납 가정 : 1보다 큰 양수 i에 대해, level이 i-1인 이진 트리의 최대 노드 개수를 $2^{i-2}$개 라고 하자.
3. 귀납 단계 : 귀납 가정에 의해 i-1일때의 노드 개수를 알았고, 이 트리가 최대 노드 개수를 가질때
   그 리프 노드들이 모두 2개씩 자식 노드를 갖는다고 한다면, level이 i일때 노드 개수는 $2^{i-1}$개이다.

이렇게 위의 공식을 증명할 수 있고, 밑의 공식은 위의 공식에 시그마만 씌워주면 증명가능하다.

추가로 리프노드와 차수가 2인 노드에 대해서도 관계를 찾을 수 있다.

 

식부터 보이자면, $n_0 = n_2 + 1$이다.

$n_0$은 리프 노드의 개수고, $n_2$는 차수가 2인 노드의 개수이다.

이 증명은 차수가 1인 노드의 수를 $n_1$으로 두고, $n$을 전체 노드의 개수로 두면 증명 가능하다.

 

그러면 전체 노드의 개수는 리프노드 + 차수가 1 + 차수가 2 이므로, $n_0 + n_1 + n_2$이다.

또, 루트노드를 제외한 모든 노드는 자신의 부모 노드로 향하는 브랜치가 있으므로, $n = B + 1$이다.

여기서 모든 브랜치는 차수가 1이거나 2인 노드에 1개, 2개씩 붙어있으므로, $B = n_1 + 2n_2$이다.

위의 식들을 이용하면 $n = B + 1 = n_1 + 2n_2 + 1$이고, 잘 이항하면 $n_0 = n_2 + 1$ 을 얻는다.

이진 트리의 종류 - Skewed binary tree(편향 이진 트리)

skewed 라는 단어 자체가 편향되었다는 뜻을 가지므로, 트리에 적용하면 한 쪽 방향으로만 내려가는 것을

상상해볼 수 있다. 따라서 skewed tree는 왼쪽 혹은 오른쪽으로 치우친 트리를 이야기한다.

이진 트리의 종류 - Full binary tree(포화 이진 트리)

말 그대로 노드가 꽉 찬 이진트리를 이야기한다. 깊이가 k일때, 트리의 노드 개수가 $2^k-1$개인 트리이다.

완벽하게 차있기 때문에 각 노드에 번호를 순차적으로 쫙 매길 수 있다. Perfect binary tree라고 하기도 한다.

이진 트리의 종류 - Complete binary tree(완전 이진 트리)

 

사실 이 완전 이진 트리를 배우기 위해 앞선 두개를 설명했다.

완전 이진 트리는 깊이 k에서 n개의 노드를 가질 때, 이 n개의 노드가 포화 이진 트리와 똑같이 번호가 매겨진다.

즉, 노드의 위치가 포화 이진 트리 모습과 같아 순차적으로 번호를 매길 수 있다는 것이다.

그러려면 항상 좌측부터 노드를 채워나가는 모습이 될 것이다.

여기까지 보면, 포화 이진 트리가 완전 이진 트리의 특별 케이스임을 단번에 알 수 있다.

 

여기서 알 수 있는 정보는, 완전 이진 트리의 노드가 n개일 때 그 높이는 $\left \lceil log_2(n+1)\right \rceil$ 이라는 것이다.위의 사진도, 노드가 9개 이므로, 위의 식에 대입하면 level이 4로 제대로 나옴을 알 수 있다.

이진 트리의 구현

여기서도 배열과 연결 리스트를 이용한 두 방법으로 소개하겠다.

배열을 통한 구현

1차원 배열을 사용해 노드를 저장할 것이다. 트리가 완전 이진 트리라고 가정하면, 몇 가지 규칙을 만들 수 있다.

1. i번 노드의 부모 노드 : $ \left \lceil i/2 \right \rceil$, (if i != 1)
2. i번 노드의 왼쪽 자식 노드 : $2i$, (if 2i <= n)
                                               has no left child, (if 2i > n)
3. i번 노드의 오른쪽 자식 노드 : $2i+1$, (if 2i+1 <= n)
                                                   has no right child, (if 2i+1 > n)

이렇게 규칙을 정하고 노드를 저장하면, 완전 이진 트리의 경우는 공간 낭비가 없지만

편향 이진 트리의 경우는 최악의 경우 $2^k-1$개 중 단 k개만 사용하는 대참사가 발생하게 된다.

대참사..

연결 리스트를 통한 구현

위에서도 대충 노드를 사용한 트리의 표현을 설명했는데, 여기서도 마찬가지다.

모든 노드는 세 개의 필드를 가지며, 각각 데이터와 좌우측 자녀 노드로 가는 링크를 갖는다.

template<class T> class Tree; // 먼저 선언

template <class T>
class TreeNode { 
    friend class Tree<T>;
    
    private:
        T data;
        TreeNode<T> *leftChild;
        TreeNode<T> *rightChild;
};

template<class T>
class Tree {
    
    public:
        // Tree operations
        ...
    
    private:
        TreeNode<T>*root;
};

 

하지만 이런 상태에서는 특정 노드의 부모 노드가 무엇인지 추적하기가 힘들다.

그래서 필요에 따라 parent 의 링크를 저장하는 필드를 하나 추가하기도 한다.

앞서 배운 이진 트리의 종류를 연결 리스트를 사용해 표현하면 다음과 같다.

이진 트리 순회와 트리 반복자

트리를 순회한다는 것은 트리의 모든 노드를 딱 한 번씩만 방문한다는 이야기이다.

순회는 어디를 먼저 방문하느냐에 따라 6개로 나뉜다. 선택지가 L(moving left), V(visiting the node), R(moving right) 여서,

세 개로 순열을 만드는 경우의 수를 구하면 6개다. 우리는 그 중 세 종류(LVR, VLR, LRV)만 알면 된다.

왼쪽 먼저 방문한다고 가정하고, V의 위치에 따라 나누면 저렇게 세 가지가 나온다.

 

이때 LVR을 중위 순회, VLR을 전위 순회, LRV를 후위 순회라고 부른다. 해당 트리를 기준으로 알아보자.

중위 순회(Inorder Traversal, LVR)

중위 순회는 LVR 방식으로, 계속 좌측 자식 노드로 이동해 더 이상 자식 노드가 없을 때 까지 이동한 후,

좌측으로 갈 길이 없거나 이미 방문했을 때 현 위치를 V(visit)하고, 우측 자식 노드로 이동하는 방법이다.

위의 트리를 기준으로 하면, 계속 좌측으로 내려가 A에 도달한 후에 더 이상 없으니 A를 방문하고,

우측은 없으니 다시 /로 돌아온다. 그럼 /의 기준에서는 이미 L은 갔으니, 자신을 방문하고, 우측으로 간다.

이런 식으로 계속해서 반복해주면 순회 결과는 A/B*C*D+E 가 될 것이다.

해당 순회 방식은 스택을 사용해서 구현해줄 수 있다.

 

이렇게 V를 어디서 하느냐에 따라 방법이 달라지는 식이다. 지금은 중위 순회만 알아보고,

후에 다른 것을 설명하며 같이 이야기하도록 하겠다. 여기선 별개의 순회 방법들을 알아볼 것이다.

레벨 순서 순회(Level-Order Traversal)

이 방법은 이름 그대로 레벨 순서대로 순회하는 방식이다. 루트를 먼저 방문하고, 좌 우측 자식 노드를 방문한다.

해당 방식은 큐를 사용해 구현할 수 있다. 레벨 순서로 순회하니 순회 결과는 +*E*D/CAB 가 될 것이다.

template <class T>
void Tree<T>::LevelOrder() {

    Queue<TreeNode<T>*> q;
    TreeNode<T> *currentNode = root;
    while(currentNode) {
    
        Visit(currentNode);
        if(currentNode->leftChild) q.Push(currentNode->leftChild);
        if(currentNode->rightChild) q.Push(currentNode->rightChild);
        if(q.IsEmpty()) return;
        
        currentNode = q.Front();
        q.Pop();
    }
}

 

이런 식으로 큐를 이용해 간단하게 구현할 수 있다.

 

중위 순회를 설명하면서 스택을 사용해 구현한다고 했는데, 이는 스택이 있어야 부모 노드로 되돌아 갈 수 있기 때문이다.

그럼 스택 없이도 순회할 수 있는 방법은 없는걸까? 당연히 존재한다.

기본적으로는 노드의 구조를 바꿔서 해줄 수 있다. 노드에 부모 노드로 돌아가는 필드를 추가해주면 된다.

그리고 두 번째는, 이진 트리를 스레드 이진 트리로 표현해주는 것이다. 아직 알아보진 않았지만, 후에 알아볼 것이다.

스레드 이진 트리를 사용하면 다시 루트로 돌아가는 주소를 리프 노드에 저장할 수 있다.

충족 가능성 문제 풀이(Sovling SAT with Postorder traversal)

충족 가능성 문제(SAT)란, 어떤 명제가 주어졌을 때, 해당 명제가 참이 되게 하는 변수들의 값을 지정하는 문제이다.

예를 들어, $ x_1 \vee (x_2 \wedge \sim x_3)$라는 식이 주어지면, 각각 변수에 참과 거짓 중 어떤 값이 들어가야 참일까?

$x_1$이 True라면 항상 참이 되고 그런 식이다. 이렇게 변수가 적고 명제가 간단하면 금방 구할 수 있지만,

문제는 변수도 많고 명제도 복잡하게 얽혀있는 경우이다.

 

만약 식이 $(x_1 \wedge \sim x_2) \vee (\sim x_1 \wedge x_3) \vee \sim x_3$ 이처럼 복잡하다면, 금방 찾기가 어렵다.

이런 경우를 트리와 후위 순회를 이용하여 풀어낼 수 있다.

그 전에 가장 간단한 방법은 모든 경우의 수에 대해 T, F를 넣어가며 값을 확인하는 것으로, 진리표를 이용한다고도 한다.

그렇다면 변수의 개수가 n개일 때, 각 변수마다 T, F 두 개의 값이 들어갈 수 있으므로 $2^n$개의 경우의 수가 나온다.

각 경우에 대해 결과가 참인지 거짓인지 판별하는 시간이 존재하므로, 브루트포스 방법은 $O(g*2^n)$이 걸린다.

이때 그 결과를 판별하는 방식을 트리를 후위 순회하여 판별해줄 것이다. 위처럼 명제를 쪼개어 트리로 만든 후,

리프 노드의 변수에 경우의 수에 따른 T, F값을 채워넣은 뒤 후위 순회해주면 전체 식의 진리값이 나온다.

이런 성질을 이용해 후위 순회를 이용하면 각 경우에 대해 판별해줄 수 있다.

이렇게 순회해 하나의 경우라도 T가 나오면, 충족 가능성 문제를 해결하는 것이다.

for each of the 2n  possible truth value combinations for the n variables {

    Replace the variables by their values in the current truth value combination;
    Evaluate the formula by traversing the tree it points to in postorder;
    if(formula.Data().second()) {cout << current combination; return;}	// 하나라도 true
}

cout <<“no satisfiable combination”; 	// 계속 false만 나온 경우

 

위는 후위 순회를 이용한 SAT를 푸는 알고리즘을 거의 자연어에 가깝게 작성해둔 것이다.

여유가 있다면 직접 해보는 것을 추천한다. 백준에도 이런 종류의 후위 표현법을 이용한 문제들이 있다.

 

 

내용이 길어질 것 같아 첫 포스트는 여기서 마무리하고, 이후에 작성하겠다.

트리는 내용이 많아 세 개의 포스트로 나뉠 수도 있을 것 같다!