이진 트리(Binary Tree)

---

이진 트리 정의

• 트리 중, 모든 노드의 차수(degree)가 2가 넘지 않는 것을 이진트리라 한다.
• 유한 개의 노드들의 집합으로서
  • 노드 수가 0이거나 
  • 하나의 root 노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성되어 있으며, 각 서브트리는 다시 이진트리다.

 

이진트리 종류

편향 이진 트리 (Skewed Binary Tree)

: 트리의 노드가 왼쪽/오른쪽 중 한 쪽으로만 치우쳐진 트리이다.

포화 이진 트리 (Full Binary Tree)

: 트리의 깊이가 k일 때, 2^k-1 개의 노드를 가진 이진트리이다. (= 트리의 깊이까지 노드가 모두 꽉 차 있는 상태의 트리)

완전 이진 트리 (Complete Binary Tree)

: 마지막 레벨을 제외한 모든 레벨은 노드로 꽉 차 있으며, 마지막 레벨의 노드가 왼쪽에서 오른쪽으로 순차적으로 채워진 이진 트리. 

 

완전 이진 트리 X

완전 이진 트리 X

완전 이진 트리 O

이진 트리의 성질

최대 노드 수

• 이진 트리의 레벨 i(i>=1)에서의 최대 노드 수 : \( 2^{i-1} \) 
• 깊이가 k인 이진트리가 가질 수 있는 최대 노드 수 : \( 2^k-1 \)
  • \(  2^0+2^1+2^2+...+2^{k-1} \)
  • a=1, r=2인 등비수열의 합
  • \({{1(2^k-1)} \over 2-1}=2^k-1\)