3. 자료구조

1. 2WAY 합병정렬

기억공간 : S = 2N

수행시간 : O(nlog2n)

2개씩 묶어서 선택정렬을 호출

2. 기수정렬(Radix) = 버킷정렬

기수 : K값이 취할 수 있는 값의 개수(10진수는 0-9로 10개, 8진수는 0-8은 9개)

큐의 길이 : n개, n은 최대크기

1. 기수의 개수만큼 버킷을 생성

2. LSK(일의자리부터)

   MSK(십의자리부터) 선택

3. 정렬

[ LSK 정렬 ]

19, 01, 26, 43, 92, 87, 21, 38, 11, 73

[1단계]

0

1 - 01, 21, 11

2 - 92

3 - 43, 73

4

5

6 - 26

7 - 87

8 - 38

9 - 19

01, 21, 11, 92, 43, 73, 26, 87, 38, 19

[2단계]

0 - 01

1 - 11, 19

2 - 21, 26

3 - 38

4 - 43

5

6

7 - 73

8 - 87

9 - 92

01, 11, 19, 21, 26, 38, 43, 73, 87, 92

3. 외부정렬

디스크나 보조기억장치를 사용해 합병

외부정렬기법

- 균형합병(Balanced Merge)

- 다단계, 다상 합병(Polyphase Merge)

- 교대 합병(Oscillating Merge)

- 계단식 합병(Cascade Merge)

1. 균형합병

두개이상의 테이프가 필요

2. 다단계 합병

세개 이상의 테이프가 필요

피보나치 수열을 이용

3. 교대합병

자기테이프의 순, 역방향 모두 사용 가능

1. 트리

1.1 트리의 정의

근노드가 존재

서로 분리된 서브 트리로 나누어짐

1.2 용어

- 노드(node)

트리를 구성하는 요소

- 근노드(root node)

트리의 루트 노드

- 디그리(degree)

각 노드의 가지수

- 트리의 디그리

트리의 최대 디그리

- 단노드(terminal node, leaf node)

디그리가 0인 노드

- 간노드(nonterminal node)

디그리가 0이 아닌 노드

- 자노드(children node, son node)

바로 자식노드

- 부노드(parent node)

바로 부모노드

-제노드(sibling node)

바로 형제노드

- 조상노드(ancestors node)

근노드부터 임의의 노드까지의 경로

- 레벨(level)

루트가 1 자식으로 내려갈수록 1씩 증가

- 깊이 = 높이 = height = depth

1.3 종류

- 일반트리

- 이진트리

노드의 디그리가 2 이하

왼쪽 오른쪽의 서브트리가 확실히 구분되어진다.

공집합도 포함한다.

이진트리의 종류

1. 엄밀한 이진 트리

각 노드의 디그리가 2 또는 0

2. Knuth의 이진 트리

각 노드의 디그리가 2 이하인 트리

3.정 이진 트리(Full Binary Tree)

레벨의 노드를 모두 채운 트리

4. 전 이진 트리(Complete Binary Tree)

순서를 만족하여 채운 트리

5. 경사이진트리 = 사향 이진 트리

노드가 한쪽으로만 치우친 트리

	일반 트리(K진 트리)	이진 트리
총 링크 수	k * n	2 * n
널 링크 수	(k-1)*n +1	n+1