[Data Structure] #4-2 Binary Tree 이진 트리 개념

 저번 포스트에 이어서 트리 개념 정리를 이어간다. 이번에는 Binary Tree (이진 트리)를 다룰 예정이다. 사실 Binary Tree는 앞서 이야기 했던 Tree의 축소판이다. 가장 큰 특징은 이름에서 드러난다. 바로 자식이 최대 2개이다. 기억나는가? 일반 Tree의 경우에는 Degree라고 해서 자식 Node의 갯수를 의미했다. 즉, Binary Tree의 Degree는 최대 2이다.

 Binary Tree는 다음의 조건을 만족한다.

1. 공집합이거나
2. root , 좌측 Subtree , 우측 Subtree로 이루어진다.
3. Binary Tree의 Subtree는 모두 Binary Tree이다.

 1번 조건에 의해 Binary Tree는 노드를 하나도 가지지 않을 수 있다. 즉, 공집합도 Binary Tree인 것이다. (이 부분은 일반 트리와 다르다. 그래서 엄밀히 말하면 Binary Tree는 일반 Tree의 축소판이라 부르기 어렵긴 하다)


 Binary Tree는 몇 가지 특징을 가진다.

1. Binary Tree가 n개의 Node 갯수를 가지면 Edge의 갯수는 n-1개이다.

 위 그림에서 Node의 개수는 3개. Edge의 개수는 2개. 왜냐하면 root node는 부모를 가리키는 edge를 가지고 있지 않기 때문이다. 달리 말하 면 root를 제외한 모든 node는 부모를 가리키는 edge를 가지고 있다.



2. Height 가 h이면 Binary Tree가 가질 수 있는 '최대' Node 개수n은 2 ʰ-1개이다.

 왜 그럴까? 잠깐 고등학교 때 배웠던 등비급수를 떠올려보자.. :D 위의 그림에서 보면 Node의 계수가 Level에 따라서 2가 지속적으로 곱해지는 것을 알 수 있다. 그럼 우리는 높이h에 따라서 총 Node의 개수 n이 어떻게 변하는지 알고 싶기 때문에 위의 그림에서 오른쪽의 노드의 개수를 모두 더해야 한다. 그럼 총 노드의 개수 n은..

  n = 2⁰+2¹+2²+2³+ .... + 2ʰ⁻¹

        2n =      2¹+2²+2³+ .... + 2ʰ⁻¹ + 2ʰ

 두 등식을 서로 빼주면 (1-2)n = 2⁰-2ʰ 이고 총 노드의 개수 n = 2ʰ-1이 된다. 이 때 주의해야할 점은 n은 노드의 최대 개수라는 점이다. 그러니까 높이가 h이면 노드의 개수가 아무리 많아도 2ʰ-1까지라는 점이다. 즉 n ≦ 2ʰ-1 이다. 이 식을 살짝 바꿔보자.

 n ≦ 2ʰ-1 이ㅁ로
 n+1 ≦ 2ʰ 이고
 ㏒₂(n+1) ≦ h 이다. 

 이 때, h는 높이인 정수를 의미하므로
⎡㏒₂(n+1)⎤≦ h 이다. 여기서 ⎡⎤는 무조건 올림을 의미한다. 예를 들어 Node개수가 5이면 ⎡㏒₂(6)⎤이고 2<㏒₂(6)<3 이므로  ㏒₂(6) = 2.xxxx이다. 무조건 올림을 적용시키면 최소 높이가 3이 된다. Binary Tree에서 Node가 5개인 것을 그려보라 아무리 잘 그려도 높이는 3 이상이다. 

 나머지 용어 정리를 해보자.

Full Binary Tree (포화 이진 트리) : 각 레벨에 맞게 모든 Node가 최대 개수를 가지는 트리
Complete Binary Tree (완전 이진 트리) : 왼쪽 자식부터 차례대로 채워진 트리