방송대 방통대 이산수학 11강 - 트리 - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 11강 - 트리

사이클이 없는 연결 그래프인 트리의 구조와 주요 용어를 익히고, 이진 트리의 노드 수와 최소 높이를 계산한다. 이진 탐색 트리의 구성·검색 효율을 이해한 뒤 신장 트리와 최소 신장 트리, Kruskal 알고리즘과 Prim 알고리즘까지 학습한다.

1. 트리의 정의와 종류

트리의 그래프적 정의

트리(tree)는 사이클이 없는 단순 연결 그래프이다. 단순 그래프이므로 고리나 중복되는 변이 없고, 연결 그래프이므로 임의의 두 꼭지점 사이에 경로가 존재한다. 여기에 사이클이 없다는 조건이 더해져 계층적인 구조가 만들어진다.

꼭지점 하나만으로 이루어진 트리를 자명 트리(trivial tree)라고 한다. 꼭지점이 하나도 없는 트리는 공백 트리(empty tree)이다. 하나 이상의 서로 분리된 트리로 구성된 그래프를 포리스트(forest)라고 한다.

트리의 여러 계열

트리는 자식 수와 탐색 방식, 균형 유지 방식에 따라 여러 형태로 발전한다. 이진 트리 계열에는 힙, 이진 탐색 트리, AVL 트리, BB 트리, 스플레이 트리 등이 있다. m-원 트리 계열에는 트라이, m-원 탐색 트리, B 트리와 B*-트리, B+ 트리, 2-3 트리, 2-3-4 트리, 레드-블랙 트리 등이 포함된다.

그래프가 트리가 되려면 연결되어 있어야 하고 사이클이 없어야 한다. 둘 중 하나라도 만족하지 않으면 트리가 아니다.

2. 루트 트리와 서브트리

루트 트리의 재귀적 정의

루트 트리(rooted tree)는 하나 이상의 노드로 이루어진 유한집합으로, 특별히 지정한 하나의 노드가 루트(root)가 된다. 루트를 제외한 나머지 노드는 서로 분리된 집합 T₁,T₂,…,Tₘ으로 나뉘며, 각 집합은 다시 루트 트리가 된다.

이때 T₁,T₂,…,Tₘ을 루트의 서브트리(subtree)라고 한다. 같은 정의가 각 서브트리에도 반복되므로 트리는 작은 트리들이 계층적으로 결합된 재귀적 구조로 이해할 수 있다.

그래프에서 루트 트리로

일반 트리에서 특정 노드를 루트로 정하면 부모와 자식의 방향이 정해진다. 루트는 부모가 없으며, 루트에서 멀어지는 방향으로 자식 노드가 이어진다. 같은 무방향 트리라도 어느 노드를 루트로 선택하는지에 따라 부모·자식 관계와 서브트리의 모양이 달라질 수 있다.

트리와 루트 트리를 구분해야 한다. 트리는 그래프의 연결성과 사이클 여부로 정의하고, 루트 트리는 특정 노드를 기준으로 계층과 부모·자식 관계를 부여한 트리이다.

3. 트리의 주요 용어

부모·자식·형제와 차수

노드 N의 바로 아래에 연결된 노드를 자식(child) 노드, 바로 위에 연결된 노드를 부모(parent) 노드라고 한다. 같은 부모를 가진 노드들은 서로 형제(sibling) 노드이다.

노드 N의 차수(degree)는 그 노드가 가진 자식 노드의 수이다. 트리 T의 차수는 트리에 속한 모든 노드의 차수 가운데 가장 큰 값이다. 따라서 트리의 차수는 가장 많은 자식을 가진 노드의 자식 수로 결정된다.

리프·내부 노드·레벨

자식이 없는 노드를 리프(leaf) 노드 또는 단말(terminal) 노드라고 한다. 자식을 가진 노드는 내부(internal) 노드이다. 노드 N의 레벨(level)은 루트에서 N까지 경로의 길이이며, 루트의 레벨은 0이다.

높이와 무게

트리의 높이(height) 또는 깊이(depth)는 트리에 있는 노드의 레벨 중 최댓값이다. 가장 깊은 리프까지 가는 경로의 길이라고 생각하면 된다. 트리의 무게(weight)는 리프 노드의 개수이다.

용어	의미
노드의 차수	해당 노드가 가진 자식의 수
트리의 차수	모든 노드 차수 중 최댓값
리프 노드	자식이 없는 단말 노드
노드의 레벨	루트에서 해당 노드까지 경로의 길이
트리의 높이	노드 레벨의 최댓값
트리의 무게	리프 노드의 개수

4. 트리의 표현과 닮은 트리

중첩된 집합

트리는 각 노드의 서브트리를 집합 안의 집합으로 넣는 중첩된 집합으로 표현할 수 있다. 루트에 해당하는 큰 집합 안에 자식 노드의 집합이 들어가고, 그 안에 다시 후손 노드의 집합을 배치하여 포함 관계로 계층을 나타낸다.

중첩된 괄호

중첩된 괄호는 노드 이름 뒤에 자식 서브트리를 괄호로 나열한다. 강의의 트리는 다음과 같이 표현된다.

(A (B (E) (F) (G)) (C) (D (H (I) (J) (K))))

가장 바깥의 A가 루트이고, 바로 안의 B, C, D가 자식이다. D 아래의 H와 그 아래의 I, J, K도 괄호의 중첩 깊이로 확인할 수 있다.

결각과 닮은 트리

결각은 노드를 들여쓰기하거나 기준선에서 떨어진 정도로 계층을 나타내는 표현이다. 트리 모양을 직접 그리지 않아도 노드의 깊이와 부모·자식 관계를 보여 줄 수 있다.

두 트리의 구조는 같지만 각 노드에 저장된 데이터만 다르면 두 트리는 서로 닮았다고 한다. 닮은 트리는 노드 이름이나 값이 아니라 부모·자식 연결 구조가 동일한지를 기준으로 판단한다.

5. 트리의 꼭지점과 변에 관한 정리

트리이면 변은 n-1개

n개의 꼭지점을 가지는 트리는 정확히 n-1개의 변을 가진다. 꼭지점 하나에서 시작해 새로운 꼭지점을 연결할 때마다 사이클을 만들지 않으면서 연결을 유지하려면 변이 하나씩 필요하기 때문이다.

연결 그래프에서의 역

n개의 꼭지점을 가진 연결 그래프가 n-1개의 변을 가지면 그 그래프는 트리이다. 연결된 상태에서 변이 n-1개뿐이라면 사이클을 포함할 여분의 변이 없기 때문이다.

G=(V,E)가 |V|=n인 연결 그래프라면 다음이 성립한다.

G가 트리 ⇔ |E|=n-1

|E|=|V|-1만 보고 곧바로 트리라고 판단해서는 안 된다. 이 동치가 성립하려면 그래프가 연결 그래프라는 전제가 필요하다.

6. 이진 트리의 정의와 특징

이진 트리

이진 트리(binary tree)는 공집합이거나, 각 노드가 최대 두 개의 서로 다른 서브트리를 갖는 루트 트리이다. 두 서브트리는 각각 왼쪽 서브트리와 오른쪽 서브트리라고 하며, 직접 연결된 노드는 왼쪽 자식과 오른쪽 자식이다.

일반 루트 트리와 달리 이진 트리는 공집합일 수 있고 왼쪽과 오른쪽을 구분한다. 따라서 루트에 자식 하나만 있는 경우에도 그 자식이 왼쪽인지 오른쪽인지에 따라 서로 다른 이진 트리가 된다.

높이에 따른 최대 노드 수

루트의 레벨을 0으로 할 때 높이가 h인 이진 트리의 각 레벨에는 최대 2ⁱ개의 노드가 있을 수 있다. 따라서 전체 최대 노드 수는 다음과 같다.

1+2+2²+…+2ʰ = Σ(i=0…h)2ⁱ = 2^(h+1)-1

예를 들어 높이가 3이면 최대 노드 수는 1+2+4+8=15이다. 높이가 4이면 최대 2⁵-1=31개의 노드를 가질 수 있다.

7. 완전·포화·경사 이진 트리

완전 이진 트리

완전 이진 트리(complete binary tree)는 높이가 h일 때 레벨 0부터 h-1까지 모든 노드가 채워져 있고, 마지막 레벨 h에서는 왼쪽부터 차례로 노드가 채워진 이진 트리이다. 같은 노드 수를 갖는 이진 트리 가운데 최소 높이를 갖는다.

n개 노드를 가진 이진 트리의 최소 높이는 Hmin=⌊log₂n⌋이다. 예를 들어 노드가 1개이면 최소 높이는 0, 3개이면 1, 7개이면 2, 14개이면 3이다.

포화 이진 트리

포화 이진 트리(full binary tree)는 높이가 k일 때 레벨 0부터 레벨 k까지 모든 가능한 노드가 채워진 이진 트리이다. 완전 이진 트리의 특별한 경우이며 노드 수는 정확히 2^(k+1)-1개이다.

경사 이진 트리

경사 이진 트리는 노드가 한쪽 자식 방향으로만 이어진 형태이다. 노드가 n개이면 높이가 n-1까지 커질 수 있다. 강의의 14개 노드 예에서 완전 이진 트리는 높이가 3이지만 경사 이진 트리는 높이가 13이다.

종류	노드 배치	높이 특징
완전 이진 트리	마지막 레벨 전까지 가득 차고 마지막은 왼쪽부터 채움	같은 노드 수에서 최소 높이
포화 이진 트리	모든 레벨이 완전히 채워짐	높이 h에서 노드 수 2^(h+1)-1
경사 이진 트리	각 노드가 주로 한쪽 자식만 가짐	n개 노드에서 높이 n-1 가능

높이 5인 포화 이진 트리의 노드 수는 반드시 2⁶-1=63개이므로 60개 노드를 가진 포화 이진 트리는 존재하지 않는다. 반면 높이 2인 일반 이진 트리는 최대 7개까지 가능하므로 6개 노드를 가진 형태는 존재할 수 있다.

8. 이진 탐색 트리의 정의와 구성

이진 탐색 트리의 조건

이진 탐색 트리(binary search tree)는 모든 노드가 탐색에 사용할 키 값을 가지며 다음 조건을 만족하는 이진 트리이다.

• 임의의 노드 Nᵢ에 대해 왼쪽 서브트리의 모든 키는 Nᵢ의 키보다 작다.
• 임의의 노드 Nᵢ에 대해 오른쪽 서브트리의 모든 키는 Nᵢ의 키보다 크다.

이 조건은 루트뿐 아니라 모든 서브트리의 노드에서 반복되어야 한다. 어떤 노드의 바로 왼쪽 자식만 작은 것으로 충분하지 않고, 왼쪽 서브트리 전체가 해당 노드보다 작은 값을 가져야 한다.

삽입 순서와 트리의 모양

키를 하나씩 삽입할 때 첫 키가 루트가 된다. 새 키가 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 내려가 빈 자리에 삽입한다. 같은 키 집합이라도 입력 순서가 다르면 서로 다른 모양의 이진 탐색 트리가 만들어질 수 있다.

예를 들어 7,3,9,6,2,4,8,1,5 순으로 삽입하면 7을 루트로 하여 양쪽에 비교적 분산된 트리가 만들어진다. 반대로 1,2,3,4,5,6,7,8,9처럼 오름차순으로 삽입하면 모든 노드가 오른쪽으로 이어지는 높이 8의 경사 트리가 된다.

이진 탐색 트리의 모양은 키의 집합뿐 아니라 삽입 순서에 의해 결정된다. 정렬된 순서로 삽입하면 트리가 경사져 검색 효율이 낮아질 수 있다.

9. 이진 탐색 트리의 검색과 효율

검색 절차

1. 루트 노드를 현재 탐색 노드로 설정한다.
2. 현재 노드의 키와 찾을 키를 비교한다.
3. 두 키가 같으면 키를 반환하고 탐색을 끝낸다.
4. 찾을 키가 작으면 왼쪽 자식으로, 크면 오른쪽 자식으로 이동한다.
5. 이동할 자식이 없으면 키가 없음을 반환하고, 그렇지 않으면 비교를 반복한다.

각 비교에서 탐색할 서브트리 하나를 제외한 나머지 부분을 버릴 수 있다. 다만 트리가 한쪽으로 치우치면 한 단계마다 노드 하나만 제외하므로 비교 횟수가 많아진다.

비교 횟수

키 kᵢ가 저장된 노드의 레벨이 Lᵢ라면 그 키에 도달하기 위한 비교 횟수 Cᵢ는 Lᵢ+1이다. 루트에서는 한 번, 레벨 1에서는 두 번 비교한다. 동일한 네 키를 저장해도 한쪽으로 늘어선 트리는 전체 비교 횟수가 1+2+3+4=10이지만 더 균형 잡힌 트리는 1+2+2+3=8이 될 수 있다.

검색 확률을 고려한 기대 비교 횟수

키 kᵢ가 검색 대상이 될 확률을 Sᵢ라고 하면 ΣSᵢ=1이고 기대 비교 횟수는 ΣSᵢCᵢ이다. 검색 확률이 높은 키를 루트에 가깝게 배치하면 평균 비교 횟수를 줄일 수 있다.

강의에서 A:0.5, B:0.3, C:0.1, D:0.1일 때 검색 확률이 가장 높은 A가 루트에 가까운 트리의 기대 비교 횟수는 1.8이다. 다른 배치에서는 2.2가 되므로 단순한 높이뿐 아니라 키별 검색 확률도 효율에 영향을 준다.

허프만 코딩과 트리

강의에서는 데이터 압축에서 사용하는 허프만 코딩을 참고 사례로 제시한다. 문자 빈도를 바탕으로 트리를 구성하고 빈도가 높은 문자에 짧은 비트열을 배정한다. A, B, C, D, E의 빈도가 각각 17, 12, 12, 27, 32인 예에서 코드는 A=00, B=010, C=011, D=10, E=11로 구성된다.

10. 신장 트리와 최소 신장 트리

신장 트리

그래프 G의 모든 꼭지점을 연결하면서 사이클이 존재하지 않는 부분 그래프를 신장 트리(spanning tree)라고 한다. 즉 신장 트리는 원래 그래프의 모든 꼭지점을 포함하는 트리이다. 변은 원래 그래프에서 선택하되 모든 꼭지점을 연결하는 데 필요한 n-1개만 남긴다.

최소 신장 트리

가중 그래프에서 선택한 모든 변의 가중치 합을 총 가중치라고 한다. 여러 신장 트리 중 총 가중치가 가장 작은 것을 최소 신장 트리(minimum spanning tree, MST)라고 한다.

최소 신장 트리는 컴퓨터·통신 네트워크, 교통망, 상수도망, 전력망처럼 여러 지점을 최소 비용으로 연결하는 설계에 활용할 수 있다. 꼭지점 수가 커지면 가능한 신장 트리의 수가 빠르게 증가하며, 완전 그래프 Kₙ의 신장 트리는 n^(n-2)개이므로 모든 경우를 직접 비교하기보다 효율적인 알고리즘이 필요하다.

최소 신장 트리는 모든 꼭지점을 연결하지만 원래 그래프의 모든 변을 포함하지는 않는다. 사이클을 없애고 총 가중치가 최소가 되도록 정확히 트리 구조를 선택한다.

11. Kruskal 알고리즘

변을 중심으로 선택하는 방법

Kruskal 알고리즘은 가중치가 작은 변부터 전체적으로 검토하는 변 중심 알고리즘이다.

1. 그래프의 모든 변을 가중치의 오름차순으로 정렬한다.
2. 가중치가 가장 작은 변부터 차례로 살펴본다.
3. 현재 선택한 변들과 사이클을 만들지 않는다면 그 변을 트리에 추가한다.
4. 모든 꼭지점이 연결되어 변이 n-1개가 될 때까지 반복한다.

강의 슬라이드의 간단한 절차에는 작은 변을 차례로 추가한다고 제시되어 있다. 이때 결과가 트리여야 하므로 이미 선택한 변과 사이클을 만드는 변은 건너뛰어야 한다. 처음에는 서로 떨어진 여러 작은 트리로 시작할 수 있고, 선택이 진행되면서 이들이 하나의 신장 트리로 합쳐진다.

Kruskal 알고리즘의 판단 기준은 “현재 전체 그래프에서 가장 작은 변인가?”와 “그 변을 넣어도 사이클이 생기지 않는가?”이다.

12. Prim 알고리즘

꼭지점을 중심으로 확장하는 방법

Prim 알고리즘은 하나의 꼭지점에서 시작하여 현재 트리에 인접한 꼭지점을 하나씩 붙이는 꼭지점 중심 알고리즘이다.

1. 임의의 꼭지점 하나를 트리에 추가한다.
2. 현재 트리에 속한 꼭지점과 아직 속하지 않은 꼭지점을 연결하는 변 중 가중치가 가장 작은 변을 선택한다.
3. 그 변과 새로운 꼭지점을 트리에 추가한다.
4. 모든 꼭지점이 연결될 때까지 반복한다.

Prim 알고리즘은 선택 과정 내내 하나의 연결된 트리를 유지한다. 이미 트리에 들어 있는 두 꼭지점을 잇는 변은 새로운 꼭지점을 추가하지 않으므로 선택 대상이 아니다. 강의 예에서는 G→F→E→B→A→D→C와 같이 트리의 꼭지점 집합을 확장한다.

Kruskal과 Prim의 비교

구분	Kruskal 알고리즘	Prim 알고리즘
중심 대상	변 중심	꼭지점 중심
시작 방식	모든 변을 가중치 순으로 검토	임의의 꼭지점 하나에서 시작
선택 기준	사이클을 만들지 않는 가장 작은 변	현재 트리와 외부 꼭지점을 잇는 가장 작은 변
중간 형태	여러 트리의 포리스트가 생길 수 있음	항상 하나의 연결된 트리를 유지
결과	모든 꼭지점을 잇는 최소 신장 트리

13. 핵심 개념 정리

• 트리는 사이클이 없는 단순 연결 그래프이고, 포리스트는 하나 이상의 트리로 이루어진 그래프이다.
• 노드의 차수는 자식 수, 트리의 차수는 노드 차수의 최댓값, 레벨은 루트에서 노드까지의 경로 길이, 높이는 레벨의 최댓값이다.
• 트리는 중첩된 집합, 중첩된 괄호, 결각으로 표현할 수 있으며 구조가 같고 데이터만 다르면 닮은 트리이다.
• n개 꼭지점의 연결 그래프는 트리일 필요충분조건이 변의 수가 n-1개인 것이다.
• 높이 h인 이진 트리의 최대 노드 수는 2^(h+1)-1이고, n개 노드의 최소 높이는 ⌊log₂n⌋이다.
• 완전 이진 트리는 마지막 레벨을 왼쪽부터 채우고, 포화 이진 트리는 모든 레벨을 가득 채운다.
• 이진 탐색 트리는 왼쪽 서브트리의 키가 작고 오른쪽 서브트리의 키가 크며, 삽입 순서와 검색 확률이 효율에 영향을 준다.
• 신장 트리는 원래 그래프의 모든 꼭지점을 포함하는 트리이고, 최소 신장 트리는 총 가중치가 가장 작은 신장 트리이다.
• Kruskal은 변 중심, Prim은 꼭지점 중심으로 최소 신장 트리를 구한다.

트리는 사이클 없는 연결 구조라는 기본 성질에서 출발한다. 이진 트리에서는 높이와 노드 수, 이진 탐색 트리에서는 키의 배치와 비교 횟수, 최소 신장 트리에서는 연결을 유지하면서 총 가중치를 줄이는 선택 기준을 중심으로 문제를 풀어야 한다.

14. 예상문제 20선

1. 트리의 정의로 옳은 것은?

① 사이클이 있는 단순 연결 그래프 ② 사이클이 없는 비연결 그래프만을 뜻함 ③ 모든 꼭지점의 차수가 같은 그래프 ④ 사이클이 없는 단순 연결 그래프

정답입니다.

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

정답 및 해설 보기

정답: ④
트리는 모든 꼭지점이 연결되어 있으면서 사이클이 없는 단순 그래프이다.

2. 한 개 이상의 서로 분리된 트리로 구성된 그래프는?

① 완전 그래프 ② 포리스트 ③ 순환 그래프 ④ 포화 이진 트리

정답입니다.

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

정답 및 해설 보기

정답: ②
서로 연결되지 않은 하나 이상의 트리를 함께 모은 그래프를 포리스트라고 한다.

3. 노드 N의 차수는 무엇으로 결정되는가?

① N이 가진 자식 노드의 수 ② 루트에서 N까지 경로의 길이 ③ N의 형제 노드 수 ④ 트리 전체의 리프 노드 수

정답입니다.

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

정답 및 해설 보기

정답: ①
노드의 차수는 그 노드에 직접 연결된 자식의 수이며, 트리의 차수는 노드 차수의 최댓값이다.

4. 트리의 무게에 대한 설명으로 옳은 것은?

① 모든 변의 가중치 합이다. ② 트리의 내부 노드 개수이다. ③ 리프 노드의 개수이다. ④ 트리의 높이에 1을 더한 값이다.

정답입니다.

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

정답 및 해설 보기

정답: ③
강의에서 트리의 무게는 자식이 없는 리프 노드들의 개수로 정의한다.

5. 노드의 데이터는 다르지만 부모·자식 연결 구조가 같은 두 트리를 무엇이라 하는가?

① 역 트리 ② 포리스트 ③ 닮은 트리 ④ 최소 신장 트리

정답입니다.

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

정답 및 해설 보기

정답: ③
노드에 저장된 값과 관계없이 구조가 동일하면 두 트리는 서로 닮았다고 한다.

6. 꼭지점이 12개인 트리의 변 개수는?

① 11개 ② 12개 ③ 13개 ④ 24개

정답입니다.

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

정답 및 해설 보기

정답: ①
n개 꼭지점을 가진 트리의 변은 정확히 n-1개이므로 11개이다.

7. 이진 트리와 일반 루트 트리의 차이로 옳지 않은 것은?

① 이진 트리는 공집합일 수 있다. ② 이진 트리는 왼쪽과 오른쪽 서브트리를 구분한다. ③ 이진 트리의 각 노드는 최대 두 자식을 갖는다. ④ 이진 트리는 반드시 모든 노드가 두 자식을 가져야 한다.

정답입니다.

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

정답 및 해설 보기

정답: ④
이진 트리는 각 노드의 자식이 최대 두 개라는 뜻이며 자식이 0개나 1개일 수도 있다.

8. 높이가 4인 이진 트리가 가질 수 있는 최대 노드 수는?

① 15개 ② 31개 ③ 32개 ④ 63개

정답입니다.

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

정답 및 해설 보기

정답: ②
최대 노드 수는 2^(h+1)-1이므로 2⁵-1=31이다.

9. 완전 이진 트리의 설명으로 옳은 것은?

① 마지막 레벨 전까지 가득 차고 마지막 레벨은 왼쪽부터 채운다. ② 모든 노드가 반드시 왼쪽 자식 하나만 갖는다. ③ 마지막 레벨은 오른쪽부터 채워야 한다. ④ 같은 노드 수의 트리 중 높이가 가장 크다.

정답입니다.

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

정답 및 해설 보기

정답: ①
완전 이진 트리는 마지막 레벨만 덜 찰 수 있으며 그 노드들도 왼쪽부터 연속해서 배치된다.

10. 노드가 14개인 이진 트리의 최소 높이는?

① 2 ② 4 ③ 13 ④ 3

정답입니다.

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

정답 및 해설 보기

정답: ④
⌊log₂14⌋=3이며 높이 3인 이진 트리는 최대 15개 노드를 담을 수 있다.

11. 높이가 5이고 노드가 60개인 포화 이진 트리가 존재하지 않는 이유는?

① 포화 이진 트리는 높이가 5일 수 없기 때문이다. ② 높이 5에서는 최대 31개만 가능하기 때문이다. ③ 높이 5인 포화 이진 트리는 정확히 63개 노드를 가져야 하기 때문이다. ④ 포화 이진 트리의 노드 수는 항상 짝수이기 때문이다.

정답입니다.

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

정답 및 해설 보기

정답: ③
모든 레벨이 가득 찬 높이 5의 포화 이진 트리는 2⁶-1=63개 노드를 갖는다.

12. 이진 탐색 트리에서 임의의 노드 키가 20일 때 옳은 것은?

① 왼쪽 서브트리의 모든 키는 20보다 커야 한다. ② 왼쪽 서브트리는 20보다 작고 오른쪽 서브트리는 20보다 큰 키를 갖는다. ③ 양쪽 서브트리의 키는 모두 20과 같아야 한다. ④ 오른쪽 서브트리의 모든 키는 20보다 작아야 한다.

정답입니다.

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

정답 및 해설 보기

정답: ②
이진 탐색 트리는 각 노드를 기준으로 작은 키를 왼쪽, 큰 키를 오른쪽 서브트리에 둔다.

13. 키 1,2,3,4,5를 차례로 빈 이진 탐색 트리에 삽입하면 나타나기 쉬운 형태는?

① 모든 레벨이 가득 찬 포화 이진 트리 ② 루트가 3인 완전 이진 트리 ③ 왼쪽으로만 이어지는 경사 트리 ④ 오른쪽으로 이어지는 경사 이진 트리

정답입니다.

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

정답 및 해설 보기

정답: ④
새 키가 항상 기존 키보다 크므로 매번 오른쪽 자식 방향으로 내려가 삽입된다.

14. 이진 탐색 트리에서 찾을 키가 현재 노드 키보다 작을 때의 동작은?

① 왼쪽 자식을 다음 탐색 노드로 설정한다. ② 오른쪽 자식을 다음 탐색 노드로 설정한다. ③ 무조건 루트로 돌아간다. ④ 현재 노드를 삭제한다.

정답입니다.

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

정답 및 해설 보기

정답: ①
작은 키는 왼쪽 서브트리에만 존재할 수 있으므로 왼쪽 자식 방향으로 탐색한다.

15. 레벨이 3인 노드의 키를 찾는 데 필요한 비교 횟수는?

① 2회 ② 4회 ③ 3회 ④ 8회

정답입니다.

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

정답 및 해설 보기

정답: ②
키 비교 횟수는 노드의 레벨에 1을 더한 값이므로 3+1=4회이다.

16. 신장 트리에 대한 설명으로 옳은 것은?

① 원래 그래프의 모든 변을 반드시 포함한다. ② 원래 그래프의 일부 꼭지점만 포함한다. ③ 원래 그래프의 모든 꼭지점을 포함하고 사이클이 없는 연결 부분 그래프이다. ④ 반드시 원래 그래프보다 많은 변을 가진다.

정답입니다.

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

정답 및 해설 보기

정답: ③
신장 트리는 원래 그래프의 모든 꼭지점을 연결하되 사이클 없이 트리 형태로 만든 부분 그래프이다.

17. 최소 신장 트리의 정의로 옳은 것은?

① 신장 트리 중 선택한 변의 총 가중치가 가장 작은 트리 ② 꼭지점의 수가 가장 적은 부분 그래프 ③ 사이클의 수가 가장 많은 신장 그래프 ④ 가장 큰 가중치의 변만 선택한 트리

정답입니다.

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

정답 및 해설 보기

정답: ①
최소 신장 트리는 모든 꼭지점을 연결하는 신장 트리 가운데 총 가중치가 최소인 트리이다.

18. Kruskal 알고리즘의 핵심 절차는?

① 임의의 꼭지점에서 깊이 우선 탐색만 수행한다. ② 가장 큰 가중치의 변부터 모두 추가한다. ③ 현재 트리에 인접한 꼭지점만 검토한다. ④ 가중치가 작은 변부터 사이클을 만들지 않도록 선택한다.

정답입니다.

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

정답 및 해설 보기

정답: ④
Kruskal은 모든 변을 가중치 순으로 검토하고 사이클을 만들지 않는 작은 변을 선택하는 변 중심 방법이다.

19. Prim 알고리즘에 대한 설명으로 옳은 것은?

① 중간 과정에서 여러 개의 분리된 트리만 유지한다. ② 현재 트리와 외부 꼭지점을 잇는 가장 작은 변으로 트리를 확장한다. ③ 모든 변을 먼저 내림차순으로 정렬해야 한다. ④ 사이클이 생길 때까지 변을 추가한다.

정답입니다.

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

정답 및 해설 보기

정답: ②
Prim은 임의의 꼭지점에서 시작해 현재 트리와 연결되는 가장 저렴한 새 꼭지점을 하나씩 추가한다.

20. Kruskal 알고리즘과 Prim 알고리즘의 비교로 옳은 것은?

① 두 알고리즘 모두 최장 경로를 구한다. ② Kruskal은 꼭지점 중심이고 Prim은 변 중심이다. ③ Kruskal은 변 중심, Prim은 꼭지점 중심으로 최소 신장 트리를 구한다. ④ 두 알고리즘 모두 가중치와 무관하게 변을 선택한다.

정답입니다.

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

정답 및 해설 보기

정답: ③
두 알고리즘의 목표는 같지만 Kruskal은 변의 가중치 순서, Prim은 현재 트리에서 새 꼭지점으로 확장하는 선택을 중심으로 한다.