[자료구조] 7-2. 이진 트리

이진 트리는 degree가 2인 트리를 말한다. 디그리는 각 노드의 최댓값이다. 따라서 자식 노드를 '최대' 2개 가진다는 것이지, 하나도 없거나 1개만 있어도 다 이진 트리가 될 수 있다.

코드로 구현하면 왼쪽 child인 lchild와 오른쪽 child인 rchild에 대한 포인터를 함께 정의한다.

오른쪽의 그림의 트리는 A B C라는 노드를 가지고 있으므로 각각 메모리 공간에 저장된다. 그리고 자식이 있는 A는 lchild와 rchild에 대한 공간을 가지고 있다. 기존 트리와 달리 차일드의 개수를 저장하지 않고 있다.

이진 트리에는 3가지의 성질이 있다. 첫째, i번째 레벨은 최대 2의 (i-1)승 개의 노드를 가질 수 있다.

예를 들어, 맨 위부터 레빌 1 2 3 4인 그림을 보자. 2번째 레벨은 2의 (2-1)승, 즉 최대 2개의 노드를 가진다. 레벨 4는 최대 8개의 노드를 가질 수 있다. 이것을 증명하려면 수학적 귀납법을 이용해야 한다.

수학적 귀납법은 세 가지 단계로 증명된다.

1. n=1일 때 성립함을 증명

n=1은 루트 노드의 레벨을 의미한다. 모든 트리에서 로트 노드는 1개이다. n=1일때 2의 (n-1)승, 즉 2의 (1-1)승은 1개이므로 성립한다.

2. n=i일 때 성립함을 가정

n=i일때 최대 2의 (i-1)승 개의 노드를 갖는 다는 것을 가정한다.

3. n=i+1일때 성립함을 증명

i+1번째 레벨에서 최대 노드를 갖기 위한 조건은, i번째 레벨에서 최대 노드를 갖고, 그 노드들이 각각 2개씩의 차일드 노드를 가져야 하는 것이다.

2번 단계에서 i 레벨에서 최대 노드의 개수는 2(i-1)승 개라고 가정했다. 각각 2개의 차일드 노드를 가져야 하므로 2를 곱한다.

2의 (i-1)승 곱하기 2는 2의 i승이다.

따라서 2의 i승개가 i+1번째 레벨에서 가질 수 있는 최대 노드이다.

그런데 i승 개는 (i+1) - 1승 개이므로 이 성질이 성립한다고 본다.

두 번째 성질은 뎁스가 k인 이진 트리는 최대 (2의 k승 - 1)개의 노드를 갖는다는 것이다.

예를 들어, 노란색 영역을 보면 k가 3인 트리다. 이때 가질 수 있는 최대 노드의 개수는 7개다. 그런데 이게 2³－1 개와 같다. k가 4인 경우도 마찬가지다.

아래는 강의 내용 복붙. 증명 부분은 나중에 정리하면서 이해할 예정.

이런 성질이 성립한다는 걸 이렇게 예를 보였는데 이것도 마찬가지로 이 성질이 성립함을 증명하려면 수학적 귀납법을 쓰는 것을 권합니다.

그러면 이 성질을 증명해 보겠습니다.

이것도 마찬가지로 수학적 귀납법을 쓰기 때문에 n=1일 때, n=k일 때, n=k+1일 때를 각각 증명하고 가정하고 증명해야 되는 거죠.

n=1인 경우는 뎁스가 1인 트리라는 뜻이니까 루트 노드만 있는 트리니까 노드의 개수가 1개일 겁니다.

따라서 이 녀석은 2¹－1개니까 1이 되겠죠.

그다음에 n=k인 경우에는 뎁스가 k인 트리가 최대 (2의 k승)－1개의 노드를 가지고 있다고 가정합니다.

그다음에 n=k+1인 경우에는 k+1개의 뎁스를 가진 이진 트리가 최대 노드를 가지려면 k까지의 노드들이 최대 노드를 갖고 k+1번째 레벨에서 최대 노드를 가져야 됩니다.

그런데 k까지의 최대 노드는 아까 가설에서 (2의 k승)－1개라고 했죠.

그리고 k+1번째 레벨에서 갖는 최대 노드는 이 앞에 성질에서 2의 (k+1－1)승 개입니다.

그래서 결국 이 숫자도 2의 k승이 되는 거죠.

따라서 (2의 k승)－1+(2의 k승)이니까 얘는 2×(2의 k승)－1이니까 2의 (k+1)승－1이 되는 겁니다.

따라서 성질이 성립한다는 것을 우리가 증명할 수 있죠.

세 번째 성질은 어떤 원소가 있는 트리에서 리프 노드의 개수를 n0, 디그리가 2인 노드의 수를 n2라고 하면, n0 = n2 + 1을 성립한다는 것이다.

아래의 트리를 보자. 현재 리프 노드의 개수는 4개이다. 따라서 n0=4이다. n2=3이다. 4=3+1이므로 위의 성질을 만족한다.

역시 설명 복붙

이때의 증명은 직접 증명법 즉, 우리가 어떤 성질을 유도한 다음에 그 성질로부터 직접 증명을 시도해야 됩니다.

어떤 성질을 우리가 먼저 찾을 수 있냐면 첫 번째 이런 성질을 찾을 수 있습니다.

어떤 트리에 속하는 모든 노드의 개수를 n개라고 하면 그때는 디그리가 0인 즉, 리프 노드인 개수와 디그리가 1개인 노드와 디그리가 2개인 노드의 개수를 다 더하면 된다고 하는 거죠.

이진 트리라고 하는 게 최대 디그리가 2이기 때문에 결국 디그리는 0, 1, 2 중의 하나를 가지기 때문에 이런 성질이 성립한다고 볼 수 있습니다.

정말 그럴까요? 예를 들어서 설명해 볼까요.

이 트리에서 디그리가 0인 노드는 4개가 되겠죠.

그다음에 디그리가 1인 노드는 이 노드입니다. 그래서 1이 되겠죠.

디그리가 2인 노드는 이 3개의 노드입니다. 자식이 2개죠.

그래서 합치면 3이 될 겁니다.

결국 그래서 4+1+3이니까 8개라는 노드의 개수를 가질 텐데 하나, 둘, 셋, 넷, 다섯, 여섯, 일곱, 여덟 얘는 8이죠.

그래서 같다는 걸 여러분들이 볼 수 있습니다.

두 번째 성질은 차일드 노드의 관점에서 보면 전체 노드의 개수는 디그리가 2개인 노드는 2개의 차일드를 가질 것이고, 디그리가 1개인 노드는 하나의 차일드만을 가질 겁니다.

그런데 어떤 노드의 차일드 노드가 아닌 노드가 하나 있죠.

그게 루트 노드죠. 그래서 이 녀석은 루트 노드의 몫입니다.

즉, 이런 관계가 성립한다는 거죠.

그럼 여기서 한번 볼까요.

디그리가 2인 노드는 이렇게 3개입니다.

그래서 3개 곱하기 2를 하죠.

디그리가 1인 노드는 이 녀석입니다.

그래서 1개 곱하기 1을 하죠.

루트 노드는 1개죠.

6, 1, 1이니까 다 더하면 8, 전체 노드의 개수가 됩니다.

이 1번과 2번 성질을 이용합니다.

즉, 1번과 2번 성질에서 전부 다 n=이라고 썼기 때문에 좌변과 우변은 n으로써 같다는 거죠.

그러면 여기서 우리가 n1을 삭제하고 n2를 이렇게 삭제하고 나면 n0=n2+1을 만족시킨다고 하는 것을 증명할 수 있는 겁니다.

이렇게 증명하는 걸 우리가 직접증명법이라고 합니다.

이제는 특별한 이진 트리를 알아보자. 첫번째는  포화 이진 트리이다. 뎁스가 k일 때 (2의 k승 -1) 개의 노드를 갖는 이진 트리이다. 즉, 최대 노드를 갖는다.

이와 같은 이진 트리는 노드를 증가하려면 반드시 뎁스를 증가해야 한다는 것이다. 현재의 트리에서 뎁스를 증가시키지 않고 노드를 증가시키는 방법은 없다.

또 다른 특별한 이진 트리는 완전 이진 트리이다. 같은 뎁스를 갖는 포화 이진 트리와 완전 이진 트리는 일대일 대응 관계가 성립한다.

예시를 보자. 가운데에 있는 트리는 depth=3인 포화 이진트리이다. 노드에 숫자를 붙여보면 왼쪽 트리는 7번이 없다. 하지만 왼쪽과 가운데 트리의 관계를 보면 일대일이 성립한다. 1은 2, 3을, 2는 4, 5라는 자식을 갖는다. 서로 대응한다.

반면에 오른쪽은, 6이 저 멀리 다른쪽에 있다. 그래서 일대일 대응이 성립하지 않는다고 얘기한다.

왼쪽의 경우를 완전 이진 트리라고 부른다.

트리의 탐색은 search 또는 traversal이라고 부른다. 서치는 어떤 집합을 주고, 특정 원소가 속해있다면 인덱스를 리턴하고, 아니면 null을 리턴하는 연산이었다.

하지만 트리의 서치는 이런 의미가 아니다. 루트부터 시작해 모든 노드를 다 방문하는 연산이다. 그래서 트리의 서치는 반드시 루트 노드를 주게 되어있다. 

트리의 탐색엔 깊이 우선 탐색과 넒이 우선 탐색이 있다. 자세한 내용은 그래프 부분에서 배운다. 이 글에서는 우선 이진 트리에만 적용되는 특별한 탐색에 대해 배울 것이다.

부모에서 자식노드로 갈때 왼쪽 부터 가야할까, 오른쪽 부터 가야할까? 마치 형이 동생보다 먼저이듯, 순서는 반드시 왼쪽에서 오른쪽으로 가야 한다. 다만 차이가 있다면 부모를 먼저 할건지 중간이나 끝에 할건지 생각하는 것이다.

1. 중위 우선 탐색

부모를 중간에 두는 탐색이다. 즉, 왼쪽을 먼저 하고 - 부모 - 오른쪽 순으로 진행한다.

2. 전위 우선 탐색

부모를 먼저 하고 왼쪽 - 오른쪽 으로 진행한다.

3. 후위 우선 탐색

왼쪽 - 오른쪽 - 부모 순으로 진행한다.

코드를 보면 먼저 왼쪽 차일드에 대해 inorder를 수행한 후, 부모를 출력하고, 오른쪽 차일드를 inorder 한다.

그림 같은 트리를 보면 B-A-C 순이다.

전위 우선 탐색은 부모를 먼저 출력하고 왼쪽 - 오른쪽 순으로 preorder를 수행한다.

후위 우선 탐색은 왼쪽 - 오른쪽 - 부모 순이다.

예제를 보자.

모든 탐색은 루트 노드인 A부터 시작한다. Inorder 는 중위 우선 탐색이므로 왼쪽 - 부모 - 오른쪽의 순서를 가진다. 따라서 Inorder B - A - Inorder C 순으로 한다.

그리고 B의 left child로 인오더해서 D- B - E를 한다.

또 D에 대한 H - D - I를 진행한다.

H는 Inorder 할 차일드가 없으므로 그냥 H와 D로 출력한다.

인오더 I 또한 마찬가지로 자기 자신을 출력하고 끝낸다.

E도 자기 자신을 출력하고 끝낸다.

그리고 A를 출력하고, C에 대한 자식도 Inorder 시킨다.

그럼 최종적으로 이런 순서로 출력이 된다.

전위 우선 탐색은 자기 자신을 먼저 출력하고 왼쪽 - 오른쪽으로 간다.

부모인 자기 자신 A를 먼저 찍고 B와 C로 간다.

다시 부모인 B를 찍고 D와 E로 간다.

부모인 D를 찍고 pre H - pre I를 한다.

더 이상 child가 없으므로 H를 찍고

I도 차일드가 없으므로 자기 자신을 찍는다.

E도 마찬가지.

그 다음 C를 찍고 F와 G의 프리오더를 진행한다.

최종적으로 이렇게 된다.

후위 탐색은 왼 - 오 - 부모 순으로 진행된다.

A에 대해 포스트 오더를 시행하면 왼쪽은 B를 먼저 하고 그다음 오른쪽은 C를 수행하고 마지막으로 자기 자신을 출력한다.

마찬가지로 B도 post D, post E, 그다음 자기 자신인 B를 출력한다.

계속 반복하면 이렇게 출력된다.