Total
Search
1. 기본사항
1.1. 트리의 정의
•
사이클이 없는 단순 연결 그래프
◦
Trivial tree: 꼭지점 하나로 구성된 트리
◦
Empty tree: 꼭지점이 하나도 없는 트리
◦
Forest: 한 개 이상의 트리로 구성된 그래프
•
루트 트리
◦
루트라 부르는 노드가 1개 존재
◦
나머지 노드들은 서브 트리. 서브트리의 부모는 다시 루트 트리가 됨
1.2. 주요 용어
•
차수: 자식 노드(바로 밑 자식 노드)의 수
◦
트리 전체의 차수? 자식 노드들의 차수중 가장 큰 차수
•
레벨: 루트에서 특정 노드까지의 경로의 길이
•
높이: 깊이
•
무게: 리프 노드들의 수
1.3. 트리의 표현
•
중첩된 집합
•
중첩될 괄호
•
결각
•
달은 트리
◦
트리의 구조는 동일하지만 노드의 데이터 내용이 서로 다를 때
1.4. 주요 정리
•
그래프가 트리인 경우
◦
n개의 꼭지점을 가지는 연결 그래프가 n-1개의 변을 가질 때
◦
n개의 꼭지점을 가지는 트리는 n-1개의 변을 가짐
2. 이진 트리
2.1. 정의
•
공집합이거나 모든 노드가 최대 2개의 서브트리를 갖는 루트 노드인 트리
•
예시
2.2. 최대 노드 수
•
이진 트리 T의 높이가 h개일 때 T의 최대 노드 수는 2^(h+1) - 1
2.3. 완전 이진 트리
•
정의
◦
높이가 h인 트리에서 레벨 0부터 h-1까지 모든 노드가 채워져 있음
(포화 이진 트리)
◦
레벨 h에서는 왼쪽 노드부터 차례로 채워진 이진트리
•
예시
2.4. 이진 트리의 높이
•
완전 이진 트리의 높이
◦
같은 노드 수를 갖는 트리 중 가장 낮은 높이를 가짐
◦
다 포화상태로 만들어서 가기 때문
•
n개의 노드를 갖는 이진 트리의 최소 높이
•
예시
2.5. 포화 이진 트리
•
높이가 k인 트리에서 레벨 0부터 레벨 k까지 모든 노드가 채워진 이진 트리
2.6. 이진 트리 예제
•
높이가 4인 이진 트리가 가질 수 있는 최대 노드 수?
◦
2^5 - 1
•
높이가 5이고 60개의 노드를 가지는 포화 이진 트리가 존재하는가?
◦
2^6-1 = 63 → 존재하지 않음
•
8개의 노드를 가지는 이진 트리의 최소 높이는 얼마인가?
◦
log8 = 3
•
높이가 2이고 6개의 노드를 가지는 이진 트리가 존재하는가?
◦
존재함
•
높이가 2이고 9개의 노드를 가지는 이진트리가 존재하는가?
◦
포화 이진트리 → 2^3 - 1 = 7
◦
7개 보다 더 많은 경우 높이가 2일 수 없음 → 존재 X
3. 이진 탐색 트리
3.1. 정의
•
이진 트리에서 모든 노드가 탐색을 위한 키(key)값을 가지고 있음
•
키들이 다음의 속성을 만족하는 이진 트리
◦
특정 노드의 왼쪽 서브트리의 키값은 특정 노드의 값보다 작음
◦
특정 노드의 오른쪽 서브트리의 키값은 특정 노드의 값보다 커야함
•
예제
3.2. 구성
•
키 값의 순서에 따라 구성이 달라질 수 있음
•
예제 1)
◦
7, 3, 9, 6, 2, 4, 8, 1, 5
◦
1, 2, 3, 4, 5, 6, 7, 8, 9
•
예제 2)
◦
알파벳 순서대로 크기가 크다고 가정
3.3. 검색
1.
탐색 노드를 루트 노드로 설정한다.
2.
탐색 노드와 주어진 키를 비교한다.
a.
일치한다면 키를 반환하고 탐색을 멈춘다.
b.
주어진 키가 현재 탐색 노드보다 작다면 왼쪽 자식을 탐색 노드로 설정한다.
만약 왼쪽 자식이 없을 경우,키 없음을 반환하고 탐색을 멈춘다.
c.
주어진 키가 현재 탐색 노드보다 크다면 오른쪽 자식을 탐색 노드로 설정한다.
만약 오른쪽 자식이 없을 경우, 키 없음을 반환하고 탐색을 멈춘다.
3.
2번 과정을 반복한다.
•
효율적 이진 탐색 트리 검색
◦
비교 횟수
◦
비교 횟수 기댓 값
▪
자주 나오는 값이 루트에 있다면 결과가 달라질 수 있음
◦
점화식
참고) 허프만 코딩
4. 트리의 활용
4.1. 최소 신장 트리(MST)
•
정의
◦
신장 트리는 그래프 G의 모든 꼭지점을 포함하는 트리
•
예제
◦
위 2개 그래프는 사이클이 존재하므로 신장 트리가 아님
◦
최소 신장 트리
▪
그래프에 가중치가 있을 때, 최소한의 가중치로 연결한 경우
•
최소 신장 트리
◦
그래프 G의 모든 변의 가중치의 합을 총 가중치(total weight)라고 했을 때
◦
G의 신장 트리 중에서 총 가중치가 가장 작은 신장 트리
•
신장 트리의 수는 꼭지점의 개수가 커짐에 따라 기하급수적으로 증가함
4.2. MST 알고리즘 (1) Kruskal
•
알고리즘
1.
가중치의 오름차순으로 변을 정렬한다.
2.
가장 작은 가중치의 변부터 차례대로 트리에 추가한다.
3.
모든 꼭지점이 연결될 때까지 2번 과정을 반복한다.
•
예제
◦
가중치가 가장 낮은 변 → FE (1) 연결
◦
그다음 낮은 가중치 변 → AB (2) 연결
◦
그다음 낮은 가중치 변 → GF (3) 연결
◦
반복
4.3. MST 알고리즘 (2) Prim
•
알고리즘
1.
임의의 꼭지점 하나를 트리에 추가한다.
2.
트리의 꼭지점이 아니면서 트리와 연결된 꼭지점 중에서 가장 작은 가중치의 변으로 연결된 꼭지점을 추가한다.
3.
모든 꼭지점이 연결될 때까지 2번 과정을 반복한다.
•
예제
◦
G를 먼저 넣음. G와 연결된 변의 가중치(4,5,3) 중 가장 낮은 가중치를 가진 GF(3)을 연결
◦
반복
