binaryTree.md

이진트리 (Binary Tree)

: 모든 노드가 정확하게 두 개의 서브 트리를 가지고 있는 트리

• 이진트리의 레벨 n에서 노드의 최대 수 → 2ⁿ
• 최대 높이가 h일 때 최대 노드 수 → 2ʰ-1
• Leaf Node 높이가 1일 때 최소 높이 → log₂(N+1)

이진트리 유형

전 이진트리 (Full Binary Tree, Strict Binary Tree)

: 모든 노드가 0개 또는 2개의 자식노드를 갖는 트리

완전 이진트리 (Complete Binary Tree)

: 마지막 레벨을 제외하고 모든 레벨이 왼쪽에서 오른쪽으로 완전히 채워져 있는 트리

포화 이진트리 (Perfect Binary Tree)

: 모든 내부 노드가 2개의 자식노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는 트리

균형 이진트리 (Balanced Binary Tree)

: 왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리

• AVL Tree
• Red-Black Tree
• B-Tree, B*Tree, B+Tree

---

Referencs

• @ratsgo
• @yoongrammer