4. 트리와 그래프 - 트리편

▶ 트리의 종류

트리를 이해하기 위한 좋은 방법 중 하나는 재귀적 설명법을 사용하는 것이다. 트리는 노드로 이루어진 자료구조이다.

- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

추가적으로,

트리에는 사이클이 존재하지 않는 점, 노드들은 특정 순서로 나열될 수도 있고, 그럴 수 없을 수도 있다는 점, 각 노드는 어떤 자료형으로도 표현 가능한 점, 각 노드는 부모 노드로의 연결이 있을 수도 있고, 없을 수도 있다는 점 등이 있다.

 

Node클래스를 가장 간단하게 정의하면 다음과 같다.

class Node {
	public String name;
    public Node[] children;
}

트리 vs 이진 트리

이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리를 말한다. 모든 트리가 이진 트리는 아니다. 즉, 하나라도 두개를 초과하는, 예를 들어 세 개의 자식 노드를 가지고 있다면 그것은 삼진 트리라고 부른다.

 

이진 트리 vs 이진 탐색 트리

이진 탐색 트리는 모든 노드가 다음과 같은 특정 순서를 따르는 속성이 있는 이진 트리를 일컫는다.

모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들

물론 모든 n에 대해 반드시 참이어야만 한다.

부등식의 경우에 대해서는 바로 아래 자식뿐만 아니라 내 밑에 있는 모든 자식 노드들에 대해서 참이어야 한다. 모든 트리에 대해서 이진 탐색 트리라고 단정짓기 쉬운데, 확실히 짚고 넘어가야 하는 부분이다. 이진 탐색 트리는 모든 노드에 대해 그 왼쪽 자식들의 값이 현재 노드 값보다 작거나 같도록 하고, 그리고 오른쪽 자식들의 값은 현재 노드의 값보다 반드시 커야 한다.

 

균형 vs 비균형

많은 트리가 균형 잡혀 있긴 하지만 전부 그런 것은 아니다. 균형을 잡는다는 것이 왼쪽과 오른쪽 부분 트리의 크기가 완전히 같게 하는 것을 의미하는 것이 아니다. 균형 트리인지 아닌지 확인하는 방법 중 하나는 너무 불균형한 것은 아닌지 확인 하는 것 이상의 의미를 갖는다. O(logN) 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀 있지만, 그렇다고 꼭 완벽하게 균형 잡혀 있을 필요는 없다.

 

완전 이진 트리

완전 이진 트리는 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리를 말한다. 마지막 단계는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

 

전 이진 트리

전 이진 트리는 모든 노드의 자식이 없거나 정확히 두 개 있는 경우를 말한다. 즉 자식이 하나만 있는 노드가 존재해서는 안 된다.

 

포화 이진 트리

포화 이진 트리는 전 이진 트리이면서 완전 이진 트리인 경우를 말한다. 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대개 되어야 한다. 포화 이진 트리는 노드의 개수가 정확히 2의 k-1승(k는 트리의 높이)개여야 한다는 점에서 흔하게 나타나는 경우는 아니다.

▶ 이진 트리 순회

중위 순회

중위 순회는 왼쪽 가지, 현재 노드, 오른쪽 가지 순서로 노드를 방문하고 출력하는 방법을 말한다.

void inOrderTraversal(TreeNode node) {
	if(node != null) {
    	inOrderTraversal(node.left);
        visit(node);
        inOrderTraversal(node.right);
    }
}

전위 순회

전위 순회는 자식 노드보다 현재 노드를 먼저 방문하는 방법을 말한다. 전위 순회에서 가장 먼저 방문하게 되는 노드는 언제나 루트이다.

void preOrderTraversal(TreeNode node) {
	if(node != null) {
    	visit(node);
    	preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

후위 순회

후위 순회는 모든 자식 노드들을 먼저 방문한 뒤 마지막에 현재 노드를 방문하는 방법을 말한다. 후위 순회에서 가장 마지막에 방문하게 될 노드는 언제나 루트이다.

void postOrderTraversal(TreeNode node) {
	if(node != null) {
    	postOrderTraversal(node.left);
        postOrderTraversal(node.right);
    	visit(node);
    }
}

▶ 이진 힙(최소힙과 최대힙)

최소힙은 트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있다는 점에서 완전 이진 트리이며, 각 노드의 원소가 자식들의 원소보다 작다는 특성이 있다. 따라서 루트는 트리 전체에서 가장 작은 원소가 된다.

최소힙에는 insert와 extract_min이라는 핵심 연산 두 가지가 존재한다.

삽입

최소힙에 원소를 삽입할 때는 언제나 트리의 밑바닥에서부터 삽입을 시작하며, 완전 트리의 속성에 위배되지 않도록 새로운 원소는 밑바닥 가장 오른쪽 위치로 삽입된다. 그 다음에 새로 삽입된 원소가 제대로 된 자리를 찾을 때까지 부모 노드와 교환해 나간다. 기본적으로 이와 같은 방식으로 최소 원소를 위쪽으로 올린다.

최소 원소 뽑아내기

최소힙에서 최소 원소를 찾기란 쉬운 일이다. 최소 원소는 언제나 가장 위에 놓인다. 사실 이 최솟값을 어떻게 힙에서 제거하느냐가 까다로운 부분이 된다.

최소 원소를 제거한 후에 힙에 있는 가장 마지막 원소와 교환한다. 그 다음 최소힙의 성질을 만족하도록, 해당 노드를 자식 노드와 교환해 나감으로써 밑으로 내보낸다. 그런데 왼쪽 자식과 오른쪽 자식 중 누구와 교환해야 할까. 그것은 원소의 값이 무엇이냐에 따라 달라진다. 왼쪽 원소와 오른쪽 원소가 어떤 순서 관계가 있는 것은 아니지만 최소힙의 속성을 유지하기 위해선 더 작은 원소와 교환해 나가야 한다.

▶ 트라이(접두사 트리)

트라이는 n-차 트리의 변종으로 각 노드에 문자를 저장하는 자료구조이다. 따라서 트리를 아래쪽으로 순회하면 단어 하나가 나온다. 널 노드라고도 불리우는 '*노드'는 종종 단어의 끝을 나타낸다. 예를 들어, MANY라는 단어가 완성되었음을 알리는 것이다. MA라는 경로가 존재한다는 사실은 MA로 시작하는 단어가 있음을 알려준다. '*노드'의 실제 구현은 특별한 종류의 자식 노드로 표현될 수도 있다. 예를 들어, TrieNode를 상속한 TerminatingTrieNode로 표현될 수도 있다. 아니면 '* 노드'의 '부모 노드' 안에 불린 플래그를 새로 정의함으로써 단어의 끝을 표현할 수도 있다.

 

트라이에서 각 노드는 1개에서 ALPHABET_SIZE + 1개까지 자식을 갖고 있을 수 있다. 접두사를 빠르게 찾아보기 위한 아주 흔한 방식으로, 모든 언어를 트라이에 저장해 놓는 방식이 있다. 해시테이블을 이용하면 주어진 문자열이 유효한지 아닌지 빠르게 확인할 수 있지만, 그 문자열이 어떤 유효한 단어의 접두사인지 확인할 수는 없다.이는, 트라이를 이용하면 아주 빠르게 확인할 수 있다.

 

유효한 단어 집합을 이용하는 많은 문제들은 트라이를 통해 최적화할 수 있다. 트리에서 연관된 접두사를 반복적으로 검색해야 하는 상황에서는, 트리의 현재 노드를 참조값으로 넘길 수도 있다. 이렇게 한다면 매번 검색할 때마다 루트에서 시작할 필요가 없고, 단순히 Y가 MAN의 자식인지만 확인해 보면 된다.