[Algorithm/Tree] Binary Tree (이진트리)

Binary Tree / 이진 트리

최대 차수가 2인 트리 구조

증명

정리 1 : N레벨에서의 최대 노드의 수

• 직관적으로 노드의 레벨 N의 최대 노드의 갯수는 2N-1 이다.
  
  
• P(N) = 2N-1 이라고 했을 때
• P(1) = 21-1 = 20 = 1
• P(N) = 2N-1
• P(N+1) = 2N
• 노드의 차수는 최대 2 이므로
• 2*P(N) = 2*2N-1 = 2N = P(N+1) 이므로 깊이가 N일 때의 최대 노드 수는 2N-1 이다.

정리 2 : 트리의 최대 노드의 수

• 일단 결과적으로 계산해 본다면 N레벨의 트리의 최대 노드의 수는 2N-1이 된다.
  n = 1 : 2-1 = 1
  n = 2 : 22-1 = 4-1 = 3
  n = 3 : 24-1 = 8-1 = 7
• 왜 이렇게 되는가? 먼저 위와 같은 결과의 수식을 귀납법으로 증명해보겠다.
• F(n) = 2n-1이 되는데
• F(1) = 21-1
• F(n) = 2n-1
• F(n+1) = 2n+1-1
• 정리1에 의해 n+1의 최대 노드의 갯수는 2n이 되는데
  F(n+1) = P(n) + F(n)으로 계산할 수 있으니까
  F(n+1) = 2n+2n-1이 되고 이는
  F(n+1) = 2n+1-1이 됩니다.
• 이는 기존에 가설로 세운 F(n) = 2n-1이 증명된다.

하노이 탑의 최소 이동 횟수

• 하노이탑은 완전이진트리의 노드 갯수와 동일한 수식(2n-1)이 쓰이는데
  이는 N -> 목적지전을 가기 위해서는 N-1 -> 2 이동하였다 N 이 이동한 후 N-1 -> 3으로 이동하는 기존의 로직과 동일하다.
• 2n-1이 되는 이유는 최초 N번째 그릇이 단 한번만 이동하며, 그 외 차수 노드(N-1)들이 표현하는 것이 임시 이동 후 목적지로 이동하기 떄문에 2개의 차수노드가 생겨 풀 바이너리 트리와 동일한 그림이 그려진다.
• 따라서 하노이탑의 최소 이동 횟수 또한 완전 이진 트리와 같은 2n-1이 성립한다.