bdfgdfg

보완된(균형 잡힌)이진 탐색 트리의 구현 기존에 구현 했던 이진 탐색 트리에 추가적으로 구현을 한다. 리밸런싱 관련된 기능 추가와 BSTInsert 메소드와 BSTRemove 메소드를 수정. 먼저 리밸런싱에 필요한 도구들을 정의한다. 1. 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이를 구하여 불균형 여부를 판단하기 위한 함수. -> int GetHeight(Node* bst) template int BinarySearchTree::GetHeight(Node* bst) { int leftH; // left 높이 int rightH; // right 높이 if (bst == nullptr) return 0; // nullptr을 반환하므로 int형으로 형변환. leftH = GetHeight(bst->..

탐색 의미는 '데이터를 찾는 방법' 여기서 얘기할 탐색은 선형 탐색, 이진 탐색 등이 아닌 이진 트리에 관련된 탐색이다. 효율적인 탐색을 위해서는 어떻게 찾을까만을 고민해서는 안되고, 그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 우선 고민해야한다.(자료구조) 이진 탐색 트리 이진트리의 구조를 보면 최대 자식 노드를 2개까지 가질 수 있는 구조로, 1024개의 데이터를 저장한다 할지라도, 트리의 높이는 10을 넘지 않고 레벨을 내려가면서 값의 비교를 통해 비교 연산을 레벨당 한 번씩 하면 될 테니깐. 물론 값의 비교를 위해 이진트리의 저장 규칙이 있어야 한다. 그것이 지금 배울 이진 탐색 트리. 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는 데 사용..

본문은 오름차순을 기준으로 정렬을 설명합니다. 힙 정렬 힙 정렬은 앞서 구현한 자료구조인 '힙(heap)' 자료구조를 이용한 정렬 알고리즘이다. 정렬은 특성은 힙의 다음 특성을 활용하여 정렬하는 알고리즘이다. "힙의 루트 노드에 저장된 값이 가장 커야 한다." - 최대 힙의 특징. 즉 이 특성을 이용해 힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다. 앞서 힙을 제대로 공부했다면 바로 이해가 가능하니 코드를 통해 확인해본다. template void Sort::HeapSort(T* ptr, int len) { Heap hp(Sort::PriComp); int i; for (i = 0; i < len; ++i) hp.Insert(ptr[i]); for (i = 0; i < len; ++i) ptr[i..

기본적으로 오름차순으로 정렬합니다. 버블 정렬 모든 정렬 알고리즘중 매우 간단하고 이해하기 쉬운 정렬 알고리즘이다. 이해와 구현이 쉬운 만큼 성능에는 아쉬움이 존재한다. 매번 옆의 요소와 비교를 하며 오름차순으로 정렬하고 있다. 한번의 정렬과정에서 3241을 2314라는 정렬결과를 보여준 것.(정렬이 끝난것은 아님) 그림을 보면 알겠지만 한번 정렬이 완성된 상태에서 제일 큰 요소가 제일 뒤에 위치한다는것을 알 수 있다. 이렇듯 한번의 정렬에서 요소중 가장 큰 값을 뒤로 보낸다는 특징이 존재한다. 간단하니 바로 코드를 통해 확인한다. template class Sort { public: static void BubbleSort(T* ptr, int len); }; template void Sort::Bub..