2021 국가직9급 컴퓨터일반 6번 해설 — 이진트리 높이

① 299 8

이 선지 진술은 틀림(X)

높이를 노드 수로 세면 한쪽으로 치우친 이진트리의 최대 높이는 300이다. 높이 8의 포화 이진트리는 최대 255개 노드만 담을 수 있다.

② 299 9

이 선지 진술은 틀림(X)

최대 높이는 모든 노드가 한 방향으로 이어질 때 300이다. 최소 높이는 ceil(log2(301)) = 9이다.

③ 300 8

이 선지 진술은 틀림(X)

최대 높이 300은 맞지만 최소 높이 8은 부족하다. 높이 8은 최대 255개 노드까지이므로 300개에는 높이 9가 필요하다.

④ 300 9

이 선지 진술은 옳음(O)

최대 높이는 편향 트리일 때 노드 수와 같은 300이다. 최소 높이는 2^h - 1 >= 300을 만족하는 최소 h인 9이다.