개념

1. bst 이면서 height-balanced tree(좌우 subtree height 차이 1보다 작거나 같음)
2. balance factor
   1. left subtree height - right subtree height
   2. avl tree --> 모든 balance factor -1, 0 , 1 중 하나임

추가 연산 --> minimal subtree root를 항상 동그라미 쳐서 헷갈리지 않게 해주기!

1. bst 추가 연산과 유사
2. 추가 후 balanced tree 조건 위배되면 --> balanced tree 되도록 수정
3. imbalance type --> minimal subtree root 기준으로!(제일 작은 서브트리 기준으로) ==> 반드시 root 잘 확인해서 root 기준으로 돌리는 거 잊지 않기!!(돌리는 거는 항상 root랑 root 바로 밑 트리임, 무엇을 돌리는지 헷갈리지 않기!!), 양 옆에 붙어 있는 노드의 위치는 그대로이고 가운데 있는 노드들의 위치는 변경 될 수 있음
   1. LL: left subtree의 left가 긴 경우
      1. root 기준으로 right-rotation
   2. LR
      1. left subtree 기준으로 left rotation
      2. root 기준으로 right rotation
   3. RL
      1. right subtree 기준으로 right
      2. root 기준으로 left
   4. RR
      1. root 기준으로 left-rotation