이산 수학 - 16 트리 활용

가계도, 조직도, 토너먼트 대진표 등 다양한 분야에 응용되는 트리

-> 트리 구조를 이용하여 새로운 분자구조식설계 가능

 

압축 저장 방법

1. 손실 압축 : 사람의 시각, 청각 능력이 구별하지 못하는 영역을 제거해 전체 파일 크기를 줄임

2. 무손실 압축 : 원래 정보를 그대로 보존하여 압축을 풀었을 때 원래의 파일로 되돌릴수 있는 방식(허프만 코드)

 

허프만 코드

- 무손실 압축에 쓰이는 알고리즘 일종

- 파일에 등작하는 문자의 빈도수에 따라 각 문자에 다른 길이의 부호를 대응 시켜서 파일을 압축

- 트리 구조는 바로 이러한 허프만 코드를 정의하는 알고리즘에 사용

 

 

이진 트리의 순회와 탐색

1. 이진트리의 순회

2. 이진 탐색 트리

 

순회 Traversal

- 트리에 있는 모든 노드를 (한 번씩) 방문하여 노드가 가지고 있는 데이터를 처리하는 체계적인 방법

- (이진) 트리의 계층적인 구조를 이용하여 순회하는 방법을 정의

- 이진 트리 순회의 규칙

 -> 루트 노드에서 시작

 -> 형제 노드 중 왼쪽 노드를 먼저 탐색

- 순회의 종류

 -> 전위 순회, 중위 순회, 후위 순회

 

전위 순회

- 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 순회

- A -> B -> D -> E -> J -> K -> C -> F -> M

중위 순회

- 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 순회

- D -> B -> J ->E -> K -> A -> F -> M -> C

 

후위 순회

- 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순서로 순회

- D -> J  -> K -> E -> B ->  M -> F -> C -> A

 

 

이진 트리 순회를 이용한 폴더 용량 계산

 

 

전위 순회

- 0.2M(내컴퓨터) + 0.1 M(C:\) + 15M(내문서) + 2M(프로그램) + 200M(자바) + 100M(파이썬) + 0.3M(D:\) + 50M(그림) + 3M(음악) + 70M(팝송) + 90M(클래식) = 530.6M

 

중위 순회

- 내문서 + C\ + 자바 + 프로그램 + 파이썬 + 내커퓨터 + 그림 + DL\ + 팝송 + 음악 + 클래식 = 530.6M

 

후위 순회

- 내문서 + 자바 + 파이썬 + 프로그램 + C:\ + 그림 + 팝송 + 클래식 + 음악 + D:\ + 내컴퓨터 = 530.6M

 

 

이진 탐색 트리 Binary Search Tree

- 노드에 저장된 데이터의 내용에 대한 크기 기준을 정하고 이 기준에 따라 노드의 위치를 정해놓은 이진 트리

1. 모든 노드는 서로 다른 유일한 키를 갖는다.

2. 왼쪽 서브트리에 있는 모든 노드는 루트 노드 보다 작은 키를 갖는다.

3. 오른쪽 서브 트리에 있는 모든 노드는 루트 노드보다 큰 키를 가진다.

4. 왼쪽 서브 트리와 오른쪽 서브트리도 이진 탐색 트리다.

 

 

이진 탐색 트리에서 22를 검색하는 과정

1. 루트 노드는 15로 22보다 작다 -> 오른쪽 자식 노드

2. 21은 22보다 작다 -> 오른쪽 자식 노드

3. 24는 22보다 크다 ->왼쪽 자식노드

 

 

이진 탐색 트리의 삽입

 

이진 탐색 트리의 삭제 1

- 삭제 할 노드가 리프 노드인 경우

 

 

 

이진 탐색 트리의 삭제 2

- 삭제 할 노드가 1개의 자식 노드를 가지는 경우

- 21을 지우는 경우 노드 24를 21자리로 옮김

 

 

이진 탐색 트리의 삭제 3

- 삭제할 노드가 2개의 자식 노드를 가지는 경우

- 왼쪽 서브트리 노드 중 최대 값을 가지는 노드를 이동시키거나 오른쪽 서브트리의 노드 중 최소키를 가지는 노드를 이동

 

이진 탐색 트리 생성

- 18, 10, 25, 20, 14, 8, 23, 17, 29에 대한 이진 탐색 트리

 

생성 트리

1. 생성 트리의 개념

2. 프림 알고리즘

3. 크루스칼 알고리즘

 

 

생성 트리 Spanning Tree

- 그래프의 모든 노드를 포함하는 트리 -> 그래프의 생성 트리는 여러 개가 될 수 있음

그래프

위 그래프에서 아래의 생성 트리를 만들 수 있음

 

 생성 트리 예시

 

 

 

 

최소 생성 트리 Minimal Spanning Tree

- 가중 그래프에 대해서 연결선의 가중치의 합을 최소로 하는 생성 트리

- 네트워크나 도로망 설계 시 비용을 최소로 하거나 효율성을 최대로 하는 경로를 고려할 때 유용

- 최소 생성 트리를 구하는 알고리즘으로 프림 알고리즘, 크루스칼 알고리즘

 

 

프림 알고리즘

1. 임의의 시작 노드 선택

2. 가중치가 가장 작은 연결선을 선택

3. 1에서 선택된 연결선에 의해 연결된 노드와 연결된 모든 연결선 중 가중치가 가장 작은 연결선 선택. 가중치가 같은 연결선이 있으면 임의로 하나를 선택한다

4. 선택된 연결선에 의해 사이클이 형성되면 선택 하지 않는다.

5. 그래프에 포함된 노드 개수가 n일 때, n - 1개의 연결선이 선택되면 종료한다.

 

 

프림 알고리즘

- 노드 A에서 시작

 

 

 

 

크루스칼 알고리즘

1. 가중치가 가장 작은 연결선을 차례로 선택한다. 가중치가 같은 연결선은 모두 선택한다.

2. 선택된 연결선에 의해 사이클이 형성되면 선택하지 않는다.

3. 그래프에 포함된 노드의 개수가 n일 때, n - 1개의 연결선이 선택되면 종료한다.

 

 

크루스칼 알고리즘

- 노드 B에서 시작

 

 

 

아스키 코드

- 문자를 8비트 숫자로 변환하는 표

 

만약 자주 나오는 문자에 더 적은 비트를 할당한다면?

-> 전체 문자 비트 수를 줄일 수 있을텐대 -> 허프만 알고리즘

 

 

허프만 알고리즘

- 발생 빈도가 높은 문자는 적은 비트를 할당하고, 발생 빈도가 낮은 문자에 많은 비트를 할당하야 파일 크기를 줄이는 알고리즘

1. 발생 빈도가 가장 낮은 두 문자를 선택하여 하나의 이진 트리 생성

  -> 왼쪽 노드에 빈도 수가 낮은 문자, 오른쪽 노드에 빈도가 높은 문자

  -> 빈도수가 같으면 사전 순서로

  -> 두 문자의 빈도 합을 그 문자들의 부모 노드로

2. 1을 반복하여 하나의 이진 트리를 생성

3. 생성된 이진 트리의 왼쪽 노드에는 0, 오른쪽 노드에는 1을 부여

4. 루트 노드에서 해당 문자까지의 0 또는 1을 순서대로 나열

 

허프만 알고리즘 예시

1. 가장 빈도수가 낮은 o, z 선택

 - 사전의 순서대로 o를 왼쪽, z를 오른쪽 놓고

 - 두 빈도의 합인 4를 부모 노드로 설정

 

2. 가장 빈도수가 낮은 u(5)와 4

 - 4가 낮으므로 왼쪽 노드, u는 크므로 오른쪽노드

 - 합인 9가 부모 노드

 

3. 다음 가장 빈도수가 낮은 수가 8로 e, j가 존재

- 두 문자는 별도의 자식 노드가 되어

 - 두 수의 합인 16이 부모 노드가 됨

 

 

4. 가장 빈도수가 낮은 문자 b와 ozu

 - ozu가 9 낮으므로 왼쪽, b는 15라 크므로 오른쪽

 - 두 수의 합은 24가 부모 노드가 됨

 

 5. 다음 빈도수 낮은 문자는 ej와 s

 - ej는 16으로 왼쪽, s는 17로 우측

 - 두 수의 합인 33이 부모노드가 됨

6. 다음 빈도수가 낮은 문자 g와 ozub

 - g는 23 왼쪽, ozub는 24 오른쪽

 - 합한 수 47이 부모 노드

7. 다음 빈도수가 낮은 문자 i와 ejs

 - i가 30으로 왼쪽, ejs가 33으로 오른쪽

 - 두수의 합 63이 부모 노드

 

8. 나머지 두 문자 iejs, gozub

 - geozub가 47로 왼쪽, iejs가 63으로 오른쪽

 - 부모 노드는 110

 

허프만 알고리즘 정리

- g의 경우 가장 많이 사용됨 -> 00 비트

- o는 01000

=> 빈도수가 많을수록 비드 수가 짧음

 

 

bgebejlezusuo 의 허프만 코드와 아스키 코드 비교

1. 아스키 코드

00001010 01100010 01100111 01100101 01100010 01100101 01101010 01101100 01100101 01111010 01110101 01110011 01110101 01101111 00100000

 

2. 허프만 코드

01100110001111001101101100010010101111010101000