이진트리

• 각각의 노드의 자식노드 수가 2개 이하로 구성되어있는 트리
  

• 완전이진트리 : 포화 이진 트리가 되기 직전

• 균형이진트리 : 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리
  => 높이차이가 2개 이상이면 안됨

이진 탐색 트리

• 오른쪽 하위 트리에는 '노드의 값보다 큰 값'을 가진다.

• 검색하기 유리하다.

• 이진탐색트리의 시간복잡도 : O(logN) ==> 균형잡힌 경우

  • 높이는 log(N-1) 특징을 가짐

• 이진탐색트리는 삽입 순서에 영향을 받음. => 노드들을 회전시켜 균형잡히게 만든다.

  • AVL트리 , 레드블랙트리

• 서브트리를 로테이트한다. [AVL트리]