이산수학 - 8. 트리

1. 트리의 개념

2. 이진트리

3. 이진 탐색 트리

4. 트리의 활용

 

 

 

1. 트리의 개념

트리: 비선형적이며 계층적인 구조표현으로 다음 특징을 갖는다.

• 루트는 반드시 하나 있음.
• 트리를 구성하는 꼭짓점 u,w간에 u에서 w로 가는 단순경로가 있음

서브트리: 트리를 구성하는 꼭짓점 v를 루트로 하는 트리

 

노드: 그래프 T를 구성하는 꼭짓점

루트: 그래프 T의 시작 노드, 그래프 T의 가장 높은 곳에 위치

부모 노드: 어떤 노드의 한 단계 상위 노드

자식 노드: 어떤 노드의 한 단계 하위 노드

형제 노드: 같은 단계에 있으면서 부모가 같은 노드들

잎 노드: 자식 노드가 없는 노드

중간 노드: 루트 노드나 잎 노드가 아닌 노드

조상 노드: 루트 노드에서 어떤 노드에 이르는 경로에 포함된 모든 노드

자손 노드: 어떤 노드에서 잎 노드에 이르는 경로에 포함된 모든 노드

차수: 어떤 노드에 포함된 자식 노드의 개수

레벨: 루트 노드를 0으로 시작하여, 자식노드로 내려갈때마다 하나씩 증가하는 단계

트리의 높이, 깊이: 트리가 가지는 최대 레벨

숲: 루트 노드를 제거하여 얻는 서브 트리의 집합

 

노드와 변에 대한 정리: 트리에서 노드의 개수를 v , 변의 개수를 e라고 하면 e=v-1 이다.

 

트리에 대한 정리: n개의 꼭짓점을 갖는 연결 그래프 T에 대한 다음은 동치다

1) T는 트리다

2) T의 변의 수는 n-1개다

3) T에서 변 하나를 제거하면 연결 그래프가 아니다.

4) T에 속하는 서로 다른 꼭짓점 w,v에 대해 w에서 v로 가는 유일한 경로가 존재한다.

 

트리와 그래프의 차이

sexycoder.tistory.com/79

그래프와 트리의 차이점

 

 

 

2. 이진 트리

이진 트리: 트리를 구성하는 부모 노드가 갖는 자식 노드의 수가 최대 2개인 트리

완전 이진 트리: 높이가 h일때 레벨 1부터 h-1까지 모든 노드가 두 개씩 채워져 있고, (h-2까지 자식 노드가 두개다.) 레벨 h는 왼쪽부터 노드가 채워져 있는 트리

포화 이진 트리: 높이가 h 일때 레벨 1에서 h까지 모든 노드가 두 개씩 채워져 있는 트리

편향 이진 트리: 왼쪽이나 오른쪽 서브트리만 가지는 트리

이진 트리의 최대 노드 수: 레벨 k에서 가질 수 있는 최대 노드 수 2^k개

 

전위 순회: 루트 → 왼쪽 노드 → 오른쪽 노드

중위 순회: 왼쪽 노드 → 루트 → 오른쪽 노드

후위 순회: 왼쪽 노드 → 오른쪽 노드 → 루트

 

식 (x/y)+(w-z)*v 을 이진트리로 표현하면 

 

 

 

 

3. 이진 탐색 트리 (BST: Binary Search Tree)

이진 탐색 트리: 노드가 가지는 데이터의 크기에 따라 노드의 위치를 탐색할 수 있는 트리

• 트리에서 탐색되는 모든 원소는 서로다른 유일키를 갖는다.
• 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.
• 오른쪽 서브 트리에 있는 원소들의 키들은 그 루트의 키보다 크다.

 

 

4. 트리의 활용

신장 트리(Spanning Tree): 그래프 G의 꼭짓점을 모두 노드로 포함하는 트리 T

최소 신장 트리(Minimum Spanning Tree): 그래프 G의 꼭짓점을 모두 노드로 포함하면서 비용을 최소로 하는 트리 T

 

프림 알고리즘: 그래프 G의 변 중 가중치가 가장 낮은 변에서부터 연결시켜 트리를 만드는 알고리즘

1) 가중치가 가장 낮은 변을 선택

2) 연결된 꼭짓점들과 연결된 모든 변들 중 가중치가 가장 작은 변을 선택

3) 가중치가 같은 변은 임의로 선택

4) 선택된 변에 의해 순환이 형성되는 경우 선택하지 않음

5) n개의 꼭짓점에 대하여 n-1개의 변이 연결되면 종료

 

크루스칼 알고리즘: 그래프 G의 변 중 비용이 가장 낮은 변들로 트리를 구성하는 알고리즘

1) 가중치가 가장 작은 변을 차례로 선택하여 노드들을 연결

2) 가중치가 같은 변은 임의로 선택

3) 선택된 변에 의해 회로가 형성되는 경우는 선택하지 않음

4) n개의 꼭짓점에 대하여 n-1개의 변이 연결되면 종료

 

허프만 코드: 발생 빈도가 높은 문자에는 적은 비트를 할당하고 발생 빈도가 낮은 문자에는 많은 비트를 할당하기 위한 알고리즘

1) 발행빈도가 가장 낮은 두 문자를 선택하여 하나의 이진 트리로 연결

1. 왼쪽 노드에는 빈도수가 낮은 문자, 오른쪽에는 빈도가 높은 문자가 오도록함.
2. 그 두 문자 노드의 루트는 두 문자의 빈도의 합으로 함
3. 문자들을 이진 트리로 연결하는 것을 최우선적으로 작업하고, 그 후에 이진트리들을 연결하도록 함

2) 1과정을 모든 문자가 하나의 이진 트리로 묶일 때까지 반복

3) 생성된 이진 트리의 왼쪽 노드에는 0, 오른쪽 노드에는 1을 부여하여 루트부터 해당 문자까지의 0또는 1을 순서대로 나열한 것이 해당 문자의 허프만 코드가 됨.