[56회 변리사 2차-4번] 이진트리 (Binary Tree)

2019년 제 56회 변리사 2차 데이터 구조론 2교시 4번 문제 해설

 

 

 

 

 

 

 

 

 

이진 트리 (Binary Tree)

하나의 노드가 최대 두개의 자식 노드를 가지는 트리를 말한다.

이진 트리 개념 속 여러 용어가 있지만 중요한 몇가지 용어를 소개한다.

 

노드의 차수 (Degree): 노드의 서브트리 수

단말(Terminal) 노드: 리프(leaf) 노드라고하며 차수는 0

비단말 노드: 차수가 0이 아닌 노드

노드 레벨: 루트 (레벨 1)

트리의 차수: Max(노드의 차수)

트리의 높이 (Height , Depth) : Max(노드 레벨)

자식 (Child) ,형제 (Sibling)

선조 (Ancestor): 루트까지의 경로상에 있는 모든 노드

자손 (Descendants): 한 노드의 서브트리에 존재하는 모든 노드

 

 

 

1. 이진트리에 관하여 다음 물음에 답하시오.

 

​

(1) N개의 노드를 가지고 있는 이진트리에서 차수(degree)가 0인 단말노드의 개수를 T라고 하고, 차수가 2인 노드의 개수를 M이라고 하자. 이 경우, T = M+1이 성립함을 설명하시오. (10점)

 

답안)

 

먼저 차수가 i인 노드 수를 다음과 같이 정의한다.

전체 노드 수를 n이라고 했을 때, 다음과 같은 증명이 가능하다.

 

 

 

따라서 노드(차수가 0)의 개수가 T, 차수가 2인 노드의 개수가 M이므로

 

T = M+1이 성립한다.

 

​

(2) N개의 노드를 가지고 잇는 이진트리의 가능한 최대 깊이는 N이고, 최소 깊이는 [logN +1] 임을 설명하시오.

 

답안)

한 depth에는 반드시 하나의 노드가 들어간다. 최대 깊이를 갖는 경우는 사향트리처럼 각 노드가 각각 하나의 자식만을 갖는 경우이다. 즉, 다음과 같은 경우 최대 깊이는 N이 된다.

 

 

 

 

 

최소 깊이를 갖는 경우는 각각 노드가 최대의 자식을 가지도록, 즉 최대 2개의 노드를 가지도록 구성하는 것이다.

이진트리에서 노드의 개수와 depth(높이)의 상관관계에 의해 다음이 성립한다.

 

* 높이가 H인 이진트리는 최소 h개의 노드를 가지고 최대 2^(H -1)개의 노드를 가진다.

한 레벨에 최소 하나의 노드가 존재하고 최대 높이는 위에서 구한 바와 같이 N이며

높이 H의 이진트리가 가지는 최대 노드 개수는 2^(H-1)이므로 다음 식이 성립한다.

 

 

양변에 log를 취하고 식을 정리하면

 

 

따라서 이진트리가 가질 수 있는 최소 깊이는 [log(N+1)]이 된다.