Data Structure

이진트리(Binary tree)란 자식노드가 최대 두 개인 노드들로 구성된 트리를 말한다.1) 이진탐색트리의 자식 노드 개수는 2개이하이다.2) 모든원소는 중복된 값을 가져서는 안된다.3) 왼쪽 서브트리에 존재하는 노드들의 값은 그 트리의 루트 값보다 반드시 작다.4)

일반적인 큐는 FIFO구조이다.즉, 어떠한 조건없이 먼저 들어온 데이터가 먼저 나가는 구조이다.하지만, 우선순위 큐는 들어간 순서에 상관없이 우선순위 높은 데이터가 먼저 나오는것을 말한다.우선순위 큐는 힙이라는 자료구조를 가지고 구현한다.1) 만일 배열로 구현한다면 우

1) 힙은 Complete Binary Tree이다.2) 모든 노드에 저장된 값(우선순위)들은 자식 노들의 것보다 (우선순위가 크거나 같다.)직접 연결된 자식-부모 노드 간의 크기만 비교하면 된다.힙으로 우선순위 큐를 구현할 떄에는 노드에 저장된 값을 우선순위로 본다.

1) Insertion sort2) Quick Sort3) Merge Sort4) Heap Sort5) Radix Sort정렬되지 않은 Data를 비교할때는 Θ(n) 비교연산을 수행한다.정렬되어 있는 Data를 비교할때는 Θ(lg(n)) 비교연산을 수행한다.