트리(Tree)의 개념 - 정보올림피아드 문제풀이

트리(Tree)는 가장 기본적인 자료구조의 하나로 실제로도 많이 사용하지만 매우 중요하기 때문에 최근까지도 매년 한 문제 이상을 꼭 출제하는 분야입니다. 개념과 연관 알고리즘을 잘 알아두셔야 합니다.

트리 구조는 그래프(Graph, 꼭지점과 변으로 구성)의 한 종류로 1개 이상의 노드로 구성되며 사이클이 없는(acyclic graph) 그래프로 임의의 두노드간에 하나의 경로만이 존재합니다. 각 노드는 서로 중복되지 않는 원소로 구성된 부속트리(subtree)를 가질 수 있습니다. 트리 구조는 나무를 거꾸로 뒤집어 놓은 형태이며 최상위 노드는 Root(뿌리) 노드라 하고 레벨 1입니다. 루트 노드 아래로 한 단계씩 레벨(깊이)을 가지며 자식(child) 노드가 없는 노드를 leaf(잎)노드 또는 terminal(단말) 노드라 하고 자식이 하나라도 있는 노드를 Internal(내부)노드 또는 non-terminal 노드라 합니다. 트리에서 가장 큰 레벨 값을 트리의 깊이(depth)라 합니다. 자식 노드에 대하여 상위 노드를 부모(parent) 노드라하고 동일한 부모를 가진 자식 노드를 sibling(형제)노드라 합니다. 특정 노드의 부모 노드의 집합을 조상(ancestor)이라하고 반대로 특정 노드의 부속 트리의 모든 노드 집합을 자손(descendant)이라 합니다.

특정 노드의 자식 노드의 개수를 노드의 차수(degree) 또는 분지수라 하고 트리에서 가장 높은 값의 노드의 차수를 트리의 차수라 합니다. 트리 구조를 컴퓨터에 저장하기 위해서는 차수가 N인 트리의 경우에는 N개의 자식 노드 정보의 저장하기 위한 노드의 크기가 커지므로 상당히 비효율적이라는 문제가 있습니다. 이런 문제를 해소시켜주는 것이 차수가 2인 이진 트리입니다. 이진트리의 각 노드는 Left 링크는 자식 노드를 가리키고 Right 링크는 형제 노드를 가리키도록하여 어떤 차수의 트리도 이진 트리로 표현할 수 있습니다. 아래의 그림은 위의 트리 예제를 이진 트리로 표현한 것입니다. 

그러나, 이진 트리는 저장 구조로서의 특별한 성질을 가지고 있기 때문에 자식노드가 2이하인 트리라는 점외에도 다음과 같은 특성이 있습니다.

• 빈(empty) 트리도 이진트리다.
• 레벨(깊이)이 n인 이진트리의 최대 노드 수는 이다.(노드가 1개면 높이가 1로 간주할 때)
  레벨이 2면 1 + 2 = 4 -1 = 3
• 이진트리의 단노드 개수는 차수가 2인 노드의 개수 + 1이다.
  위의 이진트리 예를 보면 차수가 2인 노드는 a,d,f이므로 단노드의 개수는 3+1=4이다. 실제로 단노드는 j,e,i.m 4개다.

위와 같은 특성을 바탕으로 다음과 같이 이진 트리를 분류할 수 있습니다.

• 정(full) 이진트리 : 단말 노드가 아닌 모든 노드의 차수가 2인 이진트리

• 포화(perfect) 이진트리 : 이진트리의 깊이(레벨)이 N일때 트리의 모든 노드가 꽉차서 최대 노드수 공식을 만족시키는 경우로 모든 단말노드의 깊이가 동일한 정 이진트리라는 특성이 있다. 

• 완전(complete) 이진트리 : 포화 이진트리를 루트부터 차례로 위에서 아래로, 좌에서 우 방향으로 번호를 붙일때 끝 부분만 빈 상태를 말한다.

• 균형(balanced) 이진트리 : 모든 단말 노드의 깊이 차이가 최대 1인 이진트리를 말한다. 예측 가능성을 높인다.

• 편향(skewed) 이진트리 : 좌나 우 한쪽으로 치우친 이진트리

* 트리의 개념과 관련한 문제 풀기

아래의 문제들은 위에서 설명한 개념을 잘 읽으면 간단하게 풀수 있습니다.

1. 다음 트리에 대한 설명으로 옳지 않은 것은?

(1) 노드 B는 노드 D의 부모 노드(parent node)이다.

(2) 노드 D와 노드 E는 같은 레벨(level)에 있다.

(3) 노드 E와 노드 F는 형제 노드(sibling node)이다.

(4) 4개의 단말노드(terminal node)가 있다.

(5) 완전이진트리(complete binary tree)이다.

※ 형제 노드는 부모가 같은 동일레벨의 노드를 의미합니다.

2. 다음 트리에서 노드 E의 형제 노드(sibling node)는 몇 개인가?

① 1개   ② 2개 ③ 3개 ④ 4개 ⑤ 5개

※ 노드 E의 부모는 B이고 같은 부모노드를 가진 동일 레벨의 노드는 D, F입니다.

3. 다음 중 트리에 대한 설명으로 옳지 않은 것은?

① 임의의 두 노드(node) 사이의 경로(path)는 유일하다.

② 사이클(cycle)이 존재하지 않는다.

③ 이진트리에서 단말 노드(terminal node)의 개수는 분지수(degree)가 2인 내부 노드(internal node)의 개수보다 하나 더 많다.

④ 루트 노드(root)의 분지수(degree)가 가장 크다.

※ 루트 노드는 트리가 시작하는 특별한 노드일 뿐이지 자식 노드의 수를 가리키는 분지수 또는 차수가 크다는 특성은 없다. 분지수가 아니라 자손이 가장 많은 것은 맞다.

4. 트리(tree)에서 루트(root)로 놓았을 때 트리의 높이(height)가 가장 작아지는 노드(node)를 그 트리의 중심(center)이라고 한다. 그렇다면 다음 트리의 중심은? 

① 3  ② 4 ③ 5  ④ 6  ⑤ 7

※ 위의 문제는 이진트리의 특성과는 무관하게 단순한 트리 또는 그래프의 "지름"과 "중심"이라는 개념을 알면 명확합니다. 트리 또는 그래프에서 거리가 가장 먼 두 노드 사이의 거리를 "지름"이라 하고 이 지름의 중간에 해당하는 노드를 트리의 중심(center)으로 해서 트리를 재구성하면 높이(레벨)가 가장 작은 트리를 만들수 있다는 것입니다. 위의 문제를 보면 경로가 가장 긴것은 1-8 또는 3-8 구간으로 거리가 6입니다. 노드 8에서 거리 6의 절반인 3단계를 이동하여 중간인 5를 중심으로 하면 트리의 높이를 최소화 할 수 있습니다.

5. 아래 그림과 같은 트리의 차수(degree)는?

① 2  ② 3  ③ 4  ④ 7  ⑤ 10

※ 위의 개념 설명에도 언급한 것처럼 트리의 차수는 노드의 차수 중에서 가장 큰 값입니다.

6. 2개의 노드로 이루어진 서로 다른 이진트리는 2가지가 있다. 5개의 노드들로 이루어진 서로 다른 이진트리는 몇 가지인가?

① 42 ② 44 ③ 46 ④ 48 ⑤ 50

※ 이 문제는 일단 이진 트리의 특성을 잘 이해 해야 합니다. 이진 트리는 좌우 방향 성이 있기 때문이 2개의 노드만이라도 좌편향, 우편향 각각 2개의 이진 트리가 가능함을 이해해야 합니다. 아래의 그림은 노드가 3일때의 가능한 이진트리입니다.

그런데, 위의 같은 방식으로 노드 5개를 풀려면 시간도 많이 걸리지만 노드 개수가 많아지면 그 계산을 감당할 수 없습니다. 무엇보다 누군가 이런 상황을 대비해서 누군가 수열로 정리해 놓은 것이 있으니 잘 활용하는 것이 좋겠습니다. 그 수는 바로 카탈란수(Catalan) 입니다. 벨기에의 수학자 카탈란이 하노이의 탑 문제를 생각하며 만들었다고 합니다.(위키피디아 참조) 음수가 아닌 정수 n에 대해서 n번째 카탈란수는 다음의 공식과 같습니다.

위의 공식을 0부터 15까지 대입하면 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845가 됩니다. n개의 노드를 가진 이진 트리의 개수는 n번째 카탈란수와 동일합니다. 예제에서도 n이 2일때 2, 3일때 5임을 이미 확인할 수 있습니다. 또한 빈(Empty) 이진트리도 존재함을 기억하시면 0번째 카탈란수가 1임도 수긍이 되실것입니다. 5개의 노드를 가진 이진트리 개수는 42입니다. 

카탈란수는 다음과 같이 응용할 수 있습니다.

• n + 1개의 단말 노드를 갖는 이진 트리의 개수
• n + 2각형을 n개의 삼각형으로 나누는 방법의 개수
• n + 1개의 항에 2개의 항에 괄호를 씌우는 모든 경우의 수
• n + 1개의 항에 이항연산자를 적용하는 모든 경우의 수
• 길이가 2n인 모든 다이크(Dyck) 단어의 개수
  Dyck단어는 n개의 X, n개의 Y로 구성한 문자열을 처음부터 셀때 X가 Y보다 많거나 동일한 문자열을 말합니다.
  n=2이면 XXYY, XYXY 두개입니다.
• n개의 성냥개비로 오르막과 내리막이 대칭되는 산을 만들 수 있는 방법의 수
  
• n X n개의 정사각형으로 구성된 큰 정사각형의 양쪽 꼭지점을 작은 사각형의 변을 따라 이동할때 대각선을 지나치지 않고 갈수있는 최단 경로의 개수

7. 각 노드의 왼쪽 부트리와 오른쪽 부트리의 높이의 차이가 1이하인 이진트리를 높이균형트리라 한다. 높이가 8인 높이균형트리의 최소 노드 수는 얼마인가? 단 비어 있는 이진트리의 높이는 0이고, 1개의 노드로 이루어진 이진트리의 높이는 1이다. 

① 54 ② 55 ③ 56 ④ 57 ⑤ 58

※ 균형(balanced) 이진트리는 모든 단말 노드의 깊이 차이가 최대 1인 이진트리를 말함은 앞서 말씀드렸는데, 문제에서 노드 1개일때 높이가 1임을 유의하고 높이가 h인 높이 균형 트리(AVL트리)의 최소 노드수는 N(h)=N(h-1) + N(h-2) + 1를 적용합니다. 단, N(0) = 0, N(1) = 1, N(2) = 2를 적용합니다. N(3) = 2+1+1=4, N(4)=4+2+1 = 7, N(5)=7+4+1 = 12식입니다. 다음은 높이가 4일때 최소 노드로 구성한 높이 균형 트리입니다.

8. 루트가 있는 트리에서 노드의 분지수는 그 노드의 자식 노드의 개수를 말한다. 모든 노드의 분지수가 2 이하인 트리를 이진 트리라고 한다. 이진 트리에서 루트 노드의 레벨은 0이고, 루트가 아닌 노드의 레벨은 부모 노드의 레벨에 1을 더한 값으로 정의한다. 이진 트리의 높이는 트리에 속한 모든 노드에 대한 레벨의 최댓값이다. 노드의 개수가 1,000인 이진 트리의 최소 높이는 얼마인가? 

① 7 ② 8 ③ 9 ④ 10 ⑤ 11

※ 위의 개념 설명을 보시면 이진 트리가 최소 높이를 가지는 것은 포화이진트리일때 입니다. 또한 포화 이진 트리의 높이가 n일때의 최대 노드수는 루트를 0으로 간주 할 때는 루트를 1로 간주할 때는 이므로 특정 높이의 최대 노드수가 1000보다 큰것중에 가장 가까운 높이를 찾으면 될것입니다. 진법변환을 하다보면 2진수에 대해서는 외워두는 것이 필요한데 0승부터 차례대로 나열하면 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048......입니다. 보시면 아시겠지만 1000과 인접한 2의 10승인 1024를 확인할 수 있고 높이가 10일때의 최대 노드수는 1023입니다. 주의해야할 점은 이 공식은 노드가 1개일때 높이를 1로 간주했을경우이인데 반하여 문제에서는 루트 노드의 높이를 0이라 했으므로 최소 높이는 9입니다.