AVL-Tree는 BST가 최악의 경우 linked-list 처럼 이어저 $O(n)$의 시간복잡도의 성능을 보여준다는 단점을 보완하는 tree이다.

N개의 노드에 대해 AVL Tree는 $O(logN)$의 효율을 보인다.

tree에 새로운 node를 insert, delete 할 때 마다 보정작업이 필요

• 보정이 필요한 상황인지 어떻게 파악? → 정상과 비정상을 어떻게 빠르게 파악할 수 있는지가 키 포인트

AVL-Tree 정의

이진 검색 트리(BST)이면서 동시에 균형을 유지하고 있다.

모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하이다.

(모든 노드들은 balance factor을 알고 있음)

균형을 유지하고 있기 때문에 이진 검색시의 효율성 $O(logN)$을 보장함

각 Node는 두 가지 label 정보를 포함하게 되는데, 각각 L과 R이라고 부른다.

<aside> 📌 L : Height of Left subtree

R : Height of Right subtree

Balance Factor: L - R

Condition: $|L - R| < 2$ 즉, $L - R$은 -1, 0, 1 중 하나여야한다.

</aside>

Rotation

• 문제는 균형을 맞추기 위한 유지 방법이 복잡함.
  • 삽입 /삭제로 인해 좌우측 height의 계산 결과가 2 이상이 되면, rotation 시켜줘야함
• rotation에는 2가지 관점이 있음
  • AVL 트리를 height balance 유지
  • Binary Search Tree로 유지