이진탐색트리 - AVL트리

균형 이진 트리란?

모든 노드의 좌우 서브 트리 높이가 1이상 차이나지 않는 트리

이진 탐색 트리의 편향 발생 - 삽입 순서에 따라

• case1) 20 -> 10 -> 30 -> 5
• case2) 5 -> 10 -> 20 -> 30
  

균형 이진 탐색 트리(Balanced Binary Search Tree)란?

노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리
ex) AVL 트리, Red-Black 트리

AVL 트리

• 노드가 삽입, 삭제 될 때 트리의 균현을 체크하고 유지하는 트리
• 각 노드의 BF(Balanced Factor)를 [-1, 0, 1]만 가지게 하여 균형을 유지
• BF : (왼쪽 서브트리 높이) - (오른쪽 서브트리 높이)

AVL 트리 - 리벨런싱

• 균형이 깨진 경우
  • BF가 +이면 왼쪽 서브트리에 이상 있음
  • BF가 -이면 오른쪽 서브트리에 이상 있음
• 회전 연산을 통해 밸런스를 맞춘다.
  • 단순회전 : LL, RR
  • 이중회전 : LR, RL

리벨런싱 - LL 회전

• left-left 상황일 때 회전
• 오른쪽 방향으로 1회 회전
  

리벨런싱 - RR 회전

• right-right 상황일 때 회전
• 왼쪽 방향으로 1회 회전
  

리벨런싱 - LR 회전

• left-right 상황일 때 회전
• RR회전 후 LL회전 -> 회전 2회
  

리벨런싱 - RL 회전

• right-left 상황일 때 회전
• LL회전 후 RR회전 -> 회전 2회