[CS] 알고리즘 Data Abstraction and Basic Data Structures

ADT

사용자의 측면에서 설명해주는 것이 Abstract Data Type이다. Input과 Output만 명시해준다. 해당 데이터 structure가 어떤 데이터를 저장하는지, 어떤 opeartion을 제공하는지, 발생하는 예외상황 같은 것을 제공하는 것이 ADT이다.

Tree Terminology

Root: parent가 없는 노드

Degree: 자식의 수

External node: 자식이 없는 노드(Degree가 0인 노드)

Internal node: 자식이 하나 이상인 노드

Ancestor of x: 자기자신을 제외하고 루트보다 x의 parent까지 있는 노드

Descendant: 자기자신을 제외하고 child. Ancestor와 반대의 개념

Subtree of rooted x: x가 루트이면서 x의 Descendant인 트리

Depth: 다른 노드의 depth = parent의 depth + 1

Level: 같은 depth를 가지는 노드들의 집합

Height:

• 트리에서의 height: 그 트리에 있는 가장 큰 depth.
• 노드에서의 height: 해당 노드가 루트인 subtree의 height.
  

Binary Tree ADT

1) Binary Tree의 depth가 d인 경우에는 노드가 많아봤자 2^d 개이다.

2) height가 h인 트리는 많아야 총 2^(h+1) -1의 노드를 가진다.

3) n개의 노드를 갖는 트리는 적어도 | log(n+1) | -1의 height를 갖는다.

 2^(h+1) ≥ n+1 → h+1 ≥ log(n+1) → h ≥ log(n+1) - 1

Stack(LIFO)

Queue(FIFO)

Priority Queue

원소마다 우선순위 값을 가지고 있다. 우선순위 큐는 최소 우선순위 큐, 최대 우선순위 큐로 나뉜다. 우선순위 큐를 구현하는 방법은 heap, unsorted sequence, sorted sequence가 있다.

	unsorted sequence	sorted sequence	heap
insert()	O(1)	O(n)	O(logn)
removeMin() removeMax()	O(n)	O(1)	O(logn)
min(), max()	O(n)	O(1)	O(1)

Union-Find ADT for Disjoint Sets

집합마다 setId라고 불리는 대표 집합이 있다. setId가 같으면 하나의 집합. 다르면 다른 집합이다.

Union-Find ADT Operations

원소 중에 하나만 있더라도 그것이 다 setId가 된다.

makeSet();

union-Find 구현방법이 두가지가 있는데 하나는 리스트 형태로 구현하는 것과 forest형태로 구현하는 방법이 있다. 두개의 서로다른 트레이를 머지해주는 방법이 있다. key 와 value의 pair로 저장을 한다.