5장 - 트리

목차

1. 개요

2. 이진트리

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

4. 이진트리의 추가 연산

5. 스레드 이진 트리

6. 히프

7. 이원 탐색 트리

8. 선택 트리

9. 포리스트

1. 개요

5강을 공부하기 위해선 트리에 대해 알아야 한다.

트리 구조란 정보의 항목들이 가지로 연결될 수 있게 데이터가 조직되는 구조이다.

예를 들면 족보 같은 경우 조상과 자손들, 부모와 자식들의 관계를 잘 보여준다.

 

정의 : 트리는 한 개 이상의 노드로 이루어진 유한 집합

(1) 노드 중에는 루트(root)라고 하는 노드가 있음

(2) 나머지 노드들은 n(>=0) 개의 분리 집합 T1,..., Tn으로 분할될 수 있다. 여기서 T1,..., Tn은 각각 하나의 트리이며 루트의 서브 트리(subtree)라고 한다.

 

트리의 차수 = max [노드의 차수] -> 쉽게 말해 자식이 가장 많은 노드의 자식 수

terminal 노드 (단말 노드) = 차수가 0인 노드

 

트리의 표현에는 여러 방법이 있지만, 자주 사용할 방법으로는 아래의 구조와 같다.

data
left Child	right Child

왼쪽 자식- 오른쪽 형제 표현법은 자식들이 있다면 그중 가장 가까운 자식을 가장 왼쪽 자식으로, 형제 노드들은 오른쪽 형제를 가리키게 표현하는 방법이다.

 

왼쪽 자식 - 오른쪽 형제 표현법으로 그려진 트리를 차수가 2인 트리로 만들기 위해서는 오른쪽 형제 필드를 45도 시계 방향으로 돌리면 된다.

 

2. 이진트리

이진트리 - 차수가 2인, 왼쪽 자식과 오른쪽 자식으로만 표현되는 트리 (공백을 가질 수 있다.)

 

보조 정리 1) T의 차수 = k, 노드의 수 = n 일 때, nk개의 자식 필드 중 n(k-1)+1개가 0의 값을 가진다.

     ex) 차수가 5, 노드가 10개인 트리라면 50개의 포인터 필드가 생성된다.

          이 중 Root는 포인터가 필요 없으므로 9개의 노드만 포인터를 사용한다. 즉 10(5-1) + 1 = 41 개 낭비

 

보조 정리 2) [최대 노드의 수]

     ex) 1. 레벨 i에서의 최대 노드의 수 : 2^(i -1) (i>=1일 때)

          2. 깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수 : 2^k - 1 (k>=1)

 

보조 정리 3) 증명, 단말 노드 수와 차수가 2인 노드 수와의 상관관계

     ex) n0 = n2+1    (교재 p.226)

          n = n0 + n1 + n2 (이때 n0, n1, n2는 각각 차수가 0, 1, 2 인 노드의 개수이다)

          n = B+1 (B = 가지 수, +1인 이유는 루트 노드 때문)

          B = n1 + 2n2 (차수가 1이면 가짓수는 1개, 차수가 2이면 가지수는 2개 이기 때문)

          n = B + 1 = n1 + 2n2 +1 이므로 정리하면

          n0 = n2 + 1이다.

 

포화 이진트리 - 깊이가 k이고 노드 수가 2^k - 1(k>=0)인 이진트리이다. 

완전 이진 트리 - 깊아가 k이고 노드 수가 n인 이진트리의 각 노드들이 깊이 k인 포화 이진트리에서 1부터 n까지의 번                        호를 붙인 노드들과 1대 1로 일치한다면, 이 트리는 완전 이진트리이다.

이때 완전 이진트리의 높이는 log2(n+1)보다 작지 않은 정수중 가장 큰 정수이다.

 

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

트리에서 수행하려는 연산중 트리 순회에 대해 알아보자.

트리 순회는 트리에 있는 모든 노드들을 한 번씩만 방문하는 것을 말한다.

전위 순회, 중위 순회, 후위 순회 세 가지 방법이 있다.

이 세가지 순회의 차이점은 언제 노드를 방문하냐 이다.

전위 순회부터 살펴보면 아래와 같다.

Visit(currentNode)

Inorder(current->leftChild)

Inorder(current->rightChild)

 

 

즉, 먼저 노드를 방문 한 뒤, 왼쪽 자식, 오른쪽 자식 순서대로 방문하는 것을 알 수 있다.

중위, 후위 순위도 마찬가지로 노드를 방문하는 시점이 왼쪽 자식과 오른쪽 자식을 기준으로 언제 있는지로 구분한다.

 

전위, 중위, 후위 순회 알고리즘은 아래 링크에 구현해 놓았다.

 

4. 이진트리의 추가 연산

다른 클래스들과 마찬가지로 이진 트리의 연산에도 copy, 동등 검사 등의 추가 연산이 가능하다.

이 코드들은 아래의 링크에 구현해 놓았다.

 

5. 스레드 이진 트리

이진 트리의 연결 표현을 살펴보면 실제 포인터보다 더 많은 0 링크가 있음을 알 수 있다.

이유는 보조 정리 3)을 통해 증명되어 있다.

이러한 0 링크를 이용하는 방법이 0 링크를 스레드로 대체하는 방법이다.

스레드의 규칙

(1) 노드 p의 rightChild가 0이라면 중위 순회할 때 p다음에 방문하는 노드에 대한 포인터로 p의 rightChild를 대치한다. 즉 이것은 0 링크를 p의 중위 후속자에 대한 포인터로 대치하는 것이다.

(2) 노드 p에서 leftChild가 0이라면 중위 순회할 때 p 앞에 방문하는 노드에 대한 포인터로 p의 leftChild를 대치한다. 즉 이것은 0링크를 p의 중위 선행자에 대한 포인터로 대치하는 것이다.

즉 쉽게 말해 스레드 링크를 그 노드에 대한 중위 선행자와 중위 후속자를 표현하는 필드로 만드는 것이다.

 

표현 방법은 leftThread와 rightThread란 bool형 메모리를 가지고 있으면서 만약 각각이 True라면 leftChild와 rightChild가 leftThread와 rightThread를 가리키고 있는다.

 

아래의 코드는 스레드 이진트리에서 s의 오른쪽 자식으로 r을 삽입하는 코드이다.

template <class T>
void ThreadedTree<T>::InsertRight(ThreadedNode<T>* s, ThreadedNode<T>* r) {
    r->rightChild = s->rightChild;
    r->rightThread = s->rightThread;
    r->leftThread = True;
    r->leftChild = s;
    s->rightThread = False;
    s->rightChild = r;
    if (!r->rightThread) { //진짜 자식이 있으면
        ThreadNodd<T>* temp = InorderSucc(r); //r의 중위 후속자를 반환하는 InorderSucc()함수를 통해 
        temp->leftChild = r;
    }
}

이때 rightThread가 False이면 자식 노드가 있어서 rightChild 가 오른쪽 자식을 가리키게 되고,

rightThread가 True라면 rightChild가 자식 노드가 아닌 중위 후속자를 가리키는 필드가 될 것이다.

 

6. 히프

히프는 우선순위 큐를 구현하는 데에 자주 사용된다. 

히프에는 최대 히프와 최소 히프가 있는데 먼저 최대, 최소 트리를 알아야 한다.

최대, 최소 트리는 각 노드의 키 값이 그 자식의 키 값보다 큰 트리이다.

최대, 최소 히프는 최대, 최소 트리이면서 완전 이진트리여야 한다.

 

히프의 삽입, 삭제 코드는 아래의 링크에 구현해 놓았다.

 

7. 이원 탐색 트리

이원 탐색 트리란 이진트리 이면서(공백일 수 있다.)  공백이 아니라면 

1. 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다.
2. 왼쪽 서브 트리에 있는 키들은 그 루트의 키보다 작다.
3. 오른쪽 서브트리에 있는 키들은 그 루트의 키보다 크다.
4. 왼쪽과 오른쪽 서브 트리도 모두 이원 탐색 트리이다.

이원 탐색 트리의 탐색 - 정의가 순환적이기 때문에 탐색 역시 순환적으로 하면 된다.

즉 왼쪽 자식에는 root보다 작은 값, 오른쪽에는 큰 값이 있으므로 원하는 값을 찾을 때까지 반복해주면 된다.

 

이원 탐색 트리에서의 삽입 - 삽입 코드 자체는 어렵지 않다. 노드와 자신의 key값을 비교해 가며 자신의 위치를 찾아가면 된다. (노드의 key값보다 작으면 왼쪽, 크면 오른쪽 자식으로 이동한 뒤 반복)

 

이원 탐색 트리에서의 삭제 - 리프 노드(자식이 없는 노드) 라면 바로 삭제가 가능하고, 비 리프 노드여도 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 값을 자신과 바꾸고 삭제하면 된다.

 

이원 탐색 트리 관련 코드들은 아래의 링크에 구현해 놓았다.

 

8. 선택 트리

선택 트리란 완전 이진트리이면서 노드가 자식들 중 큰 값, 또는 작은 값을 가지는 구조이다.

선택 트리에는 승자 트리, 패자 트리가 있는데 승자 트리는 노드가 자식 노드 중 큰 값을, 패자 트리는 자식 노드 중 작은 값을 부모 노드가 가지게 된다.

예로 들면 토너먼트를 선택 트리 구조로 표현 가능하다.

여기서 비슷한 구조가 생각나는데 바로 히프 구조이다. 히프 구조 역시 최소 히프, 최대 히프로 나뉘어 있는데 히프와 선택 트리에는 아주 큰 차이가 있다.

바로 선택 트리는 자식의 값 중 작은 값을 가지게 되어 있고, 히프는 자식의 값보다 작거나 같은 값을 가진다.

(최소 히프, 패자 트리일 때)

 

9. 포리스트

정의 : 포리스트(forest)는 n>=0 개의 분리 트리들의 집합이다.

 

즉, 쉽게 말해 여러 개의 트리들로 이루어진 집합을 이야기한다.

포리스트를 왼쪽 자식 - 오른쪽 형제 표현법을 통해 이진트리로 표현 가능하다.

 

이렇게 포리스트를 이진 트리로 표현하고 그 이진트리를 T라 한다면,

T를 전위, 중위 순회한 결과가 포리스트를 순회한 결과와 같다는 것을 알 수 있다.

후위 순회는 T를 후위 순회한 결과와 포리스트를 후위 순회한 결과는 다르다.

교재 p.267에 나온 포리스트를 후위 순회한 결과는 BCDFHIGEA인데, T를 후위 순회하면 DCBFIHGEA이다.

포리스트 후위 순회의 정의는 아래와 같다.

1. F가 공백이면 복귀
2. F의 첫 번째 트리의 서브 트리를 포리스트 후위로 순회한다.
3. 나머지 트리를 포리스트 후위로 순회한다.
4. F의 첫 번째 트리의 루트를 방문한다.

가장 중요한 것은 포리스트를 이진트리로 바꾸는 방법인 것 같다.

 

https://github.com/kimtaehyun98/-

kimtaehyun98/-