코드네임 :

이진 탐색 트리 (최악의 경우 O(N)) 의 성능을 개선한AVL 트리, 레드-블랙 트리, B-트리의탐색, 삽입과 삭제 연산의 시간복잡도는 모두 O(logN) 그런데! O(logN)보다 좋은 성능을 갖는 자료구조는 없을까?>> Hash Table!  : 데이터의 값과 Hash 함수에 의해 삽입 위치가 결정되는 자료구조 : 충돌의 경우를 무시한다면 삽입, 삭제, 검색에 O(1)만 소요됨[ Hash Table의 충돌 해결법 ] 1. Chaining  2. Linear Probing 어라.. 문제점 1해결!!어라.. 문제점 23. Quadratic Probing을 통한 해결!4. Double Hashing

균형을 고려하는 AVL과는 또 다른 트리!  m차 B-트리 의 조건1. 모든 leaf 노드의 깊이가 동일  2. 노드 당 자식 수는 [m/2] ~ m개 (leaf 노드 제외) *[m/2] : 올림 함수  3. 자식 노드의 수는 데이터 수보다 1 많음 (leaf노드 제외) >> 즉, m차 B트리 에서 노드 내 데이터의 수는 최대 m-1개  4. 단일 노드 내에서 데이터는 정렬됨  5. 트리의 관점에서도 데이터는 정렬됨 B-트리에서의 데이터 탐색 과정높이에 따라 결정되므로.. 시간복잡도는 O(hN) = O(logN) [ B-트리에서의 원소 삽입 ]1. 데이터 수 제한을 넘어서지 않는 경우에서의 삽입 - 새 데이터가 들어갈 적절한 리프 노드를 선정 - 해당 리프 노드에 데이터가 추가될 여유가 있는 경우 그대로..

두개의 클래스를 고려1. Node Class : data, left, right, height 값2. AVL Class : 나머지 모든 것   # Case 1 (LL) # Case 2 (RR) # Case 3 (LR) # Case 4 (RL)    https://github.com/codenameVien/DataStructure/blob/main/AVLTree.ipynb DataStructure/AVLTree.ipynb at main · codenameVien/DataStructureContribute to codenameVien/DataStructure development by creating an account on GitHub.github.com

NIL 닐일반적으로 이진 트리의 노드는 값과 left 및 right를 가지는데, left나 right 중 하나 이상이 None 일 수 없음 - 즉 좌측 자식이 없거나, 우측 자식이 없거나, 둘다 없거나모든 None 을 NIL 로 규정 시 아래와 같은 트리를 얻을 수 있음 모든 leaf노드 is NIL값을 가지는 모든 노드는 내부 노드              Recoloring & Restructing  걍 아래는 위에꺼 손으로 해보기 전 적어놧던 개념.. Recoloring 과정>> 원소 추가시엔 Red만 추가하기 떄문에, Black의 수는 신경 쓸 필요 없고, Red 연속만 신경쓰기  그런데 중간에 삼촌 노드 땜에 만족하지 않는 경우가 생겼다! ( NIL = 검정)이땐 어떻게 해야 할까? Restruc..

이진 탐색 트리의 한계- 노드가 N개인 이진 탐색 트리에서 삽입/삭제/탐색에 드는 시간복잡도 : 최악의 경우 O(N) >> 아래와 같은 최악의 불균형 모양일 때,>> 80을 삽입하고자 하면 6개 노드를 모두 다 돌아야함.. >> O(N)BUT!!>> 균형 잡힌 트리의 경우>> 최악의 상황이더라도 연산에 드는 시간복잡도 : O(logN)>>> 높이 h만큼의 노드를 탐색해야하므로 시간복잡도는 O(hN)>>> O(hN) = O(logN) 트리에서 균형이란?임의 노드의 Balance Factor= 좌측 서브트리의 높이 - 우측 서브트리의 높이 >> 아무것도 없는 부분은 -1로 간주함 AVL 트리= 균형잡힌 이진탐색트리(조건)1. 이진탐색트리 이자2. 모든 노드의 Balance Factor의 절대값이 1 이하인 ..

탐색트리란?: 탐색을 위한 트리기반의 자료구조  이진 탐색이란?반을 쪼갬 -> 23이 26보다 작으니 왼쪽에 있겠군 -> 17보다 크니 오른쪽에 있겠군 -> 23이 여기있네!   이진 탐색 트리 : 좌측 서브 트리 값   힙 Heap vs 이진 탐색 Binary Search1. 힙은 부모 - 자식 간 데이터 크기에 중시 ( ex) 맥스힙은 부모가 자식보다 커야 함)      but 이진 탐색 트리는 한 노드를 기준으로 양쪽 자식간의 데이터 크기에 제한 조건2. 힙은 완전 트리 조건을 충족해야하나,    이진트리는 상관 X3. 힙은 중복을 허용하나,      이진 탐색 트리는 중복을 허용하지 않음   삽입 >- 이진 탐색 트리의 루트 노드로부터 출발- 삽입하고자 하는 값과 현재노드의 값을 반복해서 비교하며..