AVL

• 대표적인 균형 이진 탐색 트리

• 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이는 1이하임

  

  이진 검색 트리 + 균형 트리

• AVL은 노드 삽입/삭제가 일어났을때도 이러한 균형을 유지해야함

  • 이 균형을 유지하는 작업이 쉽지 않음

AVL이 아닌 사례

위 예시처럼 왼쪽과 오른쪽 서브트리의 높이 차이가 1인 경우가 AVL트리에 해당함

• AVL트리인 경우, 균형 인수의 경우는 딱 3가지임 (-1, 1, 0)
  • 다른 수가 계산됐다면, 그 트리는 AVL 트리가 아님

→ 각 불균형 유형별로 밸런스 맞추기 위한 회전 연산이 존재함

LL 유형

• 오른쪽으로 회전

RR 유형