데이터 구조와 알고리즘 6장 1

트리란 무엇인가?
트리는 연결 리스트와 유사한 데이터 구조이다. 하지만 각 노드가 선형적으로 다른 노드를 가리키는 게 아니라 각 노드가 여러 개의 노드를 가리킨다. 트리는 비선형적 데이터 구조의 한 예이다. 트리 구조는 구조의 계층적 속성을 그래프의 형태로 나타내는 방법이다.
// 항목의 순서는 중요하지 않다.

 - 용어 설명
1. 트리의 뿌리는 부모가 없는 노드이다. 트리에는 최대 한 개의 뿌리 노드가 있을 수 있다.(A)
2. 간선(edge)은 부모로부터 자식에게 이어지는 연결 선을 뜻한다.(모든 선)
3. 자식이 없는 노드를 잎(leaf) 노드라고 한다(E, I, J, K, I)
4. 같은 부모를 가진 자식들을 형제(sibling)라고 한다.(B, C, D는 A를 부모로 하는 형제 노드들이고 E, F는 B를 부모로 하는 형제 노드들이다.)
5. 뿌리 노드로부터 노드 q에 이르는 경로에 노드 p가 있으면 노드 p를 노드 조상 노드(ancestor)노드라고 한다. 노드 q는 노드 p의 자손(descendant)노드이다.
// A, B, F는 J의 조상 노드들이다.
6. 주어진 깊이의 모든 노드의 집합을 그 트리의 레벨이라고 한다.

7. 노드의 깊이는 뿌리로부터 그 노드까지의 경로의 길이이다.
  // F의 깊이는 2, A-C-G
8. 노드의 높이는 그 노드로부터 가장 깊은 노드까지의 경로의 길이이다. 트리의 높이는 뿌리로부터 가장 깊은 까지의 경로의 길이이다.
  // B의 높이는 2이다.(B-F-G)
9. 트리의 높이는 트리의 모든 노드의 높이 중 최대 값이고 트리의 깊이는 트리의 모든 노드의 깊이의 최대 값이다. 주어진 트리에 대해 높이와 깊이는 같은 값을 가진다. 하지만 각각의 노드에서의 값은 다를 수 있다.
10. 노드의 크기는 자기 자신을 포함하여 그 노드가 가진 자손의 수이다.
 // B의 크기는 4이다.
11. 트리의 모든 노드가 오직 한 개의 자식만을 가질 때(잎 노드를 제외하고) 이 트리를 경사(skew) 트리라고 한다. 모든 노드가 왼쪽 자식만을 가지면 왼쪽 경사 트리라고 한다.
반대의 경우에는 오른쪽 경사 트리라고 한다.

 - 이진 트리

각 노드가 자식이 없거나, 한 개 혹은 두 개의 자식을 가질 때 이진 트리라고 한다. 빈 트리 역시 유효한 이진 트리이다. 이진 트리는 뿌리와 왼쪽 부속 트리, 오른쪽 부속 트리라고 불리는 두 개의 분리된 이진 트리로 구성되어 있다고 볼 수 있다.

 - 이진 트리의 종류

엄격한 이진 트리: 모든 노드가 두 개의 자식을 가지거나 자식이 없을 때 엄격한 이진 트리

포화 이진 트리: 모든 노드가 두 개의 자식을 가지고 잎 노드가 같은 레벨에 있을 때 포화                     이진 트리
완전 이진 트리: 완전 이진 트리를 정의하기 전에, 이진 트리의 높이가 h라고 할 때, 완전
                  이진 트리에서는 뿌리부터 시작해서 각 노드에 번호를 매기면, 1부터 시작                   해서 트리 안의 노드 수까지의 완전한 순열을 얻는다. 탐색할 때 NULL                       포인터에게도 숫자를 매겨야 한다. 모든 잎 노드가 높이 h나 h - 1에 있고                   순열에서 빠진 숫자가 없을 때 완전 이진 트리라고 부른다.

 - 이진 트리 속성
1. 포화 이진 트리의 노드 개수 n은 2^(h+1) - 1이다. 모두 h 레벨이 있기 때문에 각 레벨의 노드를 다 더해야 한다.(2^0 + 2^1 + 2^2 + 2^3 + 2^4 +... + 2^h = 2^(h+1) - 1
2. 완전 이진 트리의 노드 개수 n은 2^h(최소 값)과 2^(h+1) - 1(최대 값) 사이에 있다.
3. 포화 이진 트리의 잎의 개수는 2h이다.
4. n개의 노드를 가진 완전 이진 트리의 NULL 연결(낭비된 포인터)의 개수는 n + 1이다.


 - 이진 트리의 구조
이제 이진 트리의 구조를 정의해보자. 예를 들어 노드의 데이터가 정수라고 하자. 다음 그림은 왼쪽과 오른쪽 자식을 가리키는 두 연결을 가진 데이터 필드로, (데이터를 포함한) 노드를 표현한 것이다.

class BinaryTreeNode {

    int data;

    class BinaryTreeNode *left;

    class BinaryTreeNode *right;

};

 - 이진 트리의 연산

   기본 연산

 트리에 항목 삽입하기

 트리로부터 항목 삭제하기

 항목 검색하기

 트리 탐색하기

   부가적 연산 

 트리의 크기 구하기
 트리의 높이 구하기
 최대의 합을 가진 레벨 찾기
 주어진 노드 쌍에 대해 최소 공통 조상 찾기
 ...  ...


 - 이진 트리 탐색
트리를 처리하기 위해서는 트리를 탐색하는 방법이 필요하다. 트리의 모든 노드를 방문하는 과정을 트리 탐색이라 한다. 각 노드는 오직 한 번씩 처리되지만 한 번 이상 방문될 수도 있다. 선형 데이터 구조(연결 리스트, 스택 , 큐)에서는 항목들이 순차적으로 방문된다.
그러나 트리 구조에서는 여러 가지 방법이 있다.
트리 탐색은 트리를 검색과 기본적인 동작이 같지만, 탐색의 목적은 특정한 순서로 트리 안을 움직이는 것이다. 또한 탐색에서는 모든 노드가 처리되지만 검색에서는 찾는 노드가 발견되면 멈L춘다.


 - 탐색 가능성
이진 트리의 뿌리부터 시작해서 모든 노드를 탐색하는 데는 세 가지 단계가 있는데, 이 단계들의 수행 순서에 따라 탐색 유형이 달라진다. 이 단계들은 현재 노드에 대해 어떤 작업 수행하기(노드를 '방문'한다고 하고 'D'라고 표기한다), 왼쪽 자식 노드 탐색하기('L'이라고 표기한다), 그리고 오른쪽 자식 노드 탐색하기('R'이라고 표기한다)이다. 이 과정은 재귀적 방법으로 쉽게 표현할 수 있는데, 다음과 같은 여섯 가지 가능성이 있다.
1. LDR: 왼쪽 부속 트리를 처리하고, 현재 노드의 데이터를 처리하고, 오른쪽 부속 트리를             처리한다.
2. LRD: 왼쪽 부속 트리를 처리하고, 오른쪽 부속 트리를 처리하고, 현재 노드의 데이터를            처리한다.
3. DLR
4. DRL
5. RDL
6. RDL


 - 탐색 분류하기
이 요소들이 처리되는 순서가 특정한 탐색 기법을 정의하게 된다. 현재 노드가 처리되는 순서에 따라 분류가 된다. 즉 현재 노드(D)에 의해 분류하는데, D가 가운데에 온다면 D의 왼쪽에 L이 오거나 상관없다. 비슷하게, D의 오른쪽에 L이 오거나 R이 오거나 상관없다. 이런 특성 때문에 모두 여섯 가지 가능성이 다음의 세 가지로 줄어든다.
1. 전위 탐색(DLR)
2. 중위 탐색(LDR)
3. 후위 탐색(LRD)

앞의 순서와 상관없는 또 다른 탐색 기법이 하나 더 있다.

레벨 순서 탐색: 이 기법은 너비 우선 탐색의 영향을 받은 것이다.

다음 그림을 기반으로 설명한다.

전위 탐색
전위 탐색에서 각 노드의 탐색은 부속 트리를 탐색하기 전에 처리된다. 각 노드가 부속 트리 전에 처리되더하도 몇몇 정보는 탐색이 트리의 다음 순서로 이동하는 동한 유지되어야 한다. 1이 먼저 처리되고 나서 왼쪽 부속 트리, 오른쪽 부속 트리 순서로 처리된다. 왼쪽 부속 트리 처리 후 오른쪽 부속 트리로 이동하려면 뿌리의 정보가 유지되어야 한다. 이런 정보를 위한 ADT는 당연히 스택인데, 스택의 LIFO 구조 때문에 오른쪽 부속 트리에 대한 정보를 역순으로 얻는 것이 가능하다.
  전위 탐색은 다음과 같이 정의된다.
1. 뿌리를 방문한다.
2. 전위 탐색으로 왼쪽 부속 트리를 탐색한다.
3. 전위 탐색으로 오른쪽 부속 트리를 탐색한다.

앞의 트리의 노드는 1 2 4 5 3 6 7의 순서로 방문된다.

void PreOrder(BinaryTreeNode root) {
  if(root != null) {
     System.out.println(root.getDate());
     PreOrder(root.getLeft());
     PreOrder(root.getRight());
    }
}

시간 복잡도: O(n)
공간 복잡도: O(n)

중위 탐색
중위 탐색에서는 뿌리 노드가 탐색에서는 뿌리 노드가 부속 트리 사이에 방문된다. 중위 탐색은 다음과 같이 정의된다.

1. 왼쪽 부속 트리를 중위 탐색으로 탐색한다.
2. 뿌리 노드를 방문한다.
3. 오른쪽 부속 트리를 중위 탐색으로 탐색한다.

앞의 트리 노드는 4 2 5 1 6 3 7의 순서로 방문된다.

void InOrder(BinaryTreeNode root) {
     if(root != null) {
        InOrder(root.getLeft());
       System.out.println(root.getData());
       InOrder(root.getRight);
    }
}

시간 복잡도: O(n)
공간 복잡도: O(n)

후위 탐색
후위 탐색에서 뿌리 노드는 양쪽 부속 트리 뒤에 방문된다. 후위 탐색은 다음과 같이 정의된다.

1. 왼쪽 부속 트리를 후위 탐색으로 탐색한다.
2. 오른쪽 부속 트리를 후위 탐색으로 탐색한다.
3. 뿌리 노드를 방문한다.

앞의 트리 노드들은 4 5 2 6 7 3 1의 순서로 방문된다.

void PostOrder(BinaryTreeNode root) {
    if(root) {
       PostOrder(root.getLeft());
       PostOrder(root.getRight());
       System.out.println(root.getData());
    }
}

시간 복잡도: O(n)
공간 복잡도: O(n)

레벨 순서 탐색
레벨 순서 탐색은 다음과 같이 정의된다.

1. 뿌리 노드를 방문한다.
2. 레벨 l을 방문하는 동안 레벨 ㅣ + 1의 모든 항목을 큐에 저장한다.
3. 다음 레벨로 가서 그 레벨의 모든 노드를 방문한다.
4. 이 과정을 모든 레벨이 끝날 때까지 방문된다.

앞의 트리의 노드들은 1 2 3 4 5 6 7의 순서로 방문된다.

void LevelOrder(BinaryTreeNode root) {
   BinaryTreeNode temp;
   LLQueue Q = new LLQueue();
   if(!root)
       return;
   Q.enQueue(root);
   while(!Q.isEmpty()) {
       temp = Q.deQueue();
       // 현재 노드를 처리한다.
       System.out.println(temp.getData());
       if(temp.getLeft())
            Q.enQueue(temp.getLeft());
       if(temp.getRight())
            Q.enQueue(temp.getRight());
       }
   Q.deleteQueue();
}

시간 복잡도: O(n)
공간 복잡도: O(n)