AVL 트리는 **이진 탐색 트리(Binary Search Tree, BST)**의 일종으로, 각 노드의 높이 균형을 유지하는 **자기 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)**입니다.. AVL 트리는 삽입, 삭제, 검색 작업 시 시간 복잡도를 O(log n)으로 유지합니다.

특징

1. 균형 조건:
   • 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(균형 인수)가 -1, 0, 1 중 하나여야 합니다. 이를 높이 균형이라고 하며, 이 균형이 깨지면 트리가 스스로 균형을 맞추기 위해 회전 작업을 수행합니다.
2. 시간 복잡도:
   • AVL 트리는 항상 높이가 O(log n)으로 유지되므로, 삽입, 삭제, 검색 모두 O(log n)의 시간 복잡도를 가집니다.
3. 회전(Rotation):
   • 삽입 또는 삭제로 인해 트리의 균형이 깨질 때, 회전이라는 작업을 통해 트리의 균형을 복원합니다. 회전에는 단일 회전과 이중 회전이 있습니다.

회전 종류

• 단일 회전(Single Rotation):
  1. LL 회전: 노드가 왼쪽 자식의 왼쪽에 삽입되었을 때 발생하며, 오른쪽으로 회전하여 균형을 맞춥니다.
  2. RR 회전: 노드가 오른쪽 자식의 오른쪽에 삽입되었을 때 발생하며, 왼쪽으로 회전하여 균형을 맞춥니다.
• 이중 회전(Double Rotation):
  1. LR 회전: 노드가 왼쪽 자식의 오른쪽에 삽입되었을 때 발생하며, 먼저 왼쪽 자식을 왼쪽으로 회전하고, 그 후에 부모 노드를 오른쪽으로 회전합니다.
  2. RL 회전: 노드가 오른쪽 자식의 왼쪽에 삽입되었을 때 발생하며, 먼저 오른쪽 자식을 오른쪽으로 회전하고, 그 후에 부모 노드를 왼쪽으로 회전합니다.

AVL 트리의 주요 연산

1. 삽입:
   • 이진 탐색 트리 규칙에 따라 삽입한 후, 균형 인수를 확인하고 필요하다면 회전을 수행하여 균형을 유지합니다.
2. 삭제:
   • 노드를 삭제한 후에도 균형 인수를 확인하여 균형이 깨지면 회전을 통해 균형을 맞춥니다.
3. 검색:
   • 이진 탐색 트리와 동일하게 O(log n)의 시간 복잡도로 원하는 값을 검색할 수 있습니다.

AVL 트리의 장단점

• 장점:
  • 항상 높이가 균형을 이루므로, 최악의 경우에도 O(log n)의 시간 복잡도를 보장합니다.
• 단점:
  • 삽입 및 삭제 시 회전 작업으로 인해 추가 연산이 필요하므로, 일반적인 이진 탐색 트리보다 연산이 복잡할 수 있습니다.

AVL 트리 예시

    10                      30
   /  \\\\         =>          /  \\\\
  5    30                 10    40
      /  \\\\               /  \\\\
    25    40            5    25

위 예시에서, 노드 40을 삽입한 후 균형이 깨졌습니다. LL 회전을 통해 트리가 다시 균형을 맞춘 상태입니다.

AVL 트리는 이와 같이 삽입과 삭제 시 균형을 유지하여 트리의 성능을 항상 최적화된 상태로 유지하는 자료구조입니다.