AVL 트리 (AVL Tree) 정리

공재원
∙∙조회 6

AVL 트리 (AVL Tree)

1. AVL 트리가 필요한 이유

일반 이진 탐색 트리(BST)는 데이터가 삽입되는 순서에 따라 한쪽으로 치우칠 수 있다.

예를 들어 정렬된 순서로 데이터를 삽입하면 트리가 한쪽으로 길게 늘어선 구조가 된다.

이 경우 트리의 높이가 노드 수에 가까워지며, 탐색 성능이 최악 O(n)까지 떨어진다. 사실상 연결 리스트와 비슷한 성능을 가지게 된다.

AVL 트리는 이러한 문제를 해결하기 위해 만들어진 균형 이진 탐색 트리이다.

핵심 아이디어

트리가 한쪽으로 치우쳐 균형이 깨지면 회전 연산을 통해 자동으로 구조를 재조정한다.

1962년 소련 수학자 Adelson-Velsky와 Landis가 제안했으며, 두 사람의 이름에서 AVL이라는 명칭이 유래했다.

2. AVL 트리의 핵심 규칙

Balance Factor (균형 인수)

Balance Factor(BF)는 특정 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 나타낸다.

계산 공식

BF = Height(Left) - Height(Right)

AVL 트리는 모든 노드의 BF가 -1, 0, +1 중 하나여야 한다.

즉, 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이어야 한다.

BF 해석

BF의미상태
+2 이상왼쪽이 지나치게 무거움불균형
+1왼쪽이 조금 더 높음균형
0양쪽 높이가 같음균형
-1오른쪽이 조금 더 높음균형
-2 이하오른쪽이 지나치게 무거움불균형

BF가 +2 이상이면 왼쪽 방향의 회전이 필요하고, -2 이하이면 오른쪽 방향의 회전이 필요하다.

3. 회전 연산 (Rotation)

회전은 트리의 연결 구조를 변경하면서도 이진 탐색 트리의 정렬 규칙을 유지하는 연산이다.

우회전 (Right Rotation)

왼쪽 자식 노드가 부모 노드의 위치로 올라오는 연산이다.

처리 순서

  1. 왼쪽 자식 노드의 오른쪽 자식을 임시로 보관한다.
  2. 왼쪽 자식 노드의 오른쪽에 기존 부모 노드를 연결한다.
  3. 기존 부모 노드의 왼쪽에 임시로 보관한 노드를 연결한다.
  4. 기존 부모 노드의 높이를 갱신한다.
  5. 새로운 부모 노드의 높이를 갱신한다.
  6. 새로운 루트 노드를 반환한다.

높이는 자식 노드부터 먼저 갱신한 다음 부모 노드를 갱신해야 한다.

좌회전 (Left Rotation)

우회전과 반대 방향으로 진행되는 연산이다.

오른쪽 자식 노드가 부모 노드의 위치로 올라온다.

처리 순서

  1. 오른쪽 자식 노드의 왼쪽 자식을 임시로 보관한다.
  2. 오른쪽 자식 노드의 왼쪽에 기존 부모 노드를 연결한다.
  3. 기존 부모 노드의 오른쪽에 임시로 보관한 노드를 연결한다.
  4. 기존 부모 노드의 높이를 갱신한다.
  5. 새로운 부모 노드의 높이를 갱신한다.
  6. 새로운 루트 노드를 반환한다.

회전의 핵심

회전은 노드의 위치만 바꾸는 것이 아니라 자식 노드의 연결 관계도 함께 변경한다.

이때 BST의 정렬 규칙은 유지되어야 한다.

또한 높이 갱신은 반드시 자식 노드부터 부모 노드 순서로 진행한다.

4. 불균형의 4가지 유형

AVL 트리는 불균형이 발생한 방향에 따라 네 가지 유형으로 구분한다.

LL (Left Left)

왼쪽 자식의 왼쪽 방향으로 무게가 쏠린 경우이다.

  • 불균형 노드의 BF는 +2이다.
  • 왼쪽 자식의 BF는 0 이상이다.
  • 해결 방법: 불균형 노드를 우회전한다.

RR (Right Right)

오른쪽 자식의 오른쪽 방향으로 무게가 쏠린 경우이다.

  • 불균형 노드의 BF는 -2이다.
  • 오른쪽 자식의 BF는 0 이하이다.
  • 해결 방법: 불균형 노드를 좌회전한다.

LR (Left Right)

왼쪽 자식의 오른쪽 방향으로 무게가 쏠린 경우이다.

해결 순서

  1. 왼쪽 자식 노드를 좌회전한다.
  2. 불균형 노드를 우회전한다.

먼저 한 번 회전하여 LL 형태로 변환한 다음 우회전한다.

RL (Right Left)

오른쪽 자식의 왼쪽 방향으로 무게가 쏠린 경우이다.

해결 순서

  1. 오른쪽 자식 노드를 우회전한다.
  2. 불균형 노드를 좌회전한다.

먼저 한 번 회전하여 RR 형태로 변환한 다음 좌회전한다.

4가지 유형 판별표

불균형 노드 BF자식 노드 BF유형해결 방법
+20 이상LL우회전
+20 미만LR왼쪽 자식 좌회전 → 우회전
-20 이하RR좌회전
-20 초과RL오른쪽 자식 우회전 → 좌회전

5. 삽입과 삭제 시 균형 조정

AVL 트리는 BST의 기본 삽입과 삭제 과정을 그대로 활용하면서, 작업이 끝난 뒤 균형을 다시 조정한다.

균형 조정 시점

재귀 방식으로 삽입과 삭제를 구현하면 재귀 호출이 끝나고 돌아오는 과정에서 각 노드를 다시 방문하게 된다.

이때 방문한 노드마다 Balance를 호출하여 높이와 BF를 확인하고 필요한 회전을 수행한다.

삽입 과정

  1. 일반 BST 방식으로 노드를 삽입한다.
  2. 재귀 호출이 반환되면서 부모 노드로 돌아온다.
  3. 현재 노드의 높이를 갱신한다.
  4. BF를 계산한다.
  5. 불균형이 발생했다면 적절한 회전을 수행한다.

삭제 과정

  1. 일반 BST 방식으로 노드를 삭제한다.
  2. 재귀 호출이 반환되면서 부모 노드로 돌아온다.
  3. 각 노드의 높이를 갱신한다.
  4. BF를 계산한다.
  5. 불균형이 발생한 노드를 재조정한다.

삭제는 하나의 노드를 제거한 뒤 여러 조상 노드의 균형이 연속해서 깨질 수 있으므로 반환 경로 전체에서 균형을 확인해야 한다.

삽입과 삭제의 차이

  • 삽입: 새로운 노드가 추가된 경로를 따라 균형을 확인한다.
  • 삭제: 노드가 제거된 경로를 따라 여러 위치에서 재균형이 필요할 수 있다.

6. 시간 복잡도

AVL 트리는 균형을 유지하므로 탐색, 삽입, 삭제의 시간 복잡도를 O(log n)으로 보장한다.

연산일반 BST 평균일반 BST 최악AVL
SearchO(log n)O(n)O(log n)
InsertO(log n)O(n)O(log n)
DeleteO(log n)O(n)O(log n)

장점

  • 트리의 균형을 자동으로 유지한다.
  • 탐색 성능을 O(log n)으로 보장한다.
  • 한쪽으로 치우친 트리가 만들어지는 것을 방지한다.

단점

  • 삽입과 삭제 과정에서 회전 연산이 필요하다.
  • 각 노드의 높이를 관리해야 한다.
  • 일반 BST보다 구현이 복잡하다.

AVL과 Red-Black Tree 비교

  • AVL Tree: 균형을 엄격하게 유지하므로 탐색이 빈번한 상황에 유리하다.
  • Red-Black Tree: AVL보다 균형 조건이 느슨하여 삽입과 삭제가 빈번한 상황에서 유리할 수 있다.

7. 프로젝트의 AVL 트리 구현

프로젝트에서는 기존 BinarySearchTree<TKey, TValue>를 상속하여 AVL 트리를 구현한다.

주요 메서드

  • BalanceFactor(): 노드의 BF를 계산한다.
  • Balance(): 노드의 높이를 갱신하고 균형 상태를 확인한다.
  • RotateLeft(): 좌회전을 수행한다.
  • RotateRight(): 우회전을 수행한다.
  • Add(): BST 방식으로 삽입한 뒤 균형을 조정한다.
  • Remove(): BST 방식으로 삭제한 뒤 균형을 조정한다.

상속을 사용하는 이유

AVL 트리는 기본 BST의 데이터 저장 및 탐색 구조를 그대로 활용한다.

따라서 기존 BST를 상속하면 다음 기능을 재사용할 수 있다.

  • TryGetValue
  • ContainsKey
  • 인덱서
  • Count
  • 트리 순회 기능

AVL 트리에서 추가로 구현할 핵심 기능은 삽입과 삭제 이후의 균형 조정이다.

이처럼 상속을 활용하면 기존 자료구조의 기능을 재사용하면서 필요한 기능만 확장할 수 있다.

8. 전체 구조 정리

AVL 트리는 일반 BST의 한쪽 쏠림 문제를 해결하기 위해 균형 규칙을 추가한 자료구조이다.

  • BST: 키의 크기에 따라 왼쪽과 오른쪽으로 데이터를 배치한다.
  • Height: 노드와 서브트리의 높이를 관리한다.
  • Balance Factor: 좌우 서브트리의 높이 차이를 계산한다.
  • Rotation: 불균형이 발생했을 때 트리 구조를 재조정한다.
  • Balance: 높이와 BF를 확인하고 필요한 회전을 수행한다.
  • Inheritance: 기존 BST 기능을 재사용하면서 AVL 기능을 확장한다.

핵심은 BST의 정렬 규칙을 유지하면서 모든 노드의 균형을 자동으로 관리하는 것이다.