2. Data Abstraction and Basic Data Structures

1) Abstract Data Type

---

• Abstract Data Type
  Structures : data 구조 선언
  Functions : operation 정의 로 구분
  ex) C++ class Member variables, Member functions
  
  
• Tree Terminology
  - root : 부모 노드가 없는 노드
  - degree : 자식 노드의 수
  - External node(leaf) : degree가 0인 노드 (자식 노드가 없는 노드)
  - Internal node : 양의 degree를 갖는 노드 (자식 노드가 있는 노드)
  - Ancestor of node x : root 노드부터 x 노드 까지의 path
  proper ancestor : 자기자신 제외한 ancestor
  ex) G의 Ancestor는 D, I, E
  - Descendant of node : ancestor의 역
  - Subtree rooted at a node x : x의 descendant들로 이루어진, x가 root인 트리
  - Depth
  root의 depth : 0 / 다른 노드의 depth : 1 + depth[parent]
  - Level of tree : 같은 depth를 가진 모든 노드
  - Height
  Height of a tree : leaf들의 depth의 최대값
  Height of any node in a tree : 그 노드가 루트인 서브트리의 leaf들의 depth의 최대값
  
  
  [트리 그림 첨부 필요]
  
  
  

2) Stack

---

• 삽입 삭제가 top에서만 이루어지는 선형 자료 구조
• updating policy : LIFO(last in first out)
• Main Operation : push(), pop()

3) Queue

---

• 삽입이 rear(=back), 삭제가 front에서만 이루어지는 선형 자료 구조
• updating policy : FIFO(first in first out)
• Main operation : enqueue(), dequeue()
  
  

4) Priority Queue

---

• 큐 내의 데이터의 어떤 정보가 우선순위로 동작 된다.
  FIFO Queue는 데이터가 도착하는 시간을 우선순위로 하여 동작하는 것이다.
  
• 종류

	a cost viewpoint : 적은 비용이 우선순위 (min-priority queue)
    	a profit viewpoint : 큰 이익이 우선순위 (max-priority queue)

• Main Operation : insert, remove[removeMin, removeMax], get[getMin, getMax]

• 	Unsorted Sequence	Sorted Sequence	(binary) Heap
  insert	O(1)	O(n)	O(lgn)
  removeMin	O(n)	O(1)	O(lgn)
  getMin	O(n)	O(1)	O(1) => 루트만 제거하므로

  
  

5) Union-Find ADT Operations

---

• Undirected graph에서 Connected component를 찾는 문제에서 사용된다.
• vertex가 edge로 연결되면 같은 집합으로 간주한다.
• 집합의 key값을 set id(=leader, representative)라고 부른다.
• Union-Find ADT operations

	UnionFind create(int n)
	- 원소가 n개인 disjoint set을 만들어준다. 각 값이 하나의 집합이 된다
    	  { {1}, {2}, {3}, ... , {n} }
   	int Find(UnionFind sets, int e)
   	void makeSet

7) Dictionary

---

• Identifier(=key)와 Identifier과 관련된 inforamation(=value, element)로 구성된다.
• Hashing, Binary tree등을 통해서 구현된다.