• Adelson-Velsky와 Landis가 개발한 자가 균형 이진 트리이다.
  • 기존 이진트리의 경우 한 쪽으로 노드가 쏠릴경우 시간복잡도가 증가하는 것을 볼 수 있는데 이를 보안한 것이 바로 AVL Tree이다.
• 왼쪽 노드와 오른쪽 노드의 높이 차가 최대 1이 넘지 않는다
• 회전(rotation)을 통해 양옆의 높이를 조율한다.
• 불균형 상황
  • LL(Left Left) : 왼쪽 노드의 왼쪽 노드로 치우친것
  • LR(Left Right) : 왼쪽 노드의 오른쪽 노드로 치우친것
  • RL(Right Left) : 오른쪽 노드의 왼쪽 노드로 치우친것
  • RR(Right Rightt) : 오른쪽 노드의 오른쪽 노드로 치우친것
• AVL 트리가 기존 Binary Search Tree(BST)에서 달라지는 점은 아래의 사항과 같다.
  • Node에 높이(height) 추가 : 균형을 판단하기 위해서
  • 불균형 감지와 회전 연산 구현3. 삽입과 삭제 시 트리의 불균형 판단 및 회전 연산