트리

개관

트리는 기본적으로 계층 관계를 갖는 객체들을 표현하기 위해 만들어진 자료 구조이다. 하지만 사실 그 이외에도 많은 용도로 사용되곤한다. 실제 계층 관계가 없는 자료들이라고 해도 말이다.

1 트리의 구현과 순회

1.1 도입

선형으로 표현하기 어려운 형태의 자료 중 가장 일반적인 것이 바로 계층 구조이다. 이 계층 구조를 표현하기 위해서 필요한 것이 바로 트리이다.

기초적인 정의와 용어

트리의 구성 요소 : 트리는 자료가 저장된 node들이 edge(간선(으로 서로 연결되어 있는 자료 구조를 말한다. node간에는 상/하위 관계가 있으며, 두 node가 연결되었을 때 한 node는 좀 더 상위, 다른 node는 좀 더 하위에 있어야 한다.
node들간의 관계를 지칭하기 위해서 보통 가계도에서 잘 사용하는 용어를 가져다 온다. 두 연결된 노드 중 상위를 부모(parent)라고 부르며, 하위를 자식(child)라고 부른다. 또한 같은 부모를 둔 자식들을 형제(sibling)라고 부르고, 자식과 그의 자식들을 통들어 자손(descendant)라고 부른다.
node는 여러 개의 자식을 가질 수 있지만 부모는 반드시 하나만 가질 수 있다. 이 속성들은 궁극적으로 모든 node들이 하나의 부모로 수렴한다는 특징을 가지게 해준다. 이 최상위 단의 node를 루트 또는 뿌리라고 부른다. 반대로 자식이 하나도 없는 node들를 트리의 잎 node혹은 leaf라고 부른다.
트리와 노드의 속성 : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 해당 노드의 깊이(depth)라고 한다. 따라서 깊이가 깊을수록 트리 아래쪽에 있는 노드를 지칭하게 된다. 트리에서 가장 깊숙히 있는 노드의 깊이를 이 트리의 높이라고 한다.
트리의 재귀적 속성 : 트리가 유용한 이유는 트리가 재귀적인 성질을 갖고 있기 때문이다. 트리에서 한 노드와 그의 자손들을 모두 모으면 그들도 하나의 트리가 되는 것이다. 위의 그림을 예로 든다면 자료 구조의 자식인 탐색형 자료 구조 역시 하나의 트리가 되는 것을 확인할 수 있다. 이때 어떤 노드t와 그 자손들로 구성된 트리를 ‘t를 루트로 하는 서브트리’라고 말한다. 따라서 모든 트리는 루트와 루트 밑에 있는 서브트리들의 집합이라고 말할 수 있다. 이와 같은 특징 덕분에 트리를 다루는 코드들은 대개 재귀 호출을 이용하여 구현된다.

트리의 표현 : 구현의 방법에 있어서 정해져 있는 것은 없지만, 그 중 가장 일반적인 형태는 각 노드를 하나의 구조체/객체로 표현하고, 이들을 서로의 포인터로 연결하는 것이다. 이때 각 노드들은 자신의 부모와 모든 자손들에 대한 포인터를 가지고 있다.

Struct TreeNode{
    String label; //저장할 데이터
    TreeNode* parent; //부모 노드를 가리키는 포인터
    Vector<TreeNode*> children; // 자손 노드들을 가리키는 포인터 배열
};

이 코드는 트리의 가장 기본적인 형태를 나타내고 있으며 자식의 개수를 무한정 받아낼 수 있도록 설계되어 있다. 하지만 트리의 가장 유명한 형태인 ‘이진 트리’의 경우 단 두개의 자식만 만들 수 있기 때문에 그 경우, left와 right자식 변수만 가지고 있을 것이다.

1.2 트리의 순회
하나의 트리에 소속된 데이터들을 순회하는 것은 귀운 일이 아니기 때문에 하나의 로직을 재귀적으로 타고 들어가는 작업들을 하도록 만드는게 일반적이다. 모든 트리는 각 자식들을 루트로 하는 서브트리와 루트로 나눌 수 있으므로, 트리의 루트가 주어질 때 루트를 ‘방문’한 뒤 각 서브트리를 재귀적으로 방문하는 함수를 만들어 트리의 모든 노드를 순회할 수 있다. 이 개념의 구현은 다음과 같다.

void printLabel(TreeNode* root)
{
    cout << root->label >> endl;

    for (int i = 0; i < root->children.size(); i++)
        printLabel(root->children[i]);
}

순회의 다른 예로는 트리의 높이를 구하는 문제가 있다. 이것은 서브트리의 개념을 이용하여 구할 수 있는데, 서브트리들의 높이들을 구해가며 마지막에 도달했을 때 그 중 최대치에다가 1을 더하면 전체 높이가 되는 것이다.

int height(TreeNode* root)
{
    int h = 0;
    for (int i = 0; i < root->children.size(); i++)
    {
        h = max(h, 1 + height(root->children[i]));
    }
    return h;
}

1.3 트리 순회 문제 풀이

순회에 대한 문제를 한 가지 풀어보겠다. 자식 노드의 개수가 최대 2개인 이진 트리를 입력 받아서 전위 순회, 중위 순회, 후위순회를 한 결과를 출력하는 프로그램을 만드는 문제이다.
이진 트리의 순회의 경우 방법은 다음 3가지이다.
(1) 전위 순회 : 루트->왼쪽 자식->오른쪽 자식
(2) 중위 순회 : 왼쪽 자식 -> 루트 -> 오른쪽 자식
(3) 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 루트

방법 1. 완전 탐색의 느낌으로 전체 크기의 벡터를 만들고 요소 하나하나를 제 자리에 넣는 방식으로 처리(실패).
실패 이유 : 문제를 제대로 읽지 않아서 트리가 루트부터 시작해 순서대로 들어온다고 착각했다. 그렇게 되었을 때 입력을 받게 되면 런타임에러를 불러올 수 있는 것을 확인했다.

방법 2. 이전에 만들었던 Node 구조체를 2차원 배열로 처리했다. 이렇게 되었을 때 인덱싱에 대한 문제가 사라짐을 느꼈고, 또한 문제에서 주어진 조건이 노드를 구성할 때 알파벳 순으로 한다고 했기 때문에, 인덱스를 문자-'A'라고 하면 0부터 차례대로 정렬됨을 알 수 있었다. 이렇게 하면 이후 굳이 완전 탐색으로 자식노드를 찾을 필요가 없었다.