1. AVL 트리

AVL 트리란 RBT와 마찬가지로 BST기반의 자료구조로, BST의 단점을 보완하기 위해 만들어졌다. 기존의 BST가 편향트리가 되는 worst case를 방지하기 위해 삽입, 삭제, 과정에서 “회전(rotation)”을 하여 “균형잡힌 이진트리”를 유지한다.

<aside> 💡 [BST의 특징]

• 이진트리니까 각 노드의 자식이 2개 이하
• 왼쪽<부모<오른쪽
• 중복된 노드가 없어야됨

→ AVL도 BST 기반이므로 BST의 특징을 가짐!

</aside>

2. AVL의 회전 - 4가지

• [참고] 균형인자 (Balance Factor) : 오른쪽 서브트리 높이 - 왼쪽 서브트리 높이

LL (Left Left)

부모노드와 피봇노드 모두 leftheavy일 때 ⇒ LL회전

RR (Right Right)

부모노드와 피봇노드 모두 rightheavy일 때 ⇒ RR회전

LR (Left Right)

부모노드는 rightheavy, 피봇노드는 leftheavy일 때 ⇒ L회전-R회전