📖 학습 주제
- 큐 (Queue), 순환 큐 (Circular Queue), 우선 순위 큐 (Priority Queue)
- 트리 (Tree), 이진 트리 (Binary Tree), 이진 탐색 트리 (Binary Search Tree)
- 힙 (Heap)
✏️ 주요 메모 사항 소개
큐 (Queues)
-
자료를 보관할 수 있는 선형 구조, 넣을 때 한 쪽 끝에서 넣고 (enqueue), 꺼낼 때에는 반대 쪽에서 뽑아 꺼내는 특성을 가짐 (dequeue). 선입선출(FIFO) 특징.
-
배열이나 연결리스트를 이용하여 구현할 수 있지만, 배열의 경우 dequeue에 O(n)의 복잡도를 갖기 때문에 이중 연결 리스트로 구현하는 것을 추천.
<큐의 활용>
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronously) 일어나는 경우에 활용.
- 자료를 생성하는 작업이나 자료를 이용하는 작업이 여러 곳에서 일어나는 경우에 활용 가능.
- 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우
<큐의 연산>
1. size() : 큐의 데이터 원소의 개수를 반환
2. isEmpty() : 큐가 비어 있는지를 판단
3. enqueue(x) : 데이터 x 를 큐에 추가
4. dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거 (반환 o)
5. peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거 x)
환형 큐 (Circular Queues)
- 정해진 개수의 저장 공간을 빙 돌려가며 이용하는 구조.
front와rear포인터를 사용하여enqueue,dequeue작업 수행. - 큐가 가득 차면 더 이상 원소를 넣을 수 없기 때문에 큐 길이를 기억하고 있어야 한다.
- 큐의 연산을 동일하게 갖고 가고 큐 상태가 꽉 차있는지를 판단하는
isFull()연산을 추가한다.
우선순위 큐 (Priority Queues)
- 큐의 FIFO 원칙을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식. 운영체제의 CPU 스케줄러 등에 이용된다.
<구현방법>
1. Enqueue 시 우선순위 순서를 유지하도록 구현, 2번보다 조금 더 유리
2. Dequeue 할 때 우선순위 높은 것을 선택하도록 구현
트리 (Trees)
- 정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조.
<트리 용어 정리>
루트(Root) 노드 : 최상위의 노드 : 1
리프(Leaf) 노드 : 자식이 없는 노드 : 3,5,6,7
내부(Internal) 노드 : 루트와 리프가 아닌 나머지 노드 : 2,,4
노드의 수준(Level) : 루트(level 0)를 기준으로 내려갈 때 마다 1 증가 : 5,6,7의 level은 2, (특정 노드까지 가는데 거쳐야하는 간선의 수를 나타냄)
트리의 높이(Height),깊이(Depth) : 최대 수준(level) + 1
노드의 차수(Degree) : 자식(서브트리)의 수
이진 트리(Binary Tree)
- 모든 노드의 차수가 2 이하인 트리, 재귀적으로 정의할 수 있다.
- 빈 트리(empty tree)이거나 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 (단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진 트리)
<포화 이진 트리(Full Binary Tree)>
- 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리 (높이가 n이고 노드의 개수가 2ⁿ-1인 이진 트리)
<완전 이진 트리(Complete Binary Tree)>
- 높이가 n일 때 레벨 n-2 까지는 포화 이진 트리, 레벨 n-1에서는 왼쪽부터 순차적으로 채워져 있는 트리
<이진 트리 연산>
size() : 현재 트리에 포함되어 있는 노드의 수를 구함.
depth() : 현재 트리의 깊이(높이)를 구함
traversal() : 트리 순회
<이진 트리 구현>
노드(Node): Data + Left(왼쪽 자식) + Right(오른쪽 자식)root설정size()=left subtree의 size()+right subtree의 size()+1depth()=left subtree의 depth()와right subtree의 depth()중 더 큰 것에 +1traversal(): 깊이 우선 순회 vs 넓이 우선 순회
깊이 우선 순회 (depth first traversal)
1. 중위 순회 (in-order) : left subtree -> 자기 자신 -> right subtree
2. 전위 순회 (pre-order) : 자기 자신 -> left subtree -> right subtree
3. 후위 순회 (post-order) : left subtree -> right subtree -> 자기 자신
넓이 우선 순회 (breadth first traversal)
- 수준(level)이 낮은 노드를 우선으로 방문, 수준이 같은 노드들 사이에는 부모 노드의 방문 순서에 따라 방문하고 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
- 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야 함 (Queue 이용)
<구현>
- 비어있는 list(방문 순서)와 queue 생성
- 트리가 비어있지 않다면 Queue에 root 노드 추가
- Queue에서 노드 하나 뽑아내기 (방문)
- 뽑아낸 노드의 자식 노드 Queue에 추가 (왼쪽부터)
- 2-3 반복, Queue에 원소가 없을 때 까지
이진 탐색 트리 (Binary Search Tree)
- 모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 이진 트리
- 특정 데이터를 검색하는데 유용하게 사용할 수 있고 배열보다 데이터 원소의 추가, 삭제가 용이하다는 장점이 있다.
- 공간 소요가 크다는 단점이 있다
- 한쪽으로 치우쳐진 트리가 만들어지는 경우 이진 탐색 트리가 효율적이지 못할 수 있다. 따라서 높이의 균형을 유지함으로써 O(log n)의 탐색 복잡도를 보장할 수 있다. 하지만 삽입 삭제 연산이 보다 복잡해진다. (EX : AVL 트리, 레드-블랙 트리)
<추상적 자료구조>
데이터 표현 - 각 노드는 (key, value)의 쌍으로 구성, 키를 이용해서 검색 가능하고 보다 복잡한 데이터 레코드로 확장이 가능하다.
<이진 탐색 트리 연산>
insert(key,data) : 트리에 주어진 데이터 원소를 추가
remove(key) : 특정 원소를 트리로부터 삭제
lookup(key) : 특정 원소를 검색
inorder() : 키의 순서대로 데이터 원소를 나열
min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색
<이진 탐색 트리 구현>
insert(key,data) : 루트 부터 값을 비교해서 작으면 왼쪽, 크면 오른쪽으로 탐색해서 말단에 삽입
remove(key)
- 키(key)를 이용해서 노드를 찾기, 부모 노드도 알고 있어야 함 (없으면 삭제할 필요가 없고, 삭제 시 이진 탐색 트리의 구조를 유지하기 위해 부모 노드도 알고있어야함)
- 말단 노드인 경우 : 그냥 그 노드를 삭제, 부모 노드의 링크를 조정
- 자식을 하나 가지고 있는 경우 : 삭제되는 노드 자리에 그 자식을 대신 배치하고 부모 노드의 링크를 조정
- 자식을 둘 가지고 있는 경우 : 삭제되는 노드보다 바로 다음으로 큰 키를 가지는 노드를 찾아(삭제 노드의 오른쪽에서 시작해서 제일 왼쪽 노드) 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 삭제
lookup(key)
- 찾으려는 키를 입력받아 찾은 노드와, 그것의 부모 노드를 반환 (없으면 None, None)
- 키 값을 비교해서 작으면 왼쪽으로, 크면 오른쪽으로 다시 lookup(key,self)
- 부모 노드도 반환해야 하기 때문에 lookup 의 인자로 self도 넣어줘야함
inorder() : 이진 트리의 순회와 동일
min() : 왼쪽 서브트리의 min()을 재귀적으로 구현
max() : 오른쪽 서브트리의 max()를 재귀적으로 구현
힙 (Heaps)
- 이진 트리의 한 종류로 다음 조건을 만족함.
- 루트 노드가 언제나 최댓값 또는 최솟값을 가짐 (
max heap,min heap) - 부모 노드는 모든 자식 노드보다 크거나 작음.
- 완전 이진 트리
<최대 힙 (Max Heap) 연산>
insert(item) : 새로운 원소를 삽입
remove() : 최대 원소 (root node) 를 반환하고 삭제
<배열을 이용한 최대 힙 설계>
노드 번호 m 을 기준으로
- 왼쪽 자식의 번호 :
2 * m - 오른쪽 자식의 번호 :
2 * m + 1 - 부모 노드의 번호:
m // 2 - 완전 이진 트리이므로 노드의 추가,삭제는 마지막 노드에서만 수행
insert(item)
1. 트리의 마지막 자리에 새로운 원소를 임시로 저장
2. 부모 노드와 키 값을 비교하여 위로, 위로 이동
remove()
1. 루트 노드의 제거 (최댓값 or 최솟값)
2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
3. 자식 노드들과의 값을 비교하면서 아래로, 아래로 이동
4. 자식이 둘 있다면 자식 중에서 더 큰 값과 변경
<최대/최소 힙의 응용>
- 우선 순위 큐 (priority queue)
enqueue 할 때 "느슨한 정렬" 을 이루고 있도록 함 : O(log n)
dequeue 할 때 최댓값을 순서대로 추출 : O(log n)
- 힙 정렬 (heap sort)
정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(log n)
삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 : O(log n)
원소들이 삭제된 순서가 원소들의 정렬 순서
정렬 알고리즘의 복잡도 : O(nlog n)
💦 공부하며 어려웠던 내용
이진 탐색 트리에서의 노드 삭제 연산을 구현하는 예제가 조건문이 중첩되서 여러번 들어가기 때문에 생각할게 많아 어려웠던 것 같다.
