- 연결할 객체를 나타내는 정점(Vertex)와 객체를 연결하는 간선(Edge)의 집합으로 구성
- 연결 데이터를 저장할 수 있는 자료 구조
- 예시 : 다양한 연결 관계
① Undirected Graph (무향 그래프)
G(V, E)에서
- V = {노드들의 원소} : 정점의 집합
- E : the set of unordered point of V
무향 그래프 예시
무향 그래프 예시 2무향 그래프 예시 3
② Directed Graph (유향 그래프)
G(V,E)에서
- V = {노드들의 원소} : 정점의 집합
- E : a relation on V → V x V의 부분집합 (카르테시안 곱)
Ex. V = {a, b, c}
V x V = {(a,a), (b,b), ..., (c,c)}
유향 그래프 예시유향 그래프 예시 2
2) Tree
Tree
- Tree is an undirected graph that is acyclic and connected
- 즉, Tree란 아래의 조건들을 만족하는 그래프임
undirected graph
connected
acyclic (사이클x)
Forest
- Forest is an undirected graph that is acyclic
- 즉, Forest란 아래의 조건들을 만족하는 그래프임
undirected graph
acyclic (사이클x)
Forest 예시
Rooted Tree와 Binary Tree
① Rooted Tree
- Rooted Treeis a tree in which a node is designated as the root.
- 즉, root가 생김으로써 hierarchy가 생기고, parent와 child가 생긴다.
Rooted Tree 예시 1
- 위의 예시1은 rooted tree가 아니라. root 노드가 없기 때문
Rooted Tree 예시 2
- (a)와 (b)는 다른 rooted tree이다. 노란색 하이라이트 부분에서 parent에 따른 children 노드들이 다르기 때문
② Binary Tree
- Binary Tree is a rooted tree in which each node has AT MOST two children.
→ 즉, 노드별 최대 2개의 children을 갖는 Rooted Tree
Full Binary Tree와 Complete Binary Tree / Almost Complete Binary Tree
① Full Binary Tree(정 이진 트리)
각 노드에서 option이 2개
- (각 노드별) child 0개 또는 2개
Full Binary Tree 예시
② Complete Binary Tree : 모든 레벨이 꽉 차있음
- A complete binary tree is a binary tree in which every level is completed filled.
Complete Binary Tree 예시
③ Almost Complete Binary Tree : 마지막 레벨이 꽉차지는 않아도 왼쪽부터는 차있는 Complete Binary Tree
An almost complete binary tree is a complete binary tree with one except at the last level
(1) it does not have to be completely filled.
(2) nodes should be filled from the leftmost part toward right direction
Almost Complete Binary Tree 예시
그래서
Complete binary tree는 Almost complete binary tree의 일종이다.
단, 한국 많은 자료구조 도서들에서 위에서 언급한 Almost Complete Binary Tree를 Complete Binary Tree(완전 이진 트리)라고 부르며, Complete Binary Tree를 Perfect Binary Tree(포화 이진 트리)라고 부른다.
Index
- 위 예시에서 10을 포함하고 있는 인덱스 : 3
- 인덱스 3의 parent 인덱스 : 1
- 인덱스 3의 left child 인덱스 : 6
- 인덱스 3의 right child 인덱스 : 7
부모/자식 노드 관련 pseudo code
① Parent(i)
역할: 인덱스 i의 부모 노드의 인덱스를 반환
구현: return ⌊i / 2⌋
주어진 인덱스 i에 대해 ⌊i / 2⌋ 연산을 수행 → 이는 주어진 노드의 부모를 찾기 위한 방법
힙에서 배열 인덱스는 일반적으로 1부터 시작한다고 가정하는데,
예: i = 3일 경우, 부모의 인덱스는 ⌊3 / 2⌋ = 1이 됨
⌊⌋ : floor function으로 이 기호는 소수점을 버리고 가장 가까운 정수로 내림
② LEFT(i)
역할: 인덱스 i의 왼쪽 자식 노드의 인덱스를 반환
구현: return 2i
왼쪽 자식의 인덱스는 현재 노드 인덱스 i에 2를 곱한 값
예를 들어, 노드 i = 3일 경우 왼쪽 자식의 인덱스는 2 * 3 = 6이 됨
③ RIGHT(i)
역할: 인덱스 i의 오른쪽 자식 노드의 인덱스를 반환
구현: return 2i + 1
오른쪽 자식의 인덱스는 현재 노드 인덱스 i에 2를 곱하고, 여기에 1을 더한 값
예를 들어, 노드 i = 3일 경우 오른쪽 자식의 인덱스는 2 * 3 + 1 = 7이 됨
이 함수들은 이진 힙(Binary Heap) 자료구조에서 노드들을 배열로 표현할 때 유용하게 사용(힙 : 추후 설명)
PARENT(i)는 현재 노드 i의 부모 노드의 인덱스를 반환하여 트리에서 위로 올라갈 수 있게 한다.
LEFT(i)와 RIGHT(i)는 각각 현재 노드의 왼쪽과 오른쪽 자식 노드의 인덱스를 반환하여 트리에서 아래로 내려갈 수 있게 함
이러한 연산들은 힙 자료구조의 효율적인 탐색을 가능하게 하며, 주로 힙 정렬(Heap Sort), 우선순위 큐 등에서 사용됨
2. HEAP
1) heap 속성과 heap
max heap property (min heap property)
max heap property : 아래의 노드들간의 크기 차이에대한 속성 또는 특징을 의미
- 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같다. ('min heap property'는 작거나 같다)
A (binary) heap : (이진) 힙
힙속성에 따라 max/min으로 나눠짐
① A max heap : 아래의 두 가지 조건을 모두 만족하는 트리
- 형태 속성 : Almost complete binary tree (완전 이진 트리)
- 힙 속성 : max heap property - 모든 노드의 데이터들의 크기가 자식 ≤ 부모
다시말해,
A max heap is an almost complete binary tree with 'max-heap property'
② A min heap :아래의 두 가지 조건을 모두 만족하는 트리
- 형태 속성 : Almost complete binary tree (완전 이진 트리)
- 힙 속성 : min heap property - 모든 노드의 데이터들의 크기가 부모 ≤ 자식
(시험 출제 예정) Heap의 정의?(동음이의어인 [데이터 구조, 메모리 영역] 중 데이터 구조)
2) heap 정렬
MAX-HEAPIFY
왼쪽도 오른쪽도 Max Heap일 때 사용한다.
즉, Before the execution of MAX-HEAPIFY(A, i)
- left subtree is a max-heap
- right subtree is a max-heap
배열 A 예시
MAX-HEAPIFY pseudo code
(1) l : 인덱스 i의 왼쪽 자식 노드 인덱스
- LEFT(i)에서 인덱스 i의 왼쪽 자식 노드의 인덱스를 반환해서 l에 대입
※ LEFT(i) : 인덱스 i의 왼쪽 자식 노드의 인덱스를 반환
(2) r : 인덱스 i의 오른쪽 자식 노드 인덱스
(3) ~ (5) : i의 왼쪽 자식 인덱스(l)이 heapsize 내부에 있는 인덱스이면서,
i의 왼쪽 자식 노드 인덱스가 i보다 크면 largest = l , 그게 아니면 largest = i
- Time Complexity of MAX-HEAPIFY - depends on the position of i - The height of a node : 0 at the leaf, grows upward - The height of a tree : the height of the root node - The depth of a node : 0 at the root, grows downwards
- 위 예시에서 root의 height : 3, depth : 0
- external node들의 height : 0
BUILD-MAX-HEAP
- Max-Heapify를 부분적으로 활용하여 트리를 Max Heap으로 만드는 과정
BUILD-MAX-HEAP pseudo code
(1) 배열 A의 길이를 heap-size[A]에 저장
(2) 배열 A의 길이를 2로 나눈거를 소수점아래를 버린 숫자에서(floor) 1까지를 차례로 i에 대입
(3) 배열 A에 대해서 (2)에서 나온 인덱스값 i에 해당하는 값으로 Max-Heapify를 수행
예시 : BUILD-MAX-HEAP(A), A = [1,3,2,5,4]
5/2 =2.5의 내림값인 2에서 1까지
BUILD-MAX-HEAP 예시
MAX-HEAP(A,2)
BUILD-MAX-HEAP 예시
MAX-HEAP(A,1)
HEAPSORT(A)
HEAPSORT pseudo code
(1) 우선 트리를 MAX-HEAP으로 만든다.
(2) 배열 A의 길이에서(배열 A의 마지막 원소) 2까지를 순차적으로 i에 할당한다. (for문)
(3) (2)의 for문에 해당하는 인덱스 i 와 배열 A의 첫번째(인덱스 = 1) 원소와 자리를 바꾼다.
(4)~(5) (2)에서 배열 A의 길이 ~ 2까지 순차적으로 값이 줄어든 바 있음 → 이에 맞춰 heap-size[A] 값을 하나씩 줄이면서, 이에 따라 배열 A를 MAX-HEAP으로 만든다. (여기서 줄어든 heap size는 아래 코드 중 MAX-HEAPIFY에서 적용된다.)
참고
교수님 확인 필요 - MAX-HEAPIFY는 왼쪽과 오른쪽 서브트리가 이미 MAX HEAP 구조일 때만 호출할 수 있음 - 이에, HEAPSORT(A)는 length[A]/2를 floor한 값의 인덱스까지는 적어도 왼쪽,오른쪽 서브트리가 MAX-HEAP 구조일때에만 사용이 가능
3. 추상 자료형 Priority Queue(우선순위 큐)
힙은 대표적으로 두 가지 목적으로 사용됨 ① 정렬 : 앞절들 내용 ② 추상 자료형 '우선순위 큐'를 구현하기 위해 사용
※ 추상 자료형 : 내부적인 구현보다 기능에 집중하게 해주는 개념
Priority Queue (우선순위 큐)
- 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
→ 큐, 스택과 같은 추상자료형이고, 선입선출인 '큐'와 비슷
→ 데이터를 저장할 수 있고, 저장한 데이터가 우선순위 순서대로 나온다. (각 데이터마다 우선순위가 있음)
- 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용
→ 고객 문의 처리 시 불만도 높은 문의부터 처리할 때에와 같은 상황에서 활용됨 - 우선순위 큐를 구현하는 방법
① 단순히 리스트를 이용하여 구현
② 힙(heap) 자료구조를 이용하여 구현
- 시간 복잡도
- 리스트 : 삽입할 때에는 단순히 연달아 넣으면 되지만, 삭제할 때에는 가장 높은 우선순위의 원소를 찾기 위해서 선형적인 탐색시간이 소요됨
- 힙 : 데이터 넣는것, 빼는것 둘 다 log N → 단순히 N개의 데이터를 힙에 넣어다가 빼는 작업을 수행하더라도 그 자체로서 정렬이 수행
(CHAT GPT) - 우선순위 큐(Priority Queue)는 일반적인 큐(Queue)와 유사하지만, 각 원소가 우선순위(priority)를 가지고 있어 우선순위가 높은 원소부터 처리되는 자료구조
주요 특징 - 큐와 유사하지만 차이점: 큐(Queue)는 선입선출(FIFO)이지만, 우선순위 큐는 우선순위가 높은 원소부터 처리 - 힙(Heap) 자료구조를 이용해 구현하는 경우가 많음 → Max-PQ: 최대 우선순위 큐(우선순위가 높은 값이 먼저 출력됨) → Min-PQ: 최소 우선순위 큐(우선순위가 낮은 값이 먼저 출력됨)
구성 요소와 주요 연산
1) Priority Queue의 개념
Priority Queue
- data structure for maintaning a set S of elements, each with an associated value called a key
(CHAT GPT) - 우선순위 큐에서 key는 각 원소가 가지는 우선순위 값을 의미 - 이 key 값이 원소의 우선순위(priority)를 결정하며, 우선순위가 높은 원소일수록 먼저 처리
- Heap과 같이 Max PQ, Min PQ가 있음
- Max PQ를 기준으로 아래의 네 가지 연산을(3.-2)) 지원하는 자료구조
2) Max-Priority queue 의 네 가지 연산 : Max PQ를 중심으로
① Insert(S,x) : 원소 x 를 set S에 삽입함. 이는 S=S∪{x} 하고 표현될 수 있음
(Chat GPT) 우선순위 큐의 S는 현재 큐에 포함된 원소들의 집합을 의미합니다. 이 집합에 새로운 원소 x를 삽입할 때 아래와 같이 표현합니다 : S=S∪{x} 이는 집합 S에 새로운 원소 x를 추가한다는 의미입니다.
MAX-HEAP-INSERT pseudo code
(1) 힙에 새로운 원소를 삽입할 준비를 위해 힙의 크기를 1만큼 증가시킴. 즉, 새 원소가 들어갈 빈 자리를 마련
(2) 증가된 힙의 마지막 위치(즉, 새로 추가된 원소 자리)에 초기 값으로 -∞를 할당.
이는 가장 작은 값을 할당하여 새로운 key 값으로 변경하기 전에 미리 공간을 확보하는 역할을 한다.
(3) 새로 추가된 원소의 위치에서, key 값을 새로운 value(key)로 증가시킴.
→ HEAP-INCREASE-KEY는 최대 힙의 속성을 유지하기 위해 새로운 key를 적절한 위치로 올림.
→ 부모 노드와 비교하면서 위로 이동하는 과정(스왑)을 포함
② MAXIMUM(S) : S에서 가장 큰 key를 가진 원소를 반환한다.
③ EXTRACT-MAX(S) : S에서 가장 큰 키를 가진 원소를 제거하고 반환한다.
heap-extract-max pseudo code
④ INCREASE-KEY(S, x, k) : 원소 x의 key값을 새로운 value k로 변경한다. (조건 : 새로운 value k는 기존의 key 값보다 커야한다.)
heap-increase-key pseudo code
(1) ~ (2) 새로운 key 값이 기존의 key 값보다 작은 경우를 검사 → 최대 힙에서는 key를 증가시키는 것만 허용하므로, key가 작아지는 경우 에러를 발생시킴 → 만약 새로운 key가 기존 key보다 작다면, 에러 메시지를 출력하고 중단, 이 조건은 힙의 구조를 망가뜨리지 않기 위해 필요
(3) 새로운 key 값을 현재 위치 i에 할당 → 이 단계에서 원소의 key가 증가되었으므로, 이제 부모와 비교하며 힙의 속성을 복구해야 한다.
(4) 부모 노드와 현재 노드를 비교하며 반복하는 루프 - i > 1 : 현재 노드가 루트 노드가 아니면 계속 반복 - A[PARENT(i)] < A[i] : 부모 노드의 key가 자식 노드의 key보다 작으면, 힙 속성(부모 ≥ 자식)이 깨진 상태 → 이 경우 스왑이 필요
(5) 부모 노드와 현재 노드의 값을 swap → 이 스왑을 통해 현재 노드는 한 단계 위로 올라가며, 최대 힙의 속성을 복구
(6) 현재 노드의 인덱스를 부모 노드의 인덱스로 이동 - 이렇게 함으로써, 위로 올라가면서 계속 부모와 비교 → 루트 노드에 도달하거나 부모 노드가 더 크다면 반복을 종료
