-
자료구조 2학교 수업/자료구조 2020. 5. 17. 16:50
저번 포스팅에 이어 자료구조에 대한 설명을 하겠다.
8. heap
- 최대값, 최소값을 찾아내는 연산을 쉽게 하기 위해 고안된 자료구조
- 각 node가 (key, element)로 구성
- Heap-Order와 (Almost) Complete Binary Tree조건을 만족하는 binary tree이다.
* heap-order: 모든 노드에 대해 각 노드의 키값이 자식 노드의 키값보다 작지 않거나(max heap, 이때 root의 키값이 가장 크다) 자식노드의 키값보다 크지않은(min heap, root의 키값이 가장 작다)을 만족해야 한다.
* last node: heap의 maximum깊이의 가장 오른쪽 노드를 의미
- heap의 연산들 (min-heap기준으로 설명)
1) 삽입 연산(insert())
① 완전 이진 트리 구조를 유지하기 위해 삽입 시 트리의 가장 마지막에 원소를 추가한다.
② 그 후 삽입된 형태의 힙이 힙의 조건(heap order)를 만족하도록 재복구시킨다.
복구 방법: Upheap (새로운 key k 삽입 후, heap-order 조건 위반한 경우)
- 삽입 노드로부터 root 방향으로 연결된 노드들을 따라 k를 각 노드와 swap하는 방식
- Key k가 root에 도달하거나 부모노드의 key값이 k와 같거나 작은 경우 upheap을 종료
- Heap의 높이가 O(log n)이므로, upheap의 수행시간은 O(log n) time이다.
2) 삭제 연산(removeMin())
① Root key를 힙의 last node의 값으로 교체하고 last node를 제거한다.
② 그 후 heap-order 조건을 만족하도록 재복구시킨다.
복구 방법: Downheap (root값을 last node의 키 k로 교체 후, heap-order 조건 위반한 경우)
- Root부터 더 작은 값을 가진 자식 노드방향으로 k를 각 노드와 swap하는 방식
- Key k가 leaf에 도달하거나 자식노드의 key값이 k와 같거나 더 클 경우 downheap 종료
- 수행시간: O(log n) time
3) Heap-Sort
- Heap-based PQ: size(), empty() – O(1) time | insert, removeMin – O(log n) time
- Heap-based PQ를 이용하여 배열 정렬할 경우, n개의 원소에 대해 진행하므로 총 O(n log n) time 걸린다.
- list기반의 PQ 방식보다 정렬 속도가 빠르다.
4) Heap 구현 방식
① Top-Down heap 구현
Ø 빈 힙에 위에서부터 아래로 노드를 삽입하면서 확장하는 방식으로 insert연산을 n번 수행 (n: 노드의 개수)
Ø 시간 복잡도: O(n log n) time
② Bottom-Up heap 구현
Ø n개의 노드가 미리 주어질 때 힙을 더 빠른 속도로 구현할 수 있는 방법
Ø 들어오는 키 값 순서대로 트리를 구성한 뒤, 힙 구조가 되도록 마지막 높이에서 한단계씩 높이를 올려가며 heap-order 만족여부를 검사하여 재조정한다.
Ø downheap이용
Ø 두개의 힙을 합쳐 새로운 힙을 완성해나간다. 만약 두개의 힙과 키 k가 주어질 때, k를 root node로 하고 subtree로 주어진 두개의 힙을 가지는 새로운 힙을 생성한 뒤 heap-order조건을 만족하도록 downheap을 수행해 힙을 재조정한다. 이 과정을 계속 반복하여 n개의 키를 가진 heap을 완성
9. map
- Entry가 (key, value)쌍으로 이루어진 자료구조로 데이터 검색 시 유용하다.
- Key는 unique하다. 즉, entry별로 고유의 key를 가진다.
- ADT method: find(k), put(k, v), erase(k), size(), empty()
- map구현 방법
① List-based : 단순히 linked list로 key와 value를 entry로 한 list
Ø Size(), empty(): O(1) time
Ø Put, find, erase: worst case 경우 O(n) time (값 찾을 때 선형으로 찾으므로)
Ø Map구현시 좋지 않다.
② Array-based
Ø Hash-table을 사용하는 방법이다.
Hash Table
- 연관배열 구조(키와 값이 1:1로 연관되어 있는 구조)를 이용하여 키에 대한 결과값을 저장하는 자료구조
- Hash function과 크기 N인 bucket array(or table)로 구성된다.
Hash function
- 목표: 키를 랜덤한 방법으로 가능한 충돌이 발생하지 않도록 분산하는 것
- 다양한 길이의 키 k를 [0, N-1]사이 정수값을 가지는 일정한 길이의 값 h(k)로 변경하여 저장소를 효율적으로 운영할 수 있도록 한다.
- H(k)는 k의 해쉬값이며 bucket array의 index로 사용된다.
- Hash function은 hash code와 compression function을 가짐
① Hash code: key를 integer로 형변환, h1(k)
② Compression function: 정수형인 h1(k)를 [0, N-1]범위 정수값으로 매핑하는 함수, h2(h1(k))
(N: 해쉬값의 분배를 randomize하기 위해 소수값으로 지정)
Ø Division과 MAD 방식이 존재
Ø Division: h2(h1(k)) = |h1(k)| mod N
Ø MAD(Multiply, Add and Divide): h2(h1(k)) = (a*h1(k)+b) mod N (a, b >= 0, a mod N != 0),
division보다 더 정교한 방법으로 키값간 충돌이 덜 발생한다
- Collision handling
해쉬값을 테이블의 index로 사용하기 때문에 서로 다른 키 값이 같은 해쉬값을 가질 때 충돌이 생긴다. 충돌을 해결하기 위한 방법은 아래와 같다.
① Separate Chaining
Ø table의 각 cell을 linked list로 구현하여 entry를 저장
Ø 구현이 간단하지만 테이블 이외에 추가 메모리를 사용
② Open addressing
Ø 충돌되는 item을 테이블의 다른 cell에 저장하는 방법
Ø linear probing, double hashing
③ Linear probing
Ø 충돌되는 item을 한칸씩 이동하며 다음 이용가능한 cell에 저장
Ø primary clustering 문제점이 존재.
Ø primary clustering: 충돌 발생시, 뒤 슬롯에 데이터를 넣어 하나의 데이터 덩어리를 이루기 때문에, 데이터들이 특정 위치에만 밀집하는 현상을 말한다. 때문에 slot이 많아질수록 탐색 시간이 엄청 늘어난다
④ Double hashing
Ø linear probing에 의해 발생되는 clustering문제를 해결한 방법으로 보조 해시 함수 d(k)를 이용한다.
Ø 테이블의 index = (h(k) + j*d(k)) mod N (j=0,1,…,N-1)이며, 충돌이 발생할때마다 j의 값을 0부터 하나씩 증가하며 index를 새로 구한다.
- 성능: worst case경우(모든 key에 대해 충돌발생), n개의 entry를 가진 hash table에서 map 연산은 O(n) time 걸리지만, 보통은 O(1) time이 소요된다.
10. Dictionary
- map과 마찬가지로 Entry가 (key, element)로 구성되며, dictionary는 중복된 key를 허용
- ADT method : find, put, erase, size, empty
- dictionary 구현 방법
① List-based: map에서와 같은 방법. Put에는 O(1)이 걸리고 find, erase에는 O(n)이 걸린다.
② Hash Table: map과 마찬가지. 같은 key값이 존재하므로 value들의 저장 방법에 차이를 둬야함.
③Search Table: key값을 정렬한 search table을 만드는 방법. (STL의 방법)
이 방법에서 binary search를 사용하여 key값을 검색하도록 함.
11. Binary Search Tree
- Search Tree: ordered maps과 ordered dictionaries를 구현하는데 사용되는 tree 자료구조
- Search Tree의 ADT method: find(k), put(k, v), erase(k), size(), empty()
- Binary Search Tree
① internal node에 key or key-value entry를 저장하고
key(왼쪽 자식)<=key(본인)<=key(오른쪽 자식) 조건을 만족하는 이진 트리 자료구조
-> inorder traversal을 하면 sort된 key들을 얻을 수 있음
② external node에는 값을 저장하지 않음
- 삽입 연산
① Root부터 leaf노드까지 k에 대한 탐색을 수행한다.
② K가 존재하면 값을 변경하고 존재하지 않으면 삽입
- 삭제 연산
① root부터 leaf노드까지 k에대한 탐색을 수행하여 해당 노드를 삭제
② leaf 자식 노드를 가진 경우 해당 노드와 leaf 자식 노드를 둘 다 지움
③ 자식 노드가 모두 internal 노드인 경우,
-> 오른쪽 자식 중에서 가장 작은 값을 해당 위치로 옮기기
-> 왼쪽 자식 중에서 가장 큰 값을 해당 위치로 옮기기 방법이 있으며
둘 중 첫번째 방식을 더 많이 쓴다.
- 성능
n개의 item을 가진 ordered map을 높이가 h인 binary search tree로 구현 시
-> 공간 복잡도 O(n)
-> 삽입, 삭제, 찾기 연산의 시간 복잡도 O(h) time
best case: h=log n, 편향된 트리일 경우 Worst case: h=n
12. AVL tree
- 균형잡힌 이진 검색 트리로 모든 노드의 자식 노드간 높이 차이가 1 이하이다.
- 이진 검색 트리 중 노드 n개가 모두 한쪽으로 쏠려 높이가 n이 되는 경우같이 노드들이 한쪽으로 쏠리는 것을 방지
- AVL tree의 높이는 O(log n)
- 종류 : Splay tree, Red-black tree 등
- 삽입 연산
: 이진 검색 트리와 마찬가지로 리프노드를 확장하는 방식으로 수행된다.
단, 삽입 후 Restructuring과정을 통해 트리의 균형을 유지(변경노드부터 root까지 중 균형깨진 첫 노드 찾기)
- 제거 연산
: 이진 검색 트리와 같은 방식으로 수행.
제거된 노드의 부모부터 root까지 중 불균형 생기는 노드 반복해서 찾으며 restructuring수행.
- 성능: size(), empty() – O(1) time | find(), insert(), erase() – O(log n) time
13. Graph
- 정점과 간선으로 이루어지며 트리와 달리 계층(부모-자식)이 존재하지 않는 자료구조
- 주로 G(V,E)로 표현한다. (V:정점, E:간선)
- graph용어:
(1) Directed edge: 방향이 있는 간선
(2) Undirected edge: 방향이 없는 간선(양방향 간선)
(3) Adjacent vertex: 인접한 정점. 간선 하나로 도달할 수 있는 정점.
(4) Degree of a vertex: 정점에서 연결된 간선의 수
(5) Edges incident on a vertex: 정점에서 연결된 간선들.
(6) Parallel edge: 중복된 간선
(7) Self-loop: source(시작 정점)와 destination(도착 정점)이 같은 간선
(8) Simple graph: self-loop와 parallel edge가 없는 그래프
(9) Simple path: 사이클을 포함하지 않는 path(같은 정점이나 간선을 다시 방문하지 않는 path)
(10) Simple cycle: 같은 정점이나 간선을 방문하지 않는 사이클
(11) Subgraph: 그래프 안에 속해 있는 그래프
(12) Tree: 트리도 그래프의 한종류, 그래프 내의 모든 노드들이 연결되어있고 사이클이 없고 무방향 그래프일 경우
(13) Forest : 사이클이 없는 무방향 그래프, tree가 여러 개 존재
(14) Spanning subgraph: 모든 정점들이 연결된 subgraph
(15) Spanning tree: 모든 정점이 연결된 tree (forest가 아님.)
(16) Directed Graph(Digraph): 간선에 방향이 있는 graph
(17) Directed acyclic graph(DAG): 사이클 없는 digraph
(18) Strong Connectivity: digraph에서 모든 정점에서 다른 모든 정점으로 가는 path가 존재.
(19) Strong Connected Component(SCC): digraph의 subgraph로 component에 속한 모든 정점에서 다른 모든 정점으로 갈 수 있음.
(20) Transitive Closure: 주어진 그래프에서 모든 정점에 대하여 다른 정점으로 직접적으로 갈 수 있는 간선을 추가한 그래프.
(21) Weighted Graph: 간선에 가중치가 있는 그래프.
- 표현방법: 간선의 정보 저장박식에 따라 인접리스트, 인접행렬 표현으로 나뉨
① 인접리스트: 공간복잡도 O(V+E), 간선의 수 적은 그래프에서 유리
② 인접행렬: 공간복잡도 O(V*V), 두 정점간 연결 유무를 바로 알수 있고 간선 수 많은 그래프 유리
10
