방송대 자료구조 10강 : 선택 트리와 이진 트리 개수

방송대 자료구조 10강: 선택 트리와 이진 트리 개수

이번 강의에는 모양이 비슷한 트리가 세 가지 역할로 등장합니다. 여러 정렬 리스트의 다음 값을 고르는 선택 트리, 여러 트리를 하나의 이진 트리로 표현하는 숲 변환, 그리고 노드 수에 따른 이진 트리 모양을 세는 문제입니다. 이 글은 먼저 문제의 목적을 판별한 뒤, 승자·패자 트리 갱신, 숲의 왼쪽 자식-오른쪽 형제 변환, 순회와 카탈란 수 계산을 직접 재현하도록 구성합니다.

트리의 모양보다 먼저 묻는 일을 구분한다

선택 트리, 숲의 이진 트리 표현, 이진 트리 개수는 모두 노드와 간선을 사용하지만 해결하는 질문이 다릅니다. 선택 트리는 현재 후보 중 하나를 반복해서 고르고, 숲 변환은 여러 계층 구조의 관계를 두 링크로 보존하며, 이진 트리 개수는 가능한 구조가 몇 개인지를 셉니다.

문제에서 묻는 것	사용할 개념	핵심 단서	결과
정렬된 여러 리스트에서 다음 최솟값 선택	선택 트리	각 리스트의 머리 값, 승자 또는 패자	병합할 다음 값
분리된 여러 트리를 이진 링크로 표현	숲의 이진 트리 변환	왼쪽 자식, 오른쪽 형제	관계를 보존한 한 이진 트리
노드 n개로 만들 수 있는 모양의 수	카탈란 수	순회, 스택의 합법적인 push/pop	서로 다른 이진 트리의 개수

따라서 그림이 이진 트리처럼 보인다는 이유만으로 같은 규칙을 적용하면 안 됩니다. 내부 노드에 비교 결과를 저장하는지, 원래 트리의 관계를 보존하는지, 아니면 구조 자체를 세는지부터 확인해야 합니다.

첫 판단: 값을 고르는 문제라면 선택 트리, 관계를 옮기는 문제라면 숲 변환, 가능한 경우의 수를 묻는 문제라면 카탈란 수를 출발점으로 삼습니다.

선택 트리는 리스트 전체가 아니라 현재 후보끼리 겨룬다

병합 정렬은 이미 정렬된 여러 리스트를 정렬 상태가 유지되는 하나의 리스트로 합치는 과정입니다. 리스트가 k개라면 매번 각 리스트의 첫 원소 가운데 최솟값을 찾아 출력하고, 그 값이 나온 리스트의 다음 원소를 새 후보로 올립니다. 후보를 매번 처음부터 차례로 비교하면 한 값을 고르는 데 보통 k-1번 비교가 필요합니다.

선택 트리(selection tree)는 후보를 리프에 놓고 토너먼트 방식으로 비교 결과를 위로 전달합니다. 최초 트리를 만드는 비교는 필요하지만, 최솟값을 하나 출력한 뒤에는 바뀐 리프에서 루트까지의 경로만 다시 비교합니다. 강의자료의 8개 리스트에서는 머리 값만 리프에 놓고 작은 값이 위로 올라가 루트에서 전체 최솟값을 얻습니다.

학습용으로 다음 네 리스트를 가정해 봅시다. 각 리스트는 오름차순이고, 괄호 안은 아직 출력하지 않은 값입니다.

리스트	남은 값	현재 후보
A	6, 19, 31	6
B	4, 17	4
C	9, 14, 28	9
D	7, 22	7

첫 라운드에서 A의 6과 B의 4를 비교하면 4가 이기고, C의 9와 D의 7을 비교하면 7이 이깁니다. 마지막으로 4와 7을 비교하므로 첫 출력은 4입니다. B의 후보를 다음 값 17로 바꾸면 17은 A의 6과 다시 겨루고, 그 승자 6만 루트 방향으로 올라가 7과 비교합니다. 따라서 두 번째 출력은 6입니다.

리프가 4개인 완전한 토너먼트에서는 최초 구성에 3번, 한 리프를 바꾼 뒤 갱신에 루트까지 2번 비교합니다. 일반적으로 갱신 비교 수는 선택 트리의 높이에 비례합니다. 이 차이가 ‘매번 모든 후보를 다시 훑기’와 ‘바뀐 경로만 고치기’의 핵심 차이입니다.

승자 트리와 패자 트리는 저장 위치가 다르다

승자 트리(winner tree)는 두 자식의 비교에서 이긴 값, 즉 최솟값을 부모 노드에 저장합니다. 루트에는 전체 승자가 있으므로 그 값을 출력한 뒤 해당 리프를 다음 후보로 교체합니다. 교체된 리프에서 루트까지 승자를 다시 계산하면 됩니다.

패자 트리(loser tree)도 작은 값이 다음 비교로 올라간다는 규칙은 같습니다. 다만 내부 노드에는 그 비교에서 진 값, 즉 더 큰 값을 저장하고, 최종 승자는 루트 위의 0번 노드에 따로 둡니다. 강의자료에서 트리의 루트는 마지막 비교의 패자를, 0번 노드는 최종 승자를 보관합니다.

비교 기준	승자 트리	패자 트리
리프	각 리스트의 현재 머리 값	각 리스트의 현재 머리 값을 가리킴
내부 노드	비교의 승자 저장	비교의 패자 저장
최종 승자	루트에 저장	루트 위 0번 노드에 저장
출력 뒤 갱신	바뀐 리프부터 루트까지 승자 재계산	바뀐 후보가 경로의 패자들과 재대결
출력 순서	같은 입력이면 동일	같은 입력이면 동일

‘패자 트리이므로 큰 값을 출력한다’는 해석은 잘못입니다. 패자를 내부에 저장하는 것은 다음 비교를 위한 기록 방식일 뿐이며, 최종 출력은 여전히 가장 작은 승자입니다. 또한 어느 리스트의 원소를 모두 사용했다면 그 리프에는 다른 유효 값보다 큰 센티널 값인 무한대(∞)를 넣습니다. 그래야 빈 리스트가 다시 승자로 선택되지 않습니다.

오개념 교정: 승자·패자라는 말은 출력할 값의 방향이 아니라 내부 노드에 어느 쪽의 비교 결과를 남기는지를 가리킵니다. 두 구조 모두 오름차순 병합에서는 최솟값을 계속 출력합니다.

숲은 빈 경우까지 포함하는 분리된 트리의 집합이다

숲(forest)은 서로 분리된 트리의 집합이며 트리 수는 0개 이상입니다. 트리 한 개만 있는 경우도 숲이고, 트리가 하나도 없는 빈 숲도 정의에 포함됩니다. 한 트리의 루트를 제거하면 루트의 각 자식이 새 트리의 루트가 되어 숲이 만들어지고, 반대로 여러 트리의 루트를 적절히 연결하면 다시 하나의 트리를 만들 수 있습니다.

숲 F=(T₁,T₂,…,Tₙ)을 이진 트리로 바꾸는 규칙은 재귀적으로 정리할 수 있습니다.

1. n=0이면 결과는 빈 이진 트리입니다.
2. n=1이면 T₁을 왼쪽 자식-오른쪽 형제 규칙으로 바꾼 이진 트리가 결과입니다.
3. n≥2이면 T₁ 변환 트리의 루트를 전체 루트로 삼고, 왼쪽에는 T₁의 자식 관계를, 오른쪽에는 나머지 숲 (T₂,…,Tₙ)의 변환 결과를 연결합니다.

일반 트리 한 개를 바꿀 때 첫째 자식은 왼쪽 포인터로, 다음 형제는 오른쪽 포인터로 이어집니다. 숲에서는 이 규칙을 각 트리에 먼저 적용한 뒤, 숲의 각 트리 루트도 형제처럼 오른쪽 포인터로 연결합니다. 그래서 첫 트리의 루트가 전체 이진 트리의 루트가 됩니다.

왼쪽은 첫째 자식, 오른쪽은 다음 형제로 읽는다

직접 만든 숲을 변환해 보겠습니다. 첫 트리의 루트 A에는 자식 B, C가 이 순서로 있고, 둘째 트리의 루트 D에는 자식 E가 있다고 가정합니다. 이 숲의 원래 관계를 두 종류의 링크로 옮기면 다음과 같습니다.

원래 관계	이진 트리 링크	이유
A의 첫째 자식은 B	A.left = B	첫째 자식은 왼쪽 링크
B 다음 형제는 C	B.right = C	다음 형제는 오른쪽 링크
숲에서 A 다음 루트는 D	A.right = D	분리된 트리의 루트들을 오른쪽으로 연결
D의 첫째 자식은 E	D.left = E	둘째 트리 안에서도 같은 규칙 적용

여기서 A의 오른쪽 링크는 A의 자식 C로 가는 링크가 아닙니다. A는 숲을 구성하는 첫 트리의 루트이므로 오른쪽 링크가 다음 트리의 루트 D를 가리킵니다. 반면 A의 자식들 사이에서는 B의 오른쪽 링크가 형제 C를 가리킵니다.

변환 검산 순서: 각 노드의 첫째 자식을 왼쪽으로 보낸 뒤, 같은 부모를 둔 형제들을 오른쪽으로 잇고, 마지막으로 숲의 루트들도 오른쪽으로 잇습니다. 원래 부모의 둘째·셋째 자식을 부모의 오른쪽 자식으로 직접 연결하면 관계가 깨집니다.

순회 두 개는 이진 트리 한 개를 복원한다

서로 다른 값을 가진 이진 트리에서 전위 순회와 중위 순회가 함께 주어지면 구조를 유일하게 정할 수 있습니다. 전위 순회의 첫 값은 언제나 루트이고, 중위 순회에서 그 루트의 왼쪽에 있는 값들은 왼쪽 서브트리, 오른쪽에 있는 값들은 오른쪽 서브트리에 속합니다. 각 구간에 같은 규칙을 재귀적으로 적용합니다.

학습용 예로 전위 순회가 A, B, D, C, E, 중위 순회가 D, B, A, C, E라고 합시다.

1. 전위 순회의 첫 값 A가 루트입니다.
2. 중위 순회에서 A 왼쪽의 D, B는 왼쪽 서브트리, 오른쪽의 C, E는 오른쪽 서브트리입니다.
3. 왼쪽 구간의 전위 순회 첫 값 B가 왼쪽 서브트리의 루트이고, 중위 순서에서 D가 B 왼쪽에 있으므로 D는 B의 왼쪽 자식입니다.
4. 오른쪽 구간의 루트는 C이고, 중위 순서에서 E가 C 오른쪽에 있으므로 E는 C의 오른쪽 자식입니다.

전위 순회 하나만으로는 노드가 왼쪽에 붙었는지 오른쪽에 붙었는지 구분할 수 없어 여러 구조가 가능합니다. 중위 순회 하나만으로도 루트를 알 수 없습니다. 두 순회의 역할을 합쳐야 뿌리와 좌우 구간이 동시에 정해집니다.

경계 조건: 이 복원 규칙은 노드 값을 서로 구분할 수 있다는 전제에서 사용합니다. 중복 값이 있으면 값만으로 중위 순회의 어느 위치를 가리키는지 모호할 수 있습니다.

합법적인 스택 연산의 수가 이진 트리 모양의 수가 된다

강의자료는 전위 순회 값을 스택에 넣고 push와 pop으로 중위 순회를 만드는 관점에서 이진 트리의 수를 설명합니다. push는 껍데기 노드와 그 왼쪽 서브트리를 만드는 방향을, pop은 현재 노드에 값을 정하고 오른쪽 서브트리로 이동하는 경계를 나타냅니다.

노드가 n개이면 push와 pop이 각각 n번 필요합니다. 그러나 이 2n개 연산을 아무 순서로 놓을 수는 없습니다. 아직 넣지 않은 원소를 꺼낼 수 없으므로 어느 중간 지점에서도 누적 pop 횟수가 누적 push 횟수보다 많아서는 안 됩니다. 이 조건을 만족하는 연산 배열 하나가 하나의 가능한 이진 트리 구조와 대응합니다.

노드 n개로 만들 수 있는 서로 다른 이진 트리의 개수는 카탈란 수입니다.

C_n = (2n)! / {n!(n+1)!}

노드 수 n	계산	가능한 이진 트리 수
0	0! / (0!·1!)	1
1	2! / (1!·2!)	1
2	4! / (2!·3!)	2
3	6! / (3!·4!) = 720 / 144	5
4	8! / (4!·5!) = 40320 / 2880	14

빈 이진 트리도 하나의 구조로 세므로 C₀=1입니다. 노드 3개일 때 강의자료가 제시한 다섯 모양도 C₃=5와 일치합니다. ‘노드에 붙이는 값의 순열’까지 세는 것이 아니라, 정해진 순회 관점에서 서로 다른 이진 트리 구조를 세는 문제라는 점을 구분해야 합니다.

새 문제는 선택·연결·계수의 순서로 판별한다

한 문제 안에 트리, 리스트, 순회, 스택이 함께 등장하면 다음 순서로 판단하면 혼동을 줄일 수 있습니다.

1. 목적을 묻습니다. 다음 최솟값을 고르는가, 여러 트리의 관계를 옮기는가, 가능한 구조 수를 세는가?
2. 저장 의미를 확인합니다. 선택 트리의 내부 노드는 비교 결과이고, 숲 변환의 링크는 첫째 자식과 다음 형제입니다.
3. 변경 범위를 좁힙니다. 선택 트리는 출력한 리스트의 리프부터 루트까지만 갱신하고, 숲 변환은 각 트리 내부와 루트 사이 연결을 나눠 처리합니다.
4. 경계 조건을 검사합니다. 빈 리스트에는 ∞를 넣고, 빈 숲과 빈 이진 트리도 정의와 개수에 포함하며, 스택은 비어 있을 때 꺼낼 수 없습니다.
5. 결과를 역검산합니다. 병합 결과가 오름차순인지, 변환 후 링크로 원래 부모·형제 관계를 복원할 수 있는지, 작은 n에서 카탈란 값이 1, 1, 2, 5와 맞는지 확인합니다.

핵심 정리

• 선택 트리는 정렬 리스트의 머리 값만 비교하고, 출력 뒤에는 바뀐 경로만 갱신합니다.
• 승자 트리는 내부에 승자를, 패자 트리는 내부에 패자를 저장하지만 둘 다 최종 최솟값을 출력합니다.
• 숲은 0개 이상의 분리된 트리이며, 첫째 자식은 왼쪽, 다음 형제와 다음 트리의 루트는 오른쪽으로 연결합니다.
• 전위와 중위 순회를 함께 사용하면 서로 다른 값을 가진 이진 트리 구조를 유일하게 복원할 수 있습니다.
• 노드 n개의 이진 트리 구조 수는 (2n)! / {n!(n+1)!}이며 합법적인 스택 연산 수와 연결됩니다.

마지막 점검: 트리 그림을 보자마자 공식을 고르지 말고, 노드가 ‘후보의 비교 결과’, ‘계층 관계의 링크’, ‘세어야 할 구조’ 중 무엇을 뜻하는지 먼저 말로 설명해 보세요. 그 한 문장이 정해지면 갱신 경로, 변환 방향, 카탈란 계산이 서로 뒤섞이지 않습니다.

예상문제 10선

1. 선택 트리의 주된 용도로 가장 알맞은 것은?

① 정렬되지 않은 한 리스트를 이진 탐색 트리로 바꾼다. ② 여러 정렬 리스트의 현재 후보 중 다음 출력값을 반복해서 고른다. ③ 숲에 속한 모든 루트를 왼쪽 링크로 연결한다. ④ 노드 수에 따른 이진 트리 개수를 직접 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 선택 트리는 한 리스트를 탐색 트리로 변환하는 구조가 아니다.
• ② 정답: 각 정렬 리스트의 머리 값을 후보로 두고 병합할 다음 값을 선택한다.
• ③ 오답: 숲의 루트는 오른쪽 링크로 이어지며 이는 선택 트리의 목적도 아니다.
• ④ 오답: 구조의 개수는 카탈란 수로 계산하며 선택 트리 내부에 저장하지 않는다.

2. 승자 트리와 패자 트리를 올바르게 비교한 것은?

① 승자 트리는 최댓값, 패자 트리는 최솟값을 출력한다. ② 승자 트리만 리스트의 머리 값을 리프에 둔다. ③ 패자 트리의 0번 노드에는 마지막 패자가 저장된다. ④ 승자 트리는 내부에 승자를, 패자 트리는 내부에 패자를 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 오름차순 병합에서는 두 구조 모두 최종 최솟값을 출력한다.
• ② 오답: 두 구조 모두 각 리스트의 현재 후보를 리프에서 사용한다.
• ③ 오답: 0번 노드는 최종 승자를 저장하고 트리 루트가 마지막 패자를 저장한다.
• ④ 정답: 두 구조의 핵심 차이는 각 비교의 어느 결과를 내부 노드에 남기는가이다.

3. 본문의 A, B, C, D 리스트에서 4를 출력하여 B의 후보가 17로 바뀐 직후, 다음 출력값은?

① 6 ② 7 ③ 9 ④ 17

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 갱신된 후보 6, 17, 9, 7 가운데 최솟값은 6이다.
• ② 오답: 7은 C·D 쪽 비교의 승자지만 전체 승자 6보다 크다.
• ③ 오답: 9는 같은 쌍의 7에게 먼저 진다.
• ④ 오답: 17은 B의 새 후보이나 A의 6에게 진다.

4. 오름차순 병합 중 한 리스트를 모두 사용했을 때 그 리프를 처리하는 올바른 방법은?

① 0을 넣어 가장 먼저 선택되게 한다. ② 방금 출력한 값을 그대로 둔다. ③ 유효한 모든 후보보다 큰 ∞를 넣어 다시 이기지 않게 한다. ④ 다른 리스트의 머리 값을 복제한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 0은 계속 최솟값으로 선택되어 이미 빈 리스트를 다시 가리킨다.
• ② 오답: 같은 값을 중복 출력하게 된다.
• ③ 정답: 큰 센티널은 다른 유효 후보가 모두 먼저 선택되게 한다.
• ④ 오답: 후보를 복제하면 어느 리스트에서 값을 소비해야 하는지 관계가 훼손된다.

5. 숲의 정의로 옳은 것은?

① 반드시 두 개 이상의 연결된 트리로만 구성된다. ② 0개 이상의 서로 분리된 트리로 이루어진 집합이다. ③ 모든 노드가 같은 루트를 공유하는 완전 이진 트리이다. ④ 리프 노드만 모아 둔 선형 리스트이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 숲은 빈 경우와 트리 하나인 경우도 포함하며 각 트리는 서로 분리된다.
• ② 정답: 트리 수 n≥0인 분리된 트리 집합이 숲이다.
• ③ 오답: 같은 루트를 공유하면 분리된 트리의 집합이 아니라 하나의 트리이다.
• ④ 오답: 숲의 각 트리는 내부 노드와 간선을 가질 수 있다.

6. 본문의 숲에서 A의 자식이 B, C이고 다음 트리의 루트가 D일 때 옳은 링크 묶음은?

① A.left=B, B.right=C, A.right=D ② A.right=B, B.left=C, C.right=D ③ A.left=C, C.left=B, B.left=D ④ A.right=C, C.right=B, B.right=D

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 첫째 자식은 왼쪽, 다음 형제와 다음 트리의 루트는 오른쪽으로 연결한다.
• ② 오답: 첫째 자식 B를 오른쪽에 둔 것부터 규칙에 어긋난다.
• ③ 오답: 자식 순서를 뒤집고 모든 관계를 왼쪽 링크로 바꾸었다.
• ④ 오답: A의 첫째 자식은 C가 아니라 B이며 D도 B의 형제가 아니다.

7. 서로 다른 노드의 전위 순회와 중위 순회로 이진 트리를 복원할 때 가장 먼저 할 일은?

① 중위 순회의 마지막 값을 루트로 정한다. ② 두 순회를 오름차순으로 정렬한다. ③ 전위 순회의 마지막 값을 가장 왼쪽 리프로 정한다. ④ 전위 순회의 첫 값을 루트로 정하고 중위 순회에서 좌우 구간을 나눈다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 중위 순회의 끝은 루트를 보장하지 않는다.
• ② 오답: 순회 순서를 정렬하면 트리의 구조 정보가 사라진다.
• ③ 오답: 전위 순회의 마지막 노드 위치는 트리 모양에 따라 달라진다.
• ④ 정답: 전위 첫 값이 루트이고 중위 순회가 왼쪽·오른쪽 서브트리 범위를 정한다.

8. 카탈란 공식을 적용할 때 노드 4개로 만들 수 있는 서로 다른 이진 트리 구조의 수는?

① 5 ② 8 ③ 14 ④ 24

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 5는 노드 3개의 카탈란 수이다.
• ② 오답: 노드마다 좌우 두 선택을 독립적으로 하는 2³ 계산은 트리 구조 조건을 반영하지 못한다.
• ③ 정답: C₄=8!/(4!·5!)=40320/2880=14이다.
• ④ 오답: 4!은 값의 배열 순열이며 이진 트리 모양의 수가 아니다.

9. 노드 3개의 스택 연산 배열 중 이진 트리 생성 과정으로 사용할 수 없는 것은? (P는 push, O는 pop)

① P P P O O O ② P O P P O O ③ P O O P P O ④ P P O O P O

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 모든 접두 구간에서 pop 수가 push 수를 넘지 않는 합법적 배열이다.
• ② 오답: 첫 노드를 꺼낸 뒤 새 노드를 넣으며 스택 공백 위반이 없다.
• ③ 정답: 세 번째 연산에서 push는 1번인데 pop이 2번이 되어 빈 스택에서 꺼내려 한다.
• ④ 오답: 두 번 넣고 두 번 꺼낸 뒤 다시 넣고 꺼내므로 모든 중간 상태가 유효하다.

10. 문제와 해결 개념의 연결이 가장 적절한 것은?

① 정렬 리스트 병합의 다음 값 선택—카탈란 수 ② 숲의 계층 관계를 두 링크로 보존—왼쪽 자식-오른쪽 형제 변환 ③ 노드 수에 따른 구조의 수 계산—패자 트리의 0번 노드 ④ 빈 리스트의 재선택 방지—전위·중위 순회 복원

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 다음 값을 반복 선택하는 구조는 선택 트리이다.
• ② 정답: 첫째 자식과 다음 형제 링크로 숲의 부모·형제 관계를 보존한다.
• ③ 오답: 구조의 수는 카탈란 수로 계산하고 0번 노드는 패자 트리의 최종 승자 저장 위치이다.
• ④ 오답: 빈 리스트에는 큰 센티널 ∞를 넣으며 순회 복원과는 관계없다.

참고 자료와 작성 기준

• 자료 성격: 한국방송통신대학교 자료구조 10강 강의록을 바탕으로 개념의 관계와 풀이 절차를 재구성한 비공식 학습자료입니다.
• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 자료구조 10강 「선택 트리, 숲, 이진 트리 개수」
• 외부 보충 자료: 사용하지 않았습니다.
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토일: 2026년 8월 18일