Tree

트리

트리는 계층 구조를 표현하는 자료구조이다. 트리는 다양한 목적으로 사용되어 다양한 종류의 트리들이 등장했다. 

• 현실 세계 계층 구조 표현
• 이진 검색 트리
• 힙
• 세그먼트 트리
• 유니온-파인드
• 트라이 등등

트리 용어

node(노드) : 트리 구성 요소

edge(간선) : 노드와 노드를 연결한 선

parent : 두 노드가 간선으로 연결되었을 때 상위 노드

child : 두 노드가 간선으로 연결되었을 때 하위 노드

sibling : 같은 부모를 가지는 자식 노드들

ancestor : 부모 노드와 그 부모 노드의 상위 노드들

descendant : 자식 노드와 그 자식 노드의 하위 노드들

root : 부모가 없는 최상위 노드

leaf : 자식이 없는 노드

Internal : 리프 노드가 아닌 노드

depth : 루트에서 어떤 노드에 도달하기 위해 거치는 간선의 수

level : 특정 깊이를 가지는 노드의 집합

height of the tree : 깊이가 가장 큰 노드의 깊이가 트리의 높이가 됨 

 

트리 노드 간에는 간선으로 연결되어 있다. 트리 노드 간에는 상, 하위(부모, 자식) 관계가 존재하며 노드는 여러 개의 자식을 가질 수 있지만 부모는 하나만 가질 수 있다.

 

사실 트리도 그래프에 속한다. 트리는 사이클이 없는 연결그래프이기 때문이다. 하지만 그래프 정점들은 자유롭게 연결될 수 있는 반면 트리의 노드들은 계층 구조를 유지하기 위해 위 제약 사항(부모 하나, 부모와 자식하고만 연결됨)을 지켜야한다는 점에서 차이가 있다.

 

트리는 재귀적인 구조를 갖고 있다. 트리의 각 노드들은 자신을 루트로하는 서브 트리이다. 서브 트리가 반복되는 재귀적인 구조 탓에 트리를 다루는 코드들은 재귀 함수를 많이 사용한다.

트리 구현

트리는 굉장히 다양한 방법으로 구현할 수 있다. 이 중 가장 일반적인 방법은 연결리스트로 구현하는 방법이다. 노드를 구조체/객체로 표현하고 포인터로 연결시킨다. 각 노드는 부모 노드의 포인터와, 모든 자손의 포인터를 갖게 된다. 아래는 해당 방법을 구현한 코드이다.

public class TreeNode {
    int value;
    TreeNode parent;
    LinkedList<TreeNode> children;
    public TreeNode(int value) {
        this.value = value;
        children = new LinkedList<>();
    }
}

class Test {
    public static void main(String[] args) {
        //트리 생성
        TreeNode root = new TreeNode(5);
        TreeNode node1 = new TreeNode(6);
        TreeNode node2 = new TreeNode(7);
        TreeNode node3 = new TreeNode(8);

        //root의 자식으로 node1 삽입
        root.children.add(node1);
        node1.parent = root;

        //root의 자식으로 node2 삽입
        root.children.add(node2);
        node2.parent = root;

        //node1의 자식으로 node3 삽입
        node1.children.add(node3);
        node3.parent = node1;
    }
}

이 방법 외에도 이진 트리의 경우 left, right 포인터를 갖는 노드의 연결 리스트로 구현하며 힙은 노드가 들어 갈 자리가 비어 있을 수 없기에 배열로 트리를 구현한다. union-find 알고리즘의 경우 단순히 부모 노드를 가리키는 포인터만으로 트리를 구현한다.

 

또한 트리는 그래프의 일종이다. 그러므로 그래프의 구현 방법인 인접 리스트, 인접 행렬로도 구현할 수 있다. 다만 트리의 간선은 정점의 개수 V-1개이고 각 노드의 간선은 최대 2개이므로 인접 행렬로 잘 구현하지 않는다. DFS, BFS 등 그래프의 알고리즘도 적용 가능하다. 다만 트리를 인접 리스트, 인접 행렬로 구현해도 트리의 계층 성질은 사라지지 않는다.

 

이처럼 트리의 구현 방법은 다양하기 때문에 여러 구현 방법을 익혀 풀고자 하는 문제와 트리의 목적에 맞춘 구현이 필요하다.

트리 순회

트리는 재귀 구조를 갖기 때문에 간단한 재귀 함수로 모든 트리 노드를 방문할 수 있다. 아래는 트리의 모든 노드들을 출력하는 코드이다.

static void printLabels(TreeNode root, StringBuilder sb) {
        sb.append(root.value).append(' ');

        if(root.children == null) return;
        for(TreeNode child : root.children) {
            printLabels(child, sb);
        }
    }

순회의 또 다른 사용 예로 트리의 높이를 구할 수 있다. 트리의 높이는 서브 트리의 높이 중 최대 치 + 1이기 때문에 재귀적으로 각 서브 트리의 높이를 구하면서 최종적으로 트리의 높이를 구할 수 있다. 같은 원리로 트리의 자식 수 등의 정보도 쉽게 구할 수 있다.

이진 트리 순회

이진 트리란 모든 노드들이 왼쪽과 오른쪽으로, 최대 2개의 자식을 갖는 트리를 말한다. 위에서는 자식 개수가 정해지지 않았지만 이진 트리의 노드는 왼쪽 자식과 오른쪽 자식만 가지기에 연결 리스트로 구현 시 아래와 같이 트리 노드를 정의할 수 있다.

public class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
    BinaryTreeNode(int value) {
        this.value = value;
    }
}

이진 트리 순회도 트리 순회의 원리와 같다. 하지만 루트 노드를 언제 방문하느냐에 따라 아래 3가지 방문(순회) 순서가 나온다. 

 

전위 순회(preorder traverse) :  루트 노드 방문 - 왼쪽 서브 트리 방문 - 오른쪽 서브 트리 방문

중위 순회(inorder traverse) : 왼쪽 서브 트리 방문 - 루트 노드 방문 - 오른쪽 서브 트리 방문

후위 순회(postorder traverse) : 왼쪽 서브 트리 방문 - 오른쪽 서브 트리 방문 - 루트 노드 방문