3-1. Binary Tree

Binary Tree

Binary Tree(이진 트리)는 각각의 노드가 최대 2개의 child 노드를 갖는 tree를 말한다.

이진 트리는 노드들이 어떻게 구성되어 있는지에 따라 다음과 같이 부르기도 한다.

 

 

Full Binary Tree (정 이진 트리)

모든 노드가 0 또는 2개의 child를 갖는 binary tree.

 

Perfect Binary Tree (포화 이진 트리)

모든 internal 노드가 2개의 child를 갖는 binary tree.

모든 leaf 노드가 같은 level에 있다.

(Proper Binary Tree라고도 함)

 

Degenerate Tree (변질 트리)

모든 parent 노드가 하나의 child만 갖고 있는 tree.

(Pathological Tree라고도 함)

 

Complete Binary Tree (완전 이진 트리)

마지막 level을 제외한 level의 모든 노드가 채워져 있으며, 마지막 level의 노드는 모두 왼쪽으로 채워진 binary tree.

 

Balanced Binary Tree (균형 이진 트리)

모든 노드의 왼쪽 child의 sub-tree와 오른쪽 child의 sub-tree의 높이 차가 최대 1인 binary tree.

 

 

Properties of Binary Trees

이진 트리는 최대 2개의 child 노드만을 갖기 때문에 다음과 같은 성질을 갖고 있다.

 

위와 같은 포화 이진 트리를 살펴보면 각 level의 노드의 수는 2^level이 되는 것을 볼 수 있다.

이를 통해 여러 가지 공식을 세울 수 있다.

 

먼저 전체 노드의 수를 n, internal 노드의 수를 m, leaf 노드의 수를 l, 트리의 높이를 h 로 정의해보자.

 

① 전체 노드의 수는 최소 h+1 이며, 최대 2^(h+1)-1이다.

최소인 경우는 변질 트리인 경우이며,

최대의 경우는 포화 이진 트리일 경우 1+2+4+···+2^h 가 되어 2^(h+1)-1개가 된다.

 

② internal 노드의 경우 ①에서 leaf 노드의 수만 빼주면 된다.

최소인 경우는 h+1개에서 leaf 노드 1개를 빼어 h개가 되며,

최대인 경우는 2^(h+1)-1에서 2^h를 빼주어 2^h-1개가 된다.

 

③ leaf 노드도 마찬가지로 ①의 경우를 생각하면 된다.

최소인 경우는 1개일 것이고, 최대인 경우 2^h개가 될 것이다.

 

④ 노드 갯수가 같다고 했을 때 포화 이진 트리일 때 가장 높이가 낮고, 변질 트리일 때 가장 높다.

따라서 변질 트리의 전체 노드 갯수는 h+1이므로 h의 최대 갯수는 n-1이 될 것이다.

그리고 포화 이진 트리에서 전체 노드 갯수는 2^(h+1)-1이므로 양변에 밑이 2인 log를 취해주면,

h의 최소 갯수는 log(n+1)-1가 되는 것을 알 수 있다.

 

 

Properties of Full Binary Trees

또한 Full Binary Tree(정 이진 트리)일 때만 나타나는 특징도 있다.

 

위와 같은 Fulll Binary Tree가 있다고 하자.

 

마찬가지로 위와 같이 문자로 정의했을 때,

 

⑤ root 노드에 2개의 child 노드만 있을 경우 m=1이고 l=2이다.

여기에 child 하나를 parent로 child로 2개 추가할 경우 m=2이고 l=3이 된다.

이와 같이 child 하나를 parent 로 바꿀 때마다 leaf 노드와 internal 노드의 수는 1씩 증가한다.

따라서 leaf 노드의 수는 항상 internal 노드의 수보다 1개 많게 된다.

 

⑥ 높이가 최소가 되는 경우는 마찬가지로 포화 이진 트리인 경우이다.

n=m+l / 전체 노드의 수 = internal 노드의 수 + leaf 노드의 수이고,

이 식에 ⑤ 식을 대입하면 n+1=m+l+1=2l 임을 알 수 있다.

이를 ④ 식의 좌변에 대입해서 풀어보면 h의 최솟값은 log(l)이 됨을 알 수 있다.

 

높이가 최대인 경우는 변질 트리에서 부족한 child를 채운 경우이다.

변질 트리의 경우 h=n-1인데 여기에 internal 노드의 수 만큼 child가 추가되게 된다.

따라서 h의 최댓값은 n-1-m이고 이 때 ⑤ 식에 의해 n=2m+1이고, 따라서 m이 되게 된다.

 

또한 위에서 증명한 식들을 통해 이와 같은 식도 나타낼 수 있다.