이진트리의 성질

1. level i 에서 최대 노드수 2^i-1

2. depth d 에서 이진 트리의 최대 노드수 2^d - 1

level 1 의 최대 노드수 + level 2 의 최대 노드수 + level 3 의 최대 노드수 + ...+ level d 에서 최대 노드수

=1+2¹+2²+....+2^d-1 = 2^d-1

초항이 1 이고 , 등비가 2 인 등비 수열이다.

3. 차수가 0 인 노드(터미널 노드)수는 차수가 2 인 노드 수 보다 하나 많다 (n₀=n₂+1)

n0,n1,n2 란?

• n0 는 degree 가 0 인 터미널 노드의 수
• n1 은 degree 가 1(아들 노드를 한개) 인노드의 수
• n2 은 degree 가 2(아들 노드를 두개) 인 노드의 수

(증명)

브랜치 수는 총 노드수보다 하나 작다. 즉 브랜치 수 = n - 1 개 --- (1)
브랜치 수 = (degree 가 2 인 노드의 수) * 2 + (degree 가 1 인 노드수) * 1 ---(2)

(1),(2) 식 에서

n - 1 = n2 * 2 + n1

n = n0 + n1 + n2 식을 위식에 대입하면

n0 + n1 + n2 - 1 = 2 * n2 + n1

그러므로 n0 = n2 + 1

4. n 개의 노드를 가진 전(complete) 이진트리 의 depth : [log₂n + 1]

증명