Binary Tree, Binary Search Tree, B-Tree

DB 공부하다 B-Tree와 Binary tree들이 헷갈려서 정리할 겸 쓰는 글

 

• Binary Tree (이진 트리) : 자식이 최대 2개인 트리
  • Complete Binary Tree (완전 이진 트리) : 앞에서부터 순서대로 채워지는 트리
  • Full Binary Tree : 모든 depth가 다 채워진 트리
  • Balanced Binary Tree : 모든 leaf node의 depth 차이가 1 이내
• Binary Search Tree (이진탐색 트리, BST) : 왼쪽엔 현재 노드보다 작은 거, 오른쪽은 큰거
• Heap (Binary Heap)
  • Max Heap: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큼
  • Min Heap: 반대
  • Complete Binary Tree의 성질을 가짐
  • 추가: 맨 끝에(complete binary tree에 의해 들어가야 할 자리) 값을 넣고, 부모의 값들과 비교하여 바꿔나감 (heapify)
  • 삭제(pop): 루트 노드를 삭제한 후, 맨 끝의 노드를 루트도 들고 온 후 자식으로 내려가면서 heapify

 

• B-Tree
  • Binary Tree 아니고 .. 이진트리를 확장해 최대 자식 개수가 2 이상도 가능한 트리
  • DB나 file system에서 널리 사용됨
  • 균형이 잘 맞춰져 있어 모든 노드에 접근하는 시간이 일정함

https://mangkyu.tistory.com/286