KalelPark's LAB

Red & Black tree란? - Red & Black tree는 AVL tree에 색상이 입혀진 것이다. - 모든 노드는 빨강색 혹은 검정색으로 이루어져 있습니다. 또한, 리프 노드(Externel node)들은 모두 검정색으로 이루어져 있습니다. Red & Black tree's Properties 1. 루트 노드와 리프 노드는 모두 검정색 노드로 구성되어 있습니다. 2. 루튼 노드에서, 리프 노드까지의 경로에는 연속적으로 빨강색 노드가 존재할 수 없습니다. 3. 루트 노ㅌ드에서, 리프 노드까지의 모든 경로에는 동일한 검은색 노드의 개수가 존재합니다. * Red-Black Tree를 만들 때, node를 insertion할 때, Red를 우선적으로 삽입합니다. Red & Black tree's ..

AVL tree란? - Binary SearchTree의 경우, 한쪽으로 노드가 쏠릴 수 있다. 트리에서 특정 값을 찾으려면 O(N)의 시간이 필요하다. 하지만, biasedTree를 AVL tree로 구성하면, 어떤 노드를 탐색하든 O(logN)에 탐색하는 것이 가능하다. - Binary Search Tree의 속성을 가집니다. - 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다. - 높이 차이가 1보다 커지면 Rotation을 활용하여, 균형을 맞춰, 높이 차이를 최소화합니다. - 삽입, 검색, 삭제의 시간 복잡도가 O(logN) 이다. (N : 노드의 개수) Balance Factor(BF) - AVL트리는 균형이 무너졌는지에 대해 판단할 때, Balance Factor라는 것을 활용합니다. A..

Hashing이란? - 선형 탐색이나, 이진 탐색은 모두 키를 저장된 키 값과 반복적으로 비교함으로써, 탐색하고자 하는 항목에 접근한다. 이러한 방법들은 최대 가능한 시간 복잡도가 O(logN)에 그친다. - 해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 용어 Identifier density - Identifier density is the ratio n/T, where n is the number of identifiers in the table. T is number of possible identifiers. (Table에 속해있는 identify의 개수) Loading factor - a = n / (s * b) 의 저장공간을 가지고 있습니..

Merge sort 이란? 분할 정복(divide and Conquer)에 속하는 알고리즘 중 하나로, "폰 노이만(von Neumann)"이라는 사람이 제안하였다. 하나의 배열을 분할하고, 분할된 배열을 정렬하고, 분할된 배열을 합하여, 최종적으로 정렬하는 알고리즘이다. 시간복잡도(Time Complexity) - O(nlogN) Merge sort 동작 1. 배열을 중간 index를 기준으로 좌, 우로 나눕니다. (부분 배열이 1개가 남을 때까지 계속해서 반복.) 2. 이후, 합병을 진행하는데 배열 내 요소의 대소 비교를 한 후, 배열을 합병합니다. Merge sort with C/C++ void merge(element initList[]. int i, int m, int n) { int j, k,..

Binary Search Tree 이란? 이진 탐색 트리(binary search tree)란 연결리스트(linked list)를 결합한 자료구조의 일종이다. 이진 탐색(binary search)의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제가 가능합니다. 이진 탐색(binary search)의 경우 탐색에 소요되는 계산복잡성은 O(longN)으로 빠르지만, 입력 및 삭제가 불가능하고, 연결리스트의 경우 입력, 삭제에 필요한 복잡도는 O(1)이지만, 탐색을 하는데, O(N)의 시간이 걸리는데, 탐색과 입력 및 삭제를 효율적으로 활용해보고자 하는 것이, 이진 탐색 트리(Binary Search Tree)입니다. 시간 복잡도 Common case : O(h) Worst case : O(n) ..

Heap 이란? 완전 이진트리(Complete Binary Tree)의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬(느슨한 정렬 상태) 상태를 유지합니다. - 큰 값이 상위 레벨에 있으며, 작은 값은 하위 레벨에 있다고 보면 됩니다. - * Max Heaps = Max trees and also Complete binary tree Priority Queue 이란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First in First Out 형식의 자료구조 이다. 우선순위 큐(Priority Queue)는 일반적으로 힙(Heap)을 이용하여 구현합니다. 일반적으로, inse..

Dijkstra's Algorithm 이란? 최단 경로(Shortest Path) 탐색 알고리즘이다. 한 정점(Vertex)에서 다른 정점(Vertex)까지의 최단 경로를 구하는 알고리즘 중 하나이다. 최단 경로(Shortest Path)를 찾는 과정에서, 도착 정점(Vertex) 뿐만 아니라, 다른 정점(Vertex)까지 최단 경로로 방문하여, 각 정점(Vertex)까지의 최단 경로를 찾게 됩니다. 시간복잡도 (Time Complexity) - using priority queue case : O(ElogE) - common case : O(n^2) Dijkstra's Algorithm 동작 1. 시작 정점(Vertex)를 설정합니다. (시작 정점(Vertex) 비용 : 0) 2. 시작 정점(Verte..

Insertion sort 이란? 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 비분과 비교하여, 위치를 찾아 삽입함으로써, 정렬을 완성합니다. 시간복잡도 (Time Complexity) - best case : O(n) - worst case : O(n^2) * It does little work if the list is nearly sorted Insertion sort 동작 1. 배열 내에서, 2번째 위치의 값을 임시로 저장합니다. 2. 임시로 저장한 값 이전에 위치한 원소들과 비교하여, 값을 변경합니다. 3. 위의 1 ~ 2번의 과정을 계속해서 시행합니다. Insertion sort code with C/C++ void insert(element e, element a[], int i..