AVL 트리

• AVL 트리는 이진 탐색 트리의 한 종류로, 엄격하게 스스로 균형을 유지하는 트리이다.
• 각 노드의 균형 인수(balance factor, BF)를 사용하여 균형을 유지하며, 모든 노드의 BF 값은 -1, 0, 1 중 하나이다.
• 장점:
  • 트리의 높이가 O(log n)으로 유지되어, 검색, 삽입, 삭제 연산의 시간 복잡도가 O(log n)이다.
  • 균형을 유지하므로 최악의 경우에도 성능이 일정하다.
• 단점:
  • 엄격하게 균형을 유지하기 때문에 삽입/삭제 시 트리 균형을 확인한다.
  • 균형이 깨졌을 시 재조정하기 때문에 시간이 꽤 소요된다.

 

균형 인수 (Balance Factor)

• 임의의 노드 x에 대해 균형 인수는 x의 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다.
• BF(x) = x의 왼쪽 서브트리의 높이 - x의 오른쪽 서브트리의 높이
• 이 값이 -1, 0, 1 중 하나여야만 AVL 트리의 균형이 유지된다.

 

동작 방식

• 삽입: 새로운 노드를 트리에 삽입한 후, 이 노드가 추가된 위치에서부터 루트까지의 경로에 있는 모든 조상 노드들의 균형 인수를 업데이트한다. 균형 인수가 -1, 0, 1을 벗어나는 경우, 트리의 균형을 맞추기 위해 회전 연산을 수행한다.
• 삭제: 노드를 삭제한 후, 삭제된 노드의 자녀 노드와 그 조상 노드들에 대한 균형 인수를 업데이트한다. 필요에 따라 회전 연산을 통해 균형을 유지한다.

 

회전 연산

• 단일 회전 (Single Rotation):
  • 좌회전 (Left Rotation):
    • 상황: 오른쪽 서브트리가 비대칭적으로 높아진 경우.
    • 동작: 균형이 깨진 노드의 오른쪽 자식 노드를 새로운 루트로 올리고, 기존의 루트 노드를 왼쪽 자식으로 이동시킨다.
  • 우회전 (Right Rotation):
    • 상황: 왼쪽 서브트리가 비대칭적으로 높아진 경우.
    • 동작: 균형이 깨진 노드의 왼쪽 자식 노드를 새로운 루트로 올리고, 기존의 루트 노드를 오른쪽 자식으로 이동시킨다.
• 이중 회전 (Double Rotation):
  • 좌우 회전 (Left-Right Rotation):
    • 상황: 왼쪽 서브트리의 오른쪽 서브트리가 비대칭적으로 높아진 경우.
    • 동작: 먼저 왼쪽 자식에 대해 좌회전을 수행한 후, 전체 트리에 대해 우회전을 수행한다.
  • 우좌 회전 (Right-Left Rotation):
    • 상황: 오른쪽 서브트리의 왼쪽 서브트리가 비대칭적으로 높아진 경우.
    • 동작: 먼저 오른쪽 자식에 대해 우회전을 수행한 후, 전체 트리에 대해 좌회전을 수행한다.