Machineboy空

1.1.1 Hashing Introduction this algorithm's often computer science's favorite algorithm, because you're going to find the results of hashing, it's going to give us a fantastic run time for certain operations. Mathematically, we define hashing as a keyspace(table) that we want to transform into a number of different values. So, everything inside of our keyspace is going to be every possible key t..

4.1 Heap introduction 제거 연산을 하는 데 걸리는 시간복잡도를 고려하면, 배열이나 리스트는 O(n)이라 굉장히 비효율적. 그렇다면 트리 구조를 생각해보자. 이진 검색트리의 경우 너무나 견고한 규칙에 따라 구성되어있기 때문에 이것 또한 성능 저하를 일으킨다. 그래서 트리의 아이디어를 가져오되, 노드가 우선순위를 가지고 있는 우선순위 큐를 활용한 힙을 만들어 볼 것 the remove operation is not having any parameters, it's simply going to take the minimum value found in the entire data structure, and remove it and return it back to the user. We want..

3.2.1 B-Tree Introduction 지금까지, 이진트리, AVL Tree, 배열, 리스트 등의 알고리즘을 살펴봤는데 이건 빅오 표기법에 따라 엄청난 런타임 퍼포먼스를 보여준다. but, Big O notation doesn't explain everything. In fact, Big O notation assumes a uniform access time for all of our data. But in reality, uniform access time for all of our data isn't actually the case. Real Application Imagine storing Facebook profiles for everyone in the US. How many recor..

3.1.1 Balanced BST Balanced BSTs are height-balanced trees that ensures nearly half of the data is located in each subtree. 불균형한 BST를 균형하게 바꾸는 알고리즘을 개발해보자. BST Sub-structures Example: BST Insert Consider a new node inserted into an initially balanceed BST: We identify the deepest node in the tree that is out of balance: BST Rotation Generic Left Rotation *arbitary = random BST Insert, Example #2..

이진탐색트리를 만드는 방법은 N!가지이며, worst case의 경우 find, insert, remove의 시간복잡도가 배열이나 연결리스트보다 좋지 못함. 따라서 균형잡힌 이진탐색 트리를 만드는 것이 중요한데, 여기서 사용되는 개념이 균형 계수 등이 있고, 다음 시간에 b tree나, avl tree 등을 만드는 방법을 알아볼 것임. 2.5 BST Analysis Binary Search Trees(BSTs) can take on many forms and structures even containing the same data: So we want to think about how can we build trees that are both efficient, and what happens when w..

이진 탐색트리는 정렬된 이진트리. find 시, 정렬되어 있으므로 해당 노드보다 큰지 작은지 판단 후 좌우 이동. insert 시, find와 같음. find가 반환하는 포인터를 바탕으로 삽입 위치 찾음. remove, 보통은 연결 리스트의 제거 원리가 적용되지만, 자식이 2개일 경우 IOP 순회흐름에서 우선하는 것, 즉 왼쪽 트리의 가장 아래노드와 swap후 제거한다. 이런 원리를 바탕으로 이메일(key)로 개인정보(data)에 접근하는 딕셔너리 등을 만들 때 활용되기도 한다. 2.4 Binary Search Trees(이진탐색트리) A binary search tree(BST) is an ordered binary tree capable of being used as a search structure..

지금까지 배운 것(array, linked list, stack, queue)는 linear or flat data structures. 오늘 배울 Tree는 data structures that provide complicated data and relationships such as a parent, child, and sibling relationships. 2.1 Tree Terminology *terminology 학술적 용어, 전문용어 (=term) A tree is a linked structure with a sense of ancestry (parents,children, siblings, and more)! Terminology Each element in our tree is a no..

queue와 stack은 array와 linked list와 같은 primitive 선상의 데이터 구조보다는 좀 더 상위인듯. 둘 다, array기반, linked list 기반으로 구현할 수 있음. queue를 linked list로 구현할 때는 tail pointer의 개념을 사용해 이중연결리스트. stack을 linked list로 구현할 때는 null pointer 싱글연결리스트로 가능. 1.5 Queue A queue is a first-in first-out data structure that is similar to waiting in a line or "queue"; Abstract Data Type In data structures, we will always begin our analy..