Abstract Data Type (ADT)

Abstract Data Type

• Structures/Funtions
• C++이나 Java의 Class와 같은 것
• 알고리즘을 디자인하고 정확도를 개선
•  

Tree

• Root: 부모노드가 없는 노드
• Degree: 자식노드의 수
• External node(leaf): 자식노드가 없는 노드
• Internal node: 자식노드가 있는 노드
• Ancestor of a node x: 루트까지의 simple path의 노드들 (x 포함, proper ancestor: 자기 자신 제외)
• Descendant: ancestor의 반대 개념. 자신 아래에 있는 모든 노드들.
• Subtree rooted at a node x: x의 descendant들을 모은 트리. 루트는 x
• Depth: 0부터 시작하여 자식으로 내려갈수록 1씩 증가
• Level: 같은 depth의 노드들
• Height: 최고 depth. 

 

Binary Tree

• 자식 수가 최대 2인 트리
• L: binary tree T의 왼쪽 서브트리
• R: binary tree T의 오른쪽 서브트리
• depth d인 레벨의 노드는 최대 2^d개 (ex. depth가 2일 때, 그 레벨의 노드 수는 4개
• height h인 트리의 노드는 최대 2^(h+1)-1개 = complete binary tree의 노드 수
• 노드가 n개인 트리의 최소 높이는 ⌈log(n+1)⌉-1  (위의 식에서 2^(h+1)-1 <= n 으로 놓고 유도할 수 있음)

Stack

• Last in, first out (LIFO)
• 연산: push, pop

 

Queue

• First in, first out (FIFO)
• 연산: inqueue, dequeue

 

Priority Queue

• element의 순서는 각각의 우선순위에 의해 결정된다.
• min priority / max priority

	unsorted sequence	sorted sequence	binary heap
insert	O(1)	O(n)	O(lg(n))
removeMin	O(n)	O(1)	O(lg(n))
getMin	O(n)	O(1)	O(1)

 

 

Union-Find ADT for Disjoint Sets

• 독립된 집합의 개념
• set id: 해당 집합의 리더가 되는 element
• connected component 찾는 문제에서 활용 가능
• void makeSet(UnionFind sets, int e): 기존의 집합에 element e 추가
• UnionFind create(int n): 자기 자신만 존재하는 n개의 서로소인 집합 생성
• void Union (UnionFind sets, int s, int t): 각 집합의 원래 set id가 s, t (s!=t)인 두 개의 집합을 합함. s, t 중 하나가 새 집합의 set id가 된다. (보통 min(s, t))
• int find(UnionFind sets, int e): e가 포함된 집합의 set id를 찾음

Dictionary

• (key, value)쌍으로 묶임
• key: identifiier
• value(element): associated information
• 순서가 없음