자연계열 3번

전체 시험 시간 2시간 내외

국민대 2012학년도 수시1차 자연계열 3번 · mathesis.kr/archive/kookmin/2012su_1/jayeon_3

【문제 3】【지정문제 2】(배점 35%)아래의 제시문을 읽고 다음 물음에 답하시오.

트리는 같은 꼭짓점으로 되돌아오는 경로가 없는 그래프이다. 트리의 꼭짓점은 노드라 하고, 변으로 연결된 두 노드 중 위의 노드는 부모 노드, 아래의 노드는 자식 노드라 한다. 루트(root) 기반 트리는 루트 노드라 하는 특별한 1개의 노드가 존재한다. 루트 노드는 부모 노드가 없다.루트 기반 트리의 일종인 이진트리는 컴퓨터 정보 처리를 위해 매우 유용하게 사용되는 트리로서 다음과 같이 구성된다.

1. 1개의 노드를 가지는 트리는 이진트리이다.2. 1개보다 많은 노드를 가지는 이진트리는 루트 노드와 2개의 이진 부분트리―왼쪽 이진 부분트리, 오른쪽 이진 부분트리―로 구성된다.

따라서 이진트리는 각 노드가 0개나 2개의 자식 노드를 갖는 특성을 보인다. 왼쪽 그림은 9개의 노드를 갖는 이진트리의 예로서 루트 노드 $\displaystyle n_1$ 과 2개의 이진 부분트리 $\displaystyle T_L$ 과 $\displaystyle T_R$ 로 구성된다. $\displaystyle T_L$ 과 $\displaystyle T_R$ 도 각각 자신의 루트 노드와 2개의 이진 부분트리로 구성되는 이진트리이다.자식 노드를 갖는 노드는 내부 노드, 자식 노드를 갖지 않는 노드는 단말 노드라 한다. 그림에서 원으로 나타낸 노드가 내부 노드, 사각형으로 나타낸 노드가 단말 노드이다.모든 노드는 루트 노드로 연결된 하나의 경로가 있으며, 각 노드의 경로의 길이는 경로 상에 있는 변의 개수이다. 예를 들어 $\displaystyle n_8$ 의 경로의 길이는 3이며 $\displaystyle n_3$ 의 경로의 길이는 1이다. 최대 경로의 길이를 트리의 높이라 한다. 루트 노드에서 노드까지의 경로의 길이를 노드의 깊이라 하고, 깊이가 $\displaystyle i$ 인 모든 노드의 집합을 레벨 $\displaystyle i$ 라 한다. 그러므로 레벨 $\displaystyle i$ 의 최대 노드 개수는 $\displaystyle 2^i$ 이다. 가령 루트 노드는 깊이가 0이고 레벨 0에 속하며, $\displaystyle n_4,n_5,n_6,n_7$ 은 깊이가 2이고 레벨 2에 속한다.

(3-1) 높이가 $\displaystyle h$ 인 이진트리가 가질 수 있는 최대 노드의 개수를 구하시오.

(3-2) 높이가 $\displaystyle h$ 인 이진트리에서 레벨 $\displaystyle i$ 에 속한 내부 노드의 개수를 $\displaystyle N_i$ 라고 할 때, $\displaystyle 0\le i<h$ 인 $\displaystyle i$ 에 대해 레벨 $\displaystyle i+1$ 의 노드 개수가 $\displaystyle 2N_i$ 임을 보이시오.

(3-3) 높이가 $\displaystyle h$ 인 이진트리에서 레벨 $\displaystyle i$ 에 속한 내부 노드의 개수를 $\displaystyle N_i$ , 레벨 $\displaystyle i$ 에 속한 단말 노드의 개수를 $\displaystyle L_i$ 라고 할 때, $\displaystyle 0\le i<h$ 인 $\displaystyle i$ 에 대해 $\displaystyle N_i=\frac{N_{i+1}+L_{i+1}}{2}$ 이 성립함을 보이시오.

(3-4) $\displaystyle n$ 개의 노드를 갖는 이진트리는 $\displaystyle n-1$ 개의 변을 가짐을 보이시오.

(3-5) $\displaystyle n$ 개의 단말 노드를 갖는 이진트리는 $\displaystyle n-1$ 개의 내부 노드를 가짐을 보이시오.

(3-6) $\displaystyle n$ 개의 단말 노드를 갖는 이진트리의 최대 높이가 $\displaystyle n-1$ 임을 보이시오.

해설강의 준비중

국민대 2012학년도 수시1차 자연계열 3번 · mathesis.kr/archive/kookmin/2012su_1/jayeon_3

(3-1)높이가 $\displaystyle h$ 인 이진트리의 최대 노드 개수= level 0 에서의 최대 노드 개수 + level 1 에서의 최대 노드 개수 + $\displaystyle \cdots$ + level $\displaystyle h$ 에서의 최대 노드 개수 = $\displaystyle 2^0+2^1+\cdots+2^h=2^{h+1}-1$ 이다.

(3-2)레벨 $\displaystyle i$ 의 단말 노드는 레벨 $\displaystyle i+1$ 에 0 개의 자식 노드를 생성하고, 레벨 $\displaystyle i$ 의 내부 노드는 레벨 $\displaystyle i+1$ 에 $\displaystyle 2N_i$ 개의 자식 노드를 생성하므로,레벨 $\displaystyle i+1$ 의 노드 개수 = (레벨 $\displaystyle i$ 의 내부 노드가 생성하는 자식 노드 수) +(레벨 $\displaystyle i$ 의 단말 노드가 생성하는 자식 노드 수)= $\displaystyle 2N_i$ 이다.

(3-3)문제 (3-2)에 의해 레벨 $\displaystyle i+1$ 은 정확히 $\displaystyle 2N_i$ 개의 노드를 가져야 한다.그러나 레벨 $\displaystyle i+1$ 에서의 총 노드 개수는 $\displaystyle N_{i+1}+L_{i+1}$ 으로 나타낼 수 있으므로 $\displaystyle 2N_i=N_{i+1}+L_{i+1}$ 이 되어 $\displaystyle N_i=\frac{N_{i+1}+L_{i+1}}{2}$ 식을 얻는다.

(3-4)이진트리의 루트 노드를 제외한 모든 노드는 왼쪽 또는 오른쪽 이진 부분트리의 루트 노드이므로 반드시 하나의 부모 노드와 변으로 연결되어야 한다. 따라서 루트 노드를 제외하면 $\displaystyle n-1$ 개의 노드가 있으므로 정확히 $\displaystyle n-1$ 개의 변이 필요하다.

(3-5) $\displaystyle s$ 를 이진트리에 있는 내부 노드 개수라 하자.이진트리의 모든 내부 노드는 2개의 자식 노드를 가지므로 이진트리에 있는 모든 변의 개수는 $\displaystyle 2s$ 이다.이진트리의 총 노드 개수는 $\displaystyle n+s$ 이므로 문제 (3-4)에 의해 이진트리에 있는 변의 개수는 $\displaystyle n+s-1$ 이다.따라서, $\displaystyle 2s=n+s-1$ , 즉 $\displaystyle s=n-1$ 이다.

(3-6)문제 (3-5)로부터 $\displaystyle n$ 개의 단말 노드를 가지는 이진트리는 총 $\displaystyle 2n-1$ 개의 노드를 갖는 것을 알 수 있다. 루트 노드 하나만 있는 레벨 0 외에는 모든 레벨이 최소 2개의 노드를 가져야 한다. 따라서 $\displaystyle 2n-2$ 개의 노드로 만들 수 있는 최대 개수의 레벨은 $\displaystyle n-1$ 개이므로, $\displaystyle n$ 개의 단말 노드를 가지는 이진트리는 최대 $\displaystyle (n-1)+1=n$ 개의 레벨, 즉 최대 $\displaystyle n-1$ 의 높이를 가질 수 있다.

첨삭 사례

아직 등록된 첨삭 사례가 없습니다.

질문과 답변 · 0개질문과 답변 · 고정 0개

아직 등록된 질문이 없습니다. 질문 작성은 멤버십 회원만 가능합니다.