bdfgdfg

이진 탐색 트리의 문제점과 AVL트리 이진 탐색 트리의 탐색 연산은 O(logN)의 시간 복잡도를 가진다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하므로. 그런데 이전 장의 이진 탐색 트리는 문제점이 있는데 예로들어 10,20,30,40,50의 Key가 저장된 이진 탐색 트리를 보자. 이렇듯 노드가 한 쪽으로 쏠리게 된다. 만약 1부터 100까지의 Key값이 들어있는 노드들을 이진 탐색 트리에 넣을 시 내가 100이라는 값을 찾기 위해선 100번의 연산. 즉 O(N) 시간 복잡도를 가진다. 그렇다면 저장 순서를 바꾸면 어떨까? 똑같이 1 ~ 5까지의 Key값이 들어간 노드들이지만 위와 비교해서 제법 균형이 잡혀있고 트리의 높이도 줄어들었다. 이렇듯 앞서 구현한 이진 탐색..

탐색 의미는 '데이터를 찾는 방법' 여기서 얘기할 탐색은 선형 탐색, 이진 탐색 등이 아닌 이진 트리에 관련된 탐색이다. 효율적인 탐색을 위해서는 어떻게 찾을까만을 고민해서는 안되고, 그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 우선 고민해야한다.(자료구조) 이진 탐색 트리 이진트리의 구조를 보면 최대 자식 노드를 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..