C++20 [C++]AVL Tree 1. 균형이진탐색트리 (Adelson-Velskii&Landis) : 균형인수(Balance Factor:BF)를 이용하여 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태를 유지하도록 하는 트리 : 평균, 최선, 최악 시간복잡도 : O(log(n)) : 모든 노드의 BF가 ±1이하이면 AVL트리라고 할 수 있음 cf. AVL의 자세한 동작은 아래 사이트에서 알 수 있음 https://www.cs.usfca.edu/~galles/visualization/AVLtree.html AVL Tree Visualzation www.cs.usfca.edu 1-1. 해당 트리 구성하는 동작 높이 균형 인수(BF) RR/LL/RL/LR 유형에 따른 rotation (=rebalancing) 노드 삽입 노.. 2023. 12. 7. [C++] BST Operations 1. Binary Search Tree : BST에 관한 설명은 아래의 글에서 2023.11.21 - [Python/자료구조] - [python] 이진트리 / 이진 탐색트리(+백준 5639) [python] 이진트리 / 이진 탐색트리(+백준 5639) 1. 이진트리 모든 노드의 차수가 self.data): if(self.right): self.right.insert(item) else: self.right=Node(item) else: raise IndexError def search(self,item,parent=None): if(itemself.data): if(self.right): return self.right.search(item,self) else growingupis.tistory.com .. 2023. 12. 7. [C++] Binary Tree Operations 1. 이진 트리 1-1. 이진 트리 기본 동작 구현 inorder() : LVR preorder() : VLR postorder() : LRV getSize() : 모든 노드의 개수 세는 함수 getHeight() : 트리의 높이 반환하는 함수 containBT() : 트리에 특정 키를 갖는 노드 있는지 true/false로 반환하는 함수 1-1-1. 코드 구현 : 아래와 같은 트리로 구성되게 함 Binary_tree.h #pragma once #include using namespace std; class TreeNode { private: int key; TreeNode* left; TreeNode* right; public: TreeNode(int item) :key(item), left(NULL).. 2023. 12. 5. [C++]Shuffle Doubly linked list 1. 알고리즘 설명 : 연결리스트를 반으로 나누어진 두 개의 연결리스트를 shuffle시키는 알고리즘 ex) 1234567890 → 6172839405 1-1. 알고리즘 동작 Ⅰ. 연결리스트를 반으로(1st half + 2nd half) 나누는 중간 노드를 찾는다 Ⅱ. 기존 연결리스트에서 1st half 연결리스트는 떼고 2nd half 연결리스트만 연결시킨다 Ⅲ. 1st half 연결리스트가 끝에 다다를때까지 기존 연결리스트에 끼워넣는다 1-2. 알고리즘 구현 1-2-1. Doubly linked list with sentinel nodes 2023.11.29 - [C++/자료구조] - [C++]Doubly linked list with sentinel nodes [C++]Doubly linked li.. 2023. 11. 30. [C++]Split Doubly Linked List 1. 알고리즘 설명 : 연결리스트를 반으로 나누는 중간 노드 반환 : 이때 연결리스트를 반으로 나눌 때 노드의 개수가 짝수와 홀수 상관없이 (노드의 개수/2)+1번째 노드 반환 : 노드를 2칸씩 건너뛰어 순회하는 rabbit 노드 + 노드를 1칸씩 건너뛰어 순회하는 turtle 노드로 구성 : rabbit노드가 마지막 노드이거나 tail노드를 가리킬 때의 turtle노드가 중간 노드가 됨 : rabbit 노드와 turtle 노드 모두 첫번째 노드부터 순회 시작 1-1. doubly linked list 2023.11.29 - [C++/자료구조] - [C++]Doubly linked list with sentinel nodes [C++]Doubly linked list with sentinel nodes .. 2023. 11. 29. [C++]Reverse doubly linked list with sentinel nodes 1. 연결리스트 구현 : 구현 방법 관련한 자세한 설명은 아래 글에 2023.11.29 - [C++/자료구조] - [C++]Doubly linked list with sentinel nodes [C++]Doubly linked list with sentinel nodes 1. 설명 : head와 tail이 직접 리스트의 첫번째 노드와 마지막 노드를 가리키는 것이 아닌 sentinel node로 설정하여 각각의 next/prev 노드가 첫번째 노드와 마지막 노드를 가리키게 함으로써 노드 삽입/ growingupis.tistory.com 2. 연결리스트 역순으로 첫 번째 노드부터 마지막 노드까지 순회 해당 노드의 next는 노드의 prev를 해당 노드의 prev는 노드의 next를 이때, 노드의 next/p.. 2023. 11. 29. 이전 1 2 3 4 다음
