AVL Tree

• 노드가 삽입, 삭제될 떄 트리의 균형을 체크하고 유지하는 트리
• 각 노드의 BF를 [-1, 0 ,1] 만 가지게 하여 균형을 유지

BF(Balnce Factor)
왼쪽 서브트리 높이 - 오른쪽 서브트리 높이

리밸런싱(Rebalancing)

• 균형이 깨진 경우, BF가 +이면 왼쪽 서브트리에 이상이 있음
• 균형이 깨진 경우, BF가 -이면 오른쪽 서브트리에 이상이 있음

회전연산

Left Rotation

Right Rotation

LR (Left-Right Rotation)

RL (Right-Left Rotation)