4Legs_Archives

단어 찾기 사전에서 "Algorithm" 이란 단어를 찾는 상황을 가정해보자. 사전에서 단어를 찾는 방법은 여러 가지가 있을 것이다. ① 단순 탐색 : 사전의 처음부터 Algorithm이 나올 때까지 모든 단어를 확인 가장 확실하고 구현하기 쉬운 방법이지만, 찾고자 하는 단어가 사전의 어느 위치에 있냐에 따라 걸리는 시간이 천차만별일 것이다. 따라서 모든 경우에 대해 그다지 좋은 효율을 갖고 있다곤 할 수 없을 것이다. ② 이분 탐색 : 사전의 절반 지점의 단어를 확인 사전의 처음부터 끝까지 모든 단어들 중 딱 절반 지점의 단어를 확인한다. 이 절반 지점을 mid라 하자. 이 때 확인된 단어가 찾고자 하는 단어보다 사전 순으로 앞서면, 다음 탐색 범위는 mid부터 사전의 끝이 될 것이다. 또한 앞서지 않..

레드-블랙 트리 (Red-Black Tree) 이전 게시글에서 AVL 트리에 대해 설명하였다. AVL 트리는 효율적인 BST 검색을 위해, 트리를 가능한 균형있게 유지하는 것이 핵심이었다. 하지만 삽입과 삭제의 효율이 좋지 않은 문제가 있다. 레드-블랙 트리의 균형을 맞추기 위한 다른 방법으로 등장한 트리이다. 정의 레드-블랙 트리 BST의 모든 노드가 Black 또는 Red로 칠해진 트리로, 다음과 같은 규칙을 가진다. RB1. root 노드와 모든 외부 노드(External Node)는 Black Node이다. (RB1' : 내부 노드로부터 외부 노드로의 포인터는 Black이다. 포인터는 노드를 잇는 간선을 의미한다.) RB2. root에서 외부 노드까지의 경로는 두 개의 연속적인 Red Node를 ..

효율적인 이진탐색 트리 (Efficient BST) 다음 두 이진탐색 트리를 보자. 첫 번째 BST는 25를 검색하기 위해 6번의 비교가 필요하다. 하지만 두 번째 BST는 3번의 비교로도 검색할 수 있다. 모든 노드를 Search하는 데 비교 횟수를 비교하면, 우리는 두 번째로 제시된 BST가 Search 수행이 더 효율적이라 할 수 있다. BST가 효율적이기 위해선 가능한 트리의 높이가 최소가 되어야 한다. 그러기 위해선 각 서브트리들이 어느 한쪽으로 치우치지 않고, 균형을 잘 이루어야 할 것이다. 이것이 AVL 트리의 핵심이다. 트리의 균형 (Balance Factor) 우리는 AVL 트리를 사용하기 위해 각 노드마다 균형 인수(BF, Balance Factor)를 둔다. 균형 인수는 한 노드에 대..

이진 탐색 트리 (Binary Search Tree) 딕셔너리(Dictionary)는 페어(Pair)의 모음으로, 각 페어는 Key값과 관련된 다른 값들로 이루어져 있다. 일반적인 딕셔너리 구조는 실제로는 그렇지 않음에도 불구하고 중복된 키값이 없다 가정하지만, 이진 탐색 트리에서는 이러한 가정 없이 쉽게 중복 키값에 대해 확장할 수 있는 자료구조이다. 정의 이진 탐색 트리는 이진 트리의 한 종류로써, 다음 조건들을 만족하는 자료구조이다. ① 각 노드는 구분되는 하나의 키값을 갖는다. ② 왼쪽 서브트리의 모든 키값들은 root의 키값보다 작다. ③ 오른쪽 서브트리의 모든 키값들은 root의 키값보다 크다. ④ 왼쪽, 오른쪽 서브트리 각각 또한 이진 탐색 트리이다. 탐색 (Search) 삽입 (Insert..

힙(Heap) 구조란? 힙은 우선순위 큐를 구현하는 데 자주 이용된다. 이러한 자료구조에서는 제거되는 원소가 모든 원소들 중에서 가장 높은(또는 낮은) 우선도를 갖는다. 힙에 대한 정의는 다음과 같다. 본 게시물은 최대 힙을 기준으로 작성했다. 정의 최대 트리(Max Tree)는 각 노드의 Key 값이 그 노드의 자식 노드보다 항상 큰 노드이다. 최대 힙(Max Heap)은 최대 트리이면서 동시에 완전 이진 트리인 자료구조를 의미한다. 삽입 (Insertion) 힙 구조에서 삽입은 다음과 같이 이루어진다. 삭제 (Deletion) 힙에서의 삭제는 다음과 같이 이루어진다. ※ 본 게시글은 『Fundamentals of Data Structures in C』 를 참고하여 작성되었습니다.