Balanced Binary Search Tree의 대표적 예 중 하나인 Red-Black Tree를 알아보려 한다. (BST에 대한 설명은 다음 링크를 참고 : https://malangdubu-tech.tistory.com/29)Red-Black Tree란? 이름처럼, 각 노드가 Red 혹은 Black의 색깔을 가지게 된다. 다음의 특징을 만족하는 BST이다.root property : root는 blackexternal property : 모든 leaf는 blackinternal property : red 노드의 자식은 blackblack의 자식은 red, black 둘 다 가능depth property : 모든 leaf는 같은 black depth를 가짐.black depth : root 노드부터..

IntroDynamic Set과 Binary Search Tree Dynamic set은 1. 크기가 동적으로 변화하면서, 2. 삽입/삭제/탐색 연산을 지원해야 한다. BST는 dynamic set 중 하나이다. 한편, 일반적인 tree는 1 조건은 만족하나, 2 조건은 만족하지 않으므로 dynamic set이라 하기 어렵다. Binary Search / Binary Tree / Binary Search Tree 셋은 전부 다른 것! 뒷단어에 유의해 보도록 한다.binary search : 이진 '탐색' 알고리즘binary tree : 이진 '트리' 자료구조binary search tree : 이진 '탐색' 조건을 만족하는 '트리' 자료구조 ($\subset$ binary tree)Binary Searc..

Dynamic sets는 동적인 원소 집합으로, 시간의 흐름에 따라 원소의 개수가 변화하는 집합을 말한다. 이러한 dynamic sets의 구현에서 필요한 array doubling에 대해 알아보고, array doubling을 합리적으로 분석할 수 있는 기법인 amortized analysis(분할 상환 분석)에 대해 알아보려고 한다. Array DoublingArray Doubling이란? array는 사용할 크기를 미리 결정한다는 특성이 있다. 이에 따라 임의의 index에 상수 시간 접근이 가능하다는 장점이 있지만, array의 size가 불필요하게 많이 남거나 필요한 공간보다 부족한 상황이 발생할 수 있다는 단점도 있다. Array Doubling은 array size가 부족할 때 기존 arr..

Radix Sort(기수정렬)은 입력의 제한사항으로 인해 문제의 복잡도가 $\Omega (n)$으로 내려간 경우의 정렬 알고리즘이다. (원래 정렬문제 복잡도는 $\Omega (n \log n)$) → Radix Sort는 특수한 상황에서 정렬을 $O(n)$ time에 수행하는 정렬 알고리즘이다.Radix Sort의 Input 기존 정렬 문제와 달리, radix sort 상황에선 다음과 같은 input에 대한 추가 정보가 주어진다.key값은 1부터 임의의 정수 m 사이의 정수이다.key값의 자릿수가 제한돼 있다. (ex. key값은 다섯자리 이하 정수)각 자릿수의 값 범위가 제한적이어야 한다. (ex. 10진수 → 자릿수당 가능한 값 10개(0~9)) 즉, radix sort는 '자릿수 기반으로 정렬 가능..

기존 heap sort는 $W(n) = 2n \log n + O(n)$ time이 걸린다. Acclerated heap sort의 경우 이를 $n \log n$으로 단축시킬 수 있다. (2배 speedup) fixHeap을 fixHeapFast로 개선한다. Acclerated Heap Sort아이디어 binary search에선 중앙값과 K의 비교를 통해 앞으로 살펴볼 영역의 절반을 없앤다. 즉 수평적으로 divide and conquer 전략을 사용한다. acclerated heap sort에선 수직적으로 divide and conquer 전략을 사용한다.전략 현재 heap의 height h에 대하여, $\frac {h}{2}$가 될 때까지 vacant의 위치를 내린다.현재 vacant의 key값과 부..

Heap Heap의 조건 Heap이 되기 위한 조건은 다음의 두 개이다.구조조건 : complete binary treeheight h에 대하여, h-1까지는 complete tree (꽉 찬 트리)모든 leaves는 depth h나 h-1에 위치, depth h의 leaves는 왼쪽부터 채워진다.순서조건 : partial order tree propertymaxheap 기준, parent의 key 값이 나보다 크거나 같아야 한다. minheap일 땐 parent의 key 값이 나보다 작거나 같아야 한다. 아래는 heap인지, 아닌지를 구분하는 예시이다.Heap ADT 삽입 : insert()삭제 : deleteMax()*max heap 기준탐색 : getMax()*max heap 기준W(n)$O( \..