[최소 비용 신장 트리에 들어가기에 앞서] 책에서도 나온 말이지만 그래프로 시작했는데 결국 또 트리 이야기가 나왔다. 그런데 사실 트리 역시 그래프의 한 유형이다. 이는 곧 이어서 보게 될 '사이클이 없는 그래프'를 보면 바로 이해가 될 것이다. [사이클을 형성하지 않는 그래프 == 신장 트리] 이 그래프에서 정점 B에서 D로 가는 방법을 나열해보면 다음과 같다. B-A-D / B-C-D / B-A-C-D / B-C-A-D 이처럼 두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로(Path)'라고 한다. 그리고 동일한 간선을 중복하여 포함하지 않는 경로를 '단순 경로(Simple Path)'라고 한다. B-A-C-B-A-D 와 같은 경로는 B-A를 잇는 간선이 두 번 포함되므로 단순 경로가 ..

[이진 탐색 트리의 문제점과 AVL 트리] 이진 탐색 트리의 탐색 연산은 $O(log_2n)$의 시간 복잡도를 가진다. 이는 이진 트리가 가지는 특징이며 트리의 높이가 하나씩 늘어날수록 추가되는 노드의 수가 2배 증가하기 때문이다. 그런데 이진 탐색 트리는 균형이 맞지 않을수록 $O(n)$에 가까운 시간 복잡도를 가지게 된다. 이를테면 1부터 5까지 순서대로 이진 탐색 트리에 삽입한다고 가정하자. 그러면 1이 루트노드가 되고 오른쪽으로만 길게 쭉 늘어진 이진 탐색 트리가 된다. 이는 선형 자료구조와 다를 바가 없는 모양이 된다. 저장 순서를 조금만 바꿔서 3을 먼저 저장하면 균형이 괜찮게 잡히게 된다. 저장 순서만 바뀌어도 탐색의 성능에 큰 차이를 보이는 것이 이진 탐색 트리의 단점이다. 그리고 이와 같..

[PriorityQueue.h] /* * 비선형 자료구조 - 힙(Heap) 기반의 우선순위 큐(Priority Queue) * 파일명: PriorityQueue.h * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-24 * 이전 버전 작성 일자: * 버전 내용: 힙을 기반으로 한 우선순위 큐 구현 * 이전 버전 내용: */ #ifndef __PRIORITY_QUEUE_H__ #define __PRIORITY_QUEUE_H__ #include "Heap.h" typedef Heap PQueue; // Heap을 PQueue라고 별칭 부여 typedef HData PQData; // HData를 PQData라고 별칭 부여 // 우선 순위 큐 초기화 void PQueueI..

[Heap.h] /* * 비선형 자료구조 - 배열 기반의 힙(Heap) * 파일명: Heap.h * 파일 버전: 0.2 * 작성자: Sevenshards * 작성 일자: 2023-11-24 * 이전 버전 작성 일자: 2023-11-24 * 버전 내용: 우선 순위 판단 기준을 힙에 설정할 수 있도록 함수 포인터로 변경 * 이전 버전 내용: 간단한 힙의 구현 */ #ifndef __HEAP_H__ #define __HEAP_H__ #define TRUE 1 #define FALSE 0 #define HEAP_LEN 100 typedef char HData; // 힙에 저장될 데이터를 HData라고 별칭 typedef int PriorityComp(HData d1, HData d2); // 힙에서 사용될 우선..

[ExpressionTree.h] /* * 비선형 자료구조 - 수식 트리 (이진 트리의 응용) * 파일명: ExpressionTree.h * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-24 * 이전 버전 작성 일자: * 버전 내용: 수식 트리 구현 및 계산 결과 프로그램 작성 * 이전 버전 내용: */ #ifndef __EXPRESSION_TREE_H__ #define __EXPRESSION_TREE_H__ #include "BinaryTree.h" // 수식 트리도 이진 트리의 일종. BTreeNode* MakeExpTree(char exp[]); // 수식 트리 구성 int EvaluateExpTree(BTreeNode* bt); // 수식 트리를 이용한 계산..

[BinaryTree.h] /* * 비선형 자료구조 - 연결 리스트 기반 이진 트리 * 파일명: BinaryTree.h * 파일 버전: 0.2 * 작성자: Sevenshards * 작성 일자: 2023-11-23 * 이전 버전 작성 일자: 2023-11-23 * 버전 내용: 전위, 중위 순회 추가 및 순회 시 할 일을 결정할 수 있도록 함수 포인터 사용. * 이전 버전 내용: 중위 순회 기능까지 포함한 이진 트리 구현. */ // 저자의 표현을 빌리자면, 이진 트리를 구현"할 수 있는 도구"를 만드는 과정이다. // 어디다 갖다 쓸 것인가는 나중에 생각하자. #ifndef __BINARY_TREE_H__ #define __BINARY_TREE_H__ typedef int BTData; // 이진 트리의 ..