자료구조 문제 정리 (3) 트리

1. 이진트리

이진트리(BST)
부모를 중심으로 좌측에는 모두 부모보다 작은 데이터가
우측에는 모두 부모보다 큰 데이터가 위치한다

(데이터가 위에서부터 들어와서 루트노드를 거쳐서 위치를 찾아감)

https://www.youtube.com/watch?v=Smmz7MT4oxM

 

• 일반 트리와 다르게 공집합을 허용한다.
• 각 노드는 최대 2개의 자식 노드를 갖는다.
• 어떤 노드에서 루트 노드에 이르는 경로는 유일하다.
• n개의 노드를 가진 이진 트리는 n-1개의 간선을 갖는다.
• 노드(node)가 11개 있는 트리의 간선(edge) 개수 = 10개

이진트리와 일반트리의 차이점

• 이진트리의 모든 노드는 차수가 2 이하이다.
• 일반트리는 자식 노드의 개수에 제한이 없다.
• 일반 트리와는 달리 이진트리는 노드를 하나도 가지고 있지 않을 수도 잇다.
• 서브트리 간에 순서가 존재한다는 점도 다른점이다. 따라서 왼쪽 서브트리와 오른쪽 서브트리를 구별한다. 

이진트리의 성질

• n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선을 갖는다.
• 이진트리의 레벨 i에서 최대 노드 수는 2^i-1 이다
• 깊이가 k인 이진트리의 경우 최소 k개의 노드를 가지며 최대 2^k-1개의 노드를 갖는다.
• k개의 노드를 가지는 이진트리의 깊이는 최대 k이거나 최소 log2(k+1)이다.

 

(1)

깊이가 k인 이진트리가 가질 수 있는 최대 노드 수를 A라고 하고, 최소 노드 수를 B라고 할 때, A-B의 값은? 

(단, 루트노드의 레벨은 1로 한다)

최대 노드 수 : 2^k-1  

최소 노드 수 : k

A-B = 2^k-k-1

 

 

(2)

300개의 노드로 이진 트리를 생성하고자 할 때, 생성 가능한 이진 트리의 최대 높이와 최소 높이로 모두 옳은 것은?

(단, 1개의 노드로 생성된 이진트리의 높이는 1이다)

• k개의 노드를 가지는 이진트리의 깊이는 최대 k이거나 최소 log2(k+1)이다.
• 최대 높이 : 300
• 최소 높이 : log2 301 => 값이 실수로 나올 경우 올린다. 즉 8.xx이고, 이를 올리면 9가 된다. 

 

 

(3)

노드의 수가 60개인 이진 트리의 최대 높이에서 최소 높이를 뺀 값은?

최대 높이 : 60

최소 높이 : log2 60 => 6

따라서 60-6=54

 

 

(4) 배열을 이용하는 완전 이진트리

 

배열을 이용하는 방법은 주로 포화이진트리나 완전이진트리의 경우 많이 쓰이는 방법이지만

그 외의 이진트리도 저장이 불가능한 것은 아니다.

포화이진트리나 완전이진트리는 순차적인 배열 표현에서 기억공간의 낭비가 없다.

배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다.

• 노드 k의 부모 노드 인덱스 = [k/2]
• 노드 k의 왼쪽 자식 노드 인덱스 = 2k
• 노드 k의 오른쪽 자식 노드 인덱스 = 2k+1
• 형제 노드의 관계는 k가 짝수인 경우 k+1이지만, k가 홀수인 경우는 k+1이 아니다

 

[트리 순회 문제]

전위 순회는 루트 노드가 맨 앞,

중위 순회는 루트 노드가 중간

후위 순위는 루트 노드가 맨 뒤에 온다.

 

(5)

전위 순회할 경우 방문 순서 : 

A -> B -> D -> E -> G -> C -> F -> H

중위 순회할 경우 방문 순서 : 

D -> G -> E -> B -> A -> H -> F-> C
후위 순회할 경우 방문 순서 : 

D -> G -> E -> B -> H -> F -> C -> A

 

 

(6)

다음과 같은 수식을 이진트리로 표현하였을 때 완성된 이진트리의 깊이(depth)는 얼마인가?

(단, 근노드만 존재하는 이진트리의 깊이는 1이다)

((a+b)+c)+d

 

이진트리는 컴퓨터 응용을 위해 많이 활용되는데, 수식을 이진트리로 표현하는 것을 수식 이진트리라 한다.

각 부노드에는 연산자, 단말노드에는 피연산자를 위치시킨다.

근노드는 1이므로 깊이는 5이다 

 

(7)

이진 트리의 내부 경로 길이와 외부 경로 길이는?

 

내부경로길이는 루트부터 그 노드까지의 간선의 개수를 의미한다.

A의 내부 경로 길이는 0이다.

B와 C의 내부 경로 길이는 각 1이다.

D, E, F의 내부 경로 길이는 각 2이다.이들의 합은 8이다.

 

외부 경로 길이는 그림과 같이 가장 외부에 존재하는 노드들(사각형 노드)에 대해 루트부터 각 외부 노드까지의

간선의 개수를 이용하여 그릴 수 있다.

3+3+3+3+3+3+2=20개이다.

 

 

[트리 노드 삽입]

(8)

6개의 데이터를 비어 있는 트리에 차례로 삽입하여 이진 탐색트리로 만들 때

만들어진 이진 탐색트리의 높이가 가장 낮은 것은? 

1. 1,2,3,4,5,6
2. 4,2,5,6,1,3
3. 3,1,4,2,6,5
4. 2,1,3,4,6,5

균형적일 경우 O(logn), 불균형적일 경우 O(n)의 탐색 시간복잡도를 갖는다.

균형적인 이진탐색트리는 첫번째 데이터가 전체 데이터의 범위에서 중간값을 갖는다.

불균형적인 이진탐색트리는 첫번째 데이터가 전체 데이터의 범위에서 작거나 큰 쪽의 값을 갖는다.

1. 1,2,3,4,5,6
2. 4,2,5,6,1,3
3. 3,1,4,2,6,5
4. 2,1,3,4,6,5

중간값은 3, 4

답 : 2번

 

(9)

다음 정수를 왼쪽부터 순서대로 삽입하여 이진탐색트리를 구성했을 때, 단말노드를 모두 나열한 것은?

44, 36, 62, 3, 16, 51, 75, 68, 49, 85, 57

 

답 : 16, 49, 57, 68, 85

 

(10)

초기에 빈 Binary Search Tree를 생성하고, 입력되는 수는 다음과 같은 순서로 된다고 가정한다.

입력되는 값을 이용하여 Binary Search Tree를 만들고 난 후 Inorder Traversal을 했을 때의

방문하는 순서는?

7, 5, 1, 8, 3, 6, 0, 2

 

Inorder Traversal = 중위 순회

* 전위 순회(Pre-order) 중위 순회(In-order) 후위 순회(Post-order).

 

답은 01235678

 

(11)

다음 이진검색트리에서 28을 삭제한 후, 28의 오른쪽 서브트리에 있는 가장 작은 원소로 28을 대치하여만들어지는 이진탐색트리에서 41의 왼쪽 자식 노드는?

28은 왼쪽 서브트리(왼쪽 자노드)와 오른쪽 서브트리를 갖는 부노드이다.

이를 삭제할 경우 왼쪽 서브트리에서 가장 큰 값 또는 오른쪽 서브트리에서 가장 작은 값을 28 위치에 대신하면 된다.

이들 값은 모두 28과 가장 가까운 값이다.

이 문제에서는 오른쪽 서브트리에서 가장 작은 원소(즉 오른쪽 서브트리에서 가장 28과 가까운 값) 30을 이용한다.

답 : 37

 

(12)

최대/최소 힙트리 : 

• 완전 이진트리이다 : 루트노드부터 시작하여 왼쪽 자식노드, 오른쪽 자식노드 순서대로 데이터가 차례로 삽입되는 트리이다
• 루트에 가장 최대 값을 가지고 있다 = 최대 힙트리
• 루트에 가장 최소 값을 가지고 있다 = 최소 힙트리

다음과 같은 키 값을 가지는 원소들을 공백 힙에 차례대로 삽입하여 최대 힙을 생성한 다음,

삭제 연산을 한 번 수행한 결과는?

4, 16, 57, 9, 32, 45, 20, 19

 

공백 힙을 사용하여 값을 삽입할 때마다 루트에 최대값이 오도록 구성된다.

각 자노드와 부노드 간의 관계에서 부노드는 자노드보다 작지 않아야 한다.

*노드는 왼쪽부터 삽입한다

최대 힙에서의 삭제는 루트를 삭제하고 그 자리에 가장 마지막 노드를 대체한 후, 새로운 최대힙으로 구성하면 된다