균형 이진 탐색 트리(Balanced Binary Search Tree, BST)

• 균형 이진 트리 : 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리.
• 노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리.
• AVL트리, Red-Black트리

AVL트리

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

LL 회전 : 불균형이 왼쪽 서브트리에서 나타날 경우

우측 회전을 하여 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮겨줍니다.

RR 회전 : 불균형이 오른쪽 서브트리에서 나타날 경우

좌측 회전을 하여 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮겨줍니다.

LR 회전 : 불균형이 왼쪽 자식의 오른쪽 서브 트리에서 나타날 경우

1. 자식 노드에 대해 부모 노드를 좌측 회전 후
2. 조부모 노드를 우측 회전을 하여 부모 노드의 오른쪽 자식 노드 위치로 옮겨줍니다.

RL 회전 : 불균형이 오른쪽 자식의 왼쪽 서브 트리에서 나타날 경우

1. 자식 노드에 대해 부모 노드를 우측 회전 후
2. 조부모 노드를 좌측 회전을 하여 부모 노드의 왼쪽 자식 노드 위치로 옮겨줍니다.