공대생 정리노트

General Trees Traversal General Tree에서 Preorder Traversal과 Postorder Traversal은 정의가 된다. 그러나 Inorder Traversal은 binary tree에서는 정의가 되지만 non binary tree에서는 정의가 되지 않는다. Equivalence Class Problem 임의의 두 노드를 골랐을 때 두 노드가 같은 tree에 있는지 다른 tree에 있는지 어떻게 알아낼 수 있을까? 각 노드의 root를 비교해서 같다면 같은 tree에 있을 것이고, 다르다면 다른 tree에 있는 것일 것이다. 이때 root를 알아내는 operation을 Find라고 한다. 실제 생활에서 사용되는 예로는 SNS에서 나와 다른 사람이 공통적으로 아는 사람이..

어떠한 구조인가? data를 입력 받을 수 있으면서 request가 들어오면 제일 큰 값을 반환할 수 있는 구조 Implementation 1. Unsorted array or linked List Insert : O(1) removemax : O(n) 2. Sorted array or linked list Insert : O(n) removemax : O(1) 위 두 개의 구현 모두 O(n)이 걸리는 함수가 존재하여 효율적이지 못하다. 이를 해결하기 위하여 heap이 등장한다. 3. heap Insert : O(logn) removemax : O(logn) Heap Heap이란 ? complete binary tree의 일종이다. Min-heap : 모든 value는 child value보다 작다. M..

Array Implementation Binary Search Tree는 Array로 표현할 수 있다. 위와 같은 Binary Tree는 다음과 같이 표현할 수 있다. 현재 있는 position number를 r이라고 하자. 그렇다면 그 position의 parent와 child, sibling은 다음과 같다 Parent(r) = floor((r-1)/2) Leftchild(r) = 2r+1 Rightchild(r) = 2r+2 Leftsibling(r) = r-1 Rightsibling(r) = r+1 BST and Traversal 앞의 게시글에서 나왔던 Traversal들 중 inorder traversal를 BST에 적용하면 정렬이 된 순서로 element를 얻을 수 있다. Inorder Trav..

Binary Search Trees(BST) Property: 노드의 left subtree에 있는 원소들의 value는 노드의 value보다 작다. 노드의 right subtree에 있는 원소들의 value는 노드의 value보다 크다. BST의 Operation 1. Check BST 어떠한 노드에 대해서 left subtree의 모든 원소들의 value들은 노드의 value보다 작아야 하고, right subtree의 모든 원소들의 value들은 노드의 value보다 커야한다. 이를 확인하기 위해서 upper bound와 lower bound를 설정한다. left subtree의 upper bound는 노드의 value보다 1 작은 값이고, right subtree의 lower bound는 노드의 ..

Dictionary Concepts : 우리가 원하는 내용을 찾기 위하여 key를 검색한다. Key comparison : key값을 비교하여 같은 key 값을 가진 value를 가져온다. Records and Keys : key를 record와 별도로 저장을 한다. (key, record) pair 형태로 가지고 잇으며 이를 (key, value) pair라고도 부른다. Sorted vs Unsorted Array List Dictionaries list가 key 값으로 sorted가 되어 있을 때 : binary search를 이용하여 key 값을 검색할 때 빠르게 검색할 수 있다. O(logn) 그러나 새로운 (key, value)값을 insert할 때 순서에 맞춰서 insert를 해야하기에 느리다..

Queues FIFO : First in, First out Stack은 LIFO였다면 반대로 Queues는 먼저 들어온 element가 먼저 나간다. 기본 Notation은 다음과 같다. Enqueue : element를 Queue의 끝부분에 추가한다. Dequeue : Queue에 있는 element들 중 가장 오래전에 추가된(가장 앞에 있는) element를 제거한다. Front : 가장 앞에 있는 element를 반환한다. Rear : 가장 뒤에 있는 element를 반환한다. Array based Queue Array를 base로하면 circular queue를 base로 한다. 그냥 단순히 Array로 Queue를 만들게 되면 element들을 추가했다 제거했다 하면서 Array의 앞부분이 비..

Full binary tree 각각의 node가 leaf(자식이 없는 노드)이거나 두 개의 자식을 가지고 있는 internal node인 tree. Complete binary tree 마지막 level을 제외한 모든 level이 완전히 차있어야(full) 한다. 가장 마지막 level은 모든 노드들이 왼쪽부터 채워져 있어야 한다. Full Binary Tree Theorem (1) non empty full binary tree의 leaves 수는 internal node의 개수보다 1개 더 많다. Mathematical Induction을 이용하면 쉽게 증명이 가능하다. 위 theorem을 이용하면 non-empty tree에 대해서 null pointer의 개수가 tree의 node 개수보다 1개 ..

Doubly Linked Lists Linked List의 한계점 : prev()를 하면 O(n) 시간이 걸린다. -> pointer를 두 개 만들자! 기존의 Linked List에서는 head만 null을 가지고 있었지만, Doubly Linked Lists는 tail도 null이다. tail이 있으면 boundary condition을 check하는데 편하다(코딩하기 편하다). 단점으로는 additional storage를 사용하게 된다. Stacks LIFO : Last In, First Out -> 최근에 추가된 element가 제거될때 먼저 제거된다. 기본적인 Notation은 PUSH, POP, TOP이 있다. PUSH : element 하나를 추가한다. POP : stack에 있는 eleme..