4Legs_Archives

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

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