Machineboy空

이진탐색트리를 만드는 방법은 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..

1.3 Run Time Analysis 런타임 분석은 입력 데이터의 크기를 늘려가며 어떤 알고리즘이 빠른지 분석하는 기법. 배열의 사이즈를 재조정하는 방법 2가지를 비교해보았음. Run-Time Analysis allows us to formalize a method of comparing the speed of an algorithm as the size of input grows. We summeraize the runtime in "Big-O notation", leaving only the term that dominates the growth O(1), constant time approximately same time no matter how many data. O(n), linear time..

1.1 Arrays An array stores data in blocks of sequential memory. so that as soon as one element ends, the next element begins. Array Limitation #1 : 모든 요소가 같은 데이터 타입 Elements are all the same type: ex) An integer array must only contain integers. The size(number of bytes) of the type of data is known. We can calculate the offset to any given index from the start of the array: *offset: 고정점으로부터의 위치..

4.6 Inheritance Inheritance allows for class to inherit all member functions and data from a base class into a derived class. Generic to Specialized A base class is a generic form of a speciallized, derived class. without having to rewrite logic, Initialization When a derived class is initialized, the derived class must construct the base class: Cube must construct Shape By default, uses default..

4.5 Templates and Classes C++ allows for us to use the power of templates in building our own classes and functions. Templated Functions A template variable is defined by declaring it before the beginning of a class or function: //class template class List{ private: T data; }; //function template int max(T a, T b){ if(a >b) {return a;} return b; } Compile-TIme Binding Templated variables are che..