이진 트리와 이진 탐색 트리

이진 트리(BT)

---

각각의 노드에 자식 노드 수가 2개 이하로 구성된 트리

종류

• 정이진트리 : 자식노드가 0개 or 2개
• 완전 이진 트리 : 왼쪽에서부터 채워진 트리
• 변질 이진 트리 : 자식노드가 1개
• 포화 이진 트리 : 모든 노드가 꽉 차있는 트리
• ⭐️ 균형 이진 트리 : 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차가 1이하
  • map, set을 구성하는 레드 블랙 트리는 균형 이진 트리

이진 탐색 트리(BST)

왼쪽 하위트리에는 노드보다 작은 값, 오른쪽 하위 트리에는 노드보다 큰 값이 있는 이진 트리

시간복잡도

O(logN)

단, 삽입 순서에 영향을 받는다
아래와 같이 선형 자료구조가 되면 O(N)이 되어버림

삽입순서가 어떻게 되든 균형잡히게 만든 이진탐색트리
-> AVL트리, 레드블랙트리