Data Structure

📝 개요 (1) 자식 노드 갯수가 2개 이하로 (2) 왼쪽 자식은 모두 나보다 값이 작고 (3) 오른쪽 자식은 모두 나보다 값이 큰 그리고 모든 자식 노드 또한 위 3가지 성질을 갖는 자료구조. When to use? (1) Local Search getNextNode (next Largest key except myself) Range Search ex) 1~100 中 5~15 (2) Implements Data structure Set, Binary Heap, Priority Queue 👨‍💻 Impelment (C++) 왼쪽, 오른쪽 자식뿐만 아니라 부모노드와 연결도 킵 BST.h BST.cpp main.cpp Key Point (Delete Node) 가장 까다로운 부분이기 때문에 그림과 함께 정..

🔒 문제 💭 생각의 흐름 중복을 허용하지 않기 때문에 같은 Key 값을 발견하면 바로 root를 리턴한다. 최종 삽입위치에 노드를 생성하고 부모가 자식을 가리키는 포인터를 지정해야 하므로 자식 노드로 내려갈 때마다 부모 노드를 킵해야한다. 🔑 풀이 Node* insert(Node* root, int Key) { Node* parent = root; Node* tempNode = root; while (tempNode != nullptr) { parent = tempNode; if (Key == tempNode->data) return root; else tempNode = (Key data) ? tempNode->left : tempNode->right; } if (parent->d..

구현 방식 2가지 1. Priority Queue. // O(n log n) for(int i = 1; i O(n * log n) ∴ O (n * log n) BuildHeap Analysis When to use? k Largest(Smallest) elements in array Implementation (C++) // make Max Heap void PriorityQueue::shiftDown(int index) { int maxIndex = index; do { index = maxIndex; const int leftChildIndex = getLeftChildIndex(index); const int rightChildIndex = getRightChildIndex(index); if (l..

Complete Binaray Tree every level, all nodes are filled ordering left to right except possibly last node When to use? -> Implements Prirority Queue! * Full Binrary Tree : every node has two children ADT of Prirority Queue implements using MAX Heap array -> parent index : i / 2 left child index : i * 2 right child index : i * 2 + 1 maxSize: Capacity size: The number of current elements which heap..

해싱 정의 키(key) 값에 직접 산술 연산을 적용하여 해시 테이블 주소를 통해 값(Value)에 접근하는 것 해시 테이블 (Hash Table) key 값의 연산에 의해 직접 접근이 가능한 자료구조 Dictionary == Map == Table 사전(Dictionary) 자료구조는 Key - Value를 갖는 자료구조로 오로지 키에 의해 값에 접근한다. (키가 정렬되었는지 여부는 구현시 결정 가능하다.) // 별로 중요하지 않다. ex) 사람 이름(key) - 전화번호(Value) 필수 연산은 다음과 같다. Insert Delete Search 이런 사전 자료구조 (Dictionary)를 효율적으로 구현하기 위해 해시 알고리즘을 적용한다. 해시 함수 키를 입력하여 해시 주소를 얻어낸다. 해시 주소는 ..