Chap02. Data Abstraction and Basic Data Structures

Binary Tree ADT

• Binary Tree

  모든 임의의 노드가 많아야 두 개의 자식을 갖는 트리

  - 노드가 없는 트리는 empty binary tree / null binary tree라고 함
  - r : root node. 유일하게 부모가 존재하지 않는 노드
  - 임의의 노드에서 왼쪽과 오른쪽의 subtree를 각각 L, R로 표시, 자식의 최대 개수는 2

• Binary Tree Property
  - depth가 d라면 $2^d$개의 노드가 존재, complete binary tree
  - height가 h라면 최대 $2^{h+1}-1$

Stack

가장 기본이 되는 operation
push(), pop()
LIFO

Queue

가장 기본이 되는 operation
enqueue(), dequeue()
FIFO

Priority Queue

- 우선순위를 데이터가 삽입되는 시간을 기준으로 따짐
- min-priority queue : cost가 작을수록 높은 우선 순위를 가짐
- max-priority queue : profit이 클수록 높은 우선 순위를 가짐

Union-Find ADT for Disjoint Sets

undirected graph에서 connected component를 찾는 문제에 적용

• Union : 임의의 두 집합을 하나의 새로운 집합으로 합쳐 줌
  두 집합의 set id를 s, t라고 할 때, 이 둘이 다른 경우에만 union
  새로 생성된 집합의 set id는 s 또는 t로 설정
• Find : 어떤 원소가 포함된 집합의 set id를 return
  특정 원소에 대한 key 값을 set id(leader)로 설정 가능

Union-Find ADT Operations

• UnionFind create(int n) : 원소가 n개인 disjoint set 생성
  {{1},{2},{3},...,{n}}
• int find(InionFind sets, int e) : 해당 key값을 포함하는 set id를 return
• void makeSet(UnionFind sets, int e) : 기존 집합에 존재하지 않는 원소 e를 set에 추가, {e}도 추가
• void union(UnionFind sets, int s, int t) : set [s]와 set [t]를 포함하는 더 큰 집합 생성, 이때 가장 작은 key값을 갖는 것을 set id로 설정
  set [s]와 set [t]에서 가장 작은 원소를 각각 s, t라고 할 때, 새로운 집합의 set id는 min(s,t)

Dictionary ADT

(key, value)를 pair로 저장
EXAMPLE :: Hashing, Binary search tree 등
항상 정렬되어 있는 것은 아님

Chap04. Sorting

Insertion Sort :: O($n^2$)

• Application of Sorting
  unsorted data : theta(n)번의 비교 연산 필요
  sorted data : theta(log n)번의 비교 연산 필요
• Strategy
  - 삽입 정렬
  - input : 정렬되지 않은 n개의 element
  - sorted segment, unsorted segment의 영역으로 분리
  unsorted segment에서 가장 앞의 원소를 sorted segment에 적절한 순서로 삽입
• Algorithm
  - Input : n개의 element가 저장되어 있는 array E, index는 0부터 n-1까지
  - Output : n개의 element가 오름차순으로 정렬되어 있는 array E

void insertionSort(Element[] E, int n)
int xindex;
for (xindex = 1; xindex < n; xindex++)
	Element current = E[xindex];
	key x = current.key;
	int xLoc = shiftVacRec(E, xindex, x);
	E[xLoc] = current;
return;

int shiftVacRec(Element[] E, int vacant, Key x)
int xLoc;
if (vacant == 0)
	xLoc = vacant;
else if (E[vacant-1].key ≤ x)
	xLoc = vacant;
else
	E[vacant] = E[vacant-1];
	xLoc = shiftVacRec(E, vacant-1, x);
return xLoc;

• loop invariant
  1 . Initialization : 첫 번째 iteration이 수행되기 전 특정 조건을 만족해야 함
  2 . Maintenauce : loop에서 어떤 iteration이 수행되기 전에 참이라면, 다음 iteration이 수행되기 전에도 참
  3 . Termination : 모든 iteration이 종료되었을 때 모든 결과가 참