Data Structure

AVL 트리의 개념 및 구현

Russell Developer 2024. 11. 19. 20:23

AVL 트리는 균형 이진 탐색 트리(Balanced Binary Search Tree)의 한 종류로, 트리의 균형을 유지하기 위해 고안된 자료구조입니다. 이번 포스팅에서는 AVL 트리의 개념, 주요 특징, 동작 원리, 그리고 C# 구현을 통해 AVL 트리를 자세히 알아보겠습니다.

1. AVL 트리란?

AVL 트리는 Adelson-Velsky와 Landis가 1962년에 제안한 자료구조로, 삽입과 삭제 작업 후 트리가 한쪽으로 치우치지 않도록 균형을 유지하는 이진 탐색 트리입니다. 균형을 유지하기 위해 AVL 트리는 균형 인수(Balance Factor)를 사용하여 트리의 불균형을 감지하고, 필요할 경우 회전 연산을 통해 재구성합니다.

2. AVL 트리의 동작 원리

AVL 트리는 데이터 삽입 및 삭제 시 균형 조건을 유지하도록 설계되었습니다.

2.1. 삽입 작업

삽입 작업이 완료된 후, 균형 인수를 계산하여 다음과 같은 회전 연산을 수행할 수 있습니다.

  • LL 회전 (Left-Left): 좌측 서브트리의 좌측 자식에 삽입된 경우
  • RR 회전 (Right-Right): 우측 서브트리의 우측 자식에 삽입된 경우
  • LR 회전 (Left-Right): 좌측 서브트리의 우측 자식에 삽입된 경우
  • RL 회전 (Right-Left): 우측 서브트리의 좌측 자식에 삽입된 경우

2.2. 삭제 작업

삭제 후에도 균형 인수를 확인하고, 불균형이 발생하면 회전 연산을 통해 트리를 재구성합니다.

 

트리의 특징

  1. 균형 조건
    • 모든 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하이어야 합니다.
    • 균형 인수(Balance Factor) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
  2. 시간 복잡도
    • 삽입, 삭제, 탐색 모두 O(log N)의 시간 복잡도를 가집니다.
  3. 회전 연산
    • 불균형을 복구하기 위해 단순 회전과 이중 회전을 사용합니다.

2. AVL 트리의 동작 원리

AVL 트리는 데이터 삽입 및 삭제 시 균형 조건을 유지하도록 설계되었습니다.

2.1. 삽입 작업

삽입 작업이 완료된 후, 균형 인수를 계산하여 다음과 같은 회전 연산을 수행할 수 있습니다.

  • LL 회전 (Left-Left): 좌측 서브트리의 좌측 자식에 삽입된 경우
  • RR 회전 (Right-Right): 우측 서브트리의 우측 자식에 삽입된 경우
  • LR 회전 (Left-Right): 좌측 서브트리의 우측 자식에 삽입된 경우
  • RL 회전 (Right-Left): 우측 서브트리의 좌측 자식에 삽입된 경우

2.2. 삭제 작업

삭제 후에도 균형 인수를 확인하고, 불균형이 발생하면 회전 연산을 통해 트리를 재구성합니다.

3. C#을 활용한 AVL 트리 구현

3.1. AVL 노드 클래스

public class AVLNode<T> where T : IComparable
{
    public T Value { get; set; }
    public AVLNode<T> Left { get; set; }
    public AVLNode<T> Right { get; set; }
    public int Height { get; set; }

    public AVLNode(T value)
    {
        Value = value;
        Left = null;
        Right = null;
        Height = 1; // 새 노드의 높이는 기본적으로 1
    }
}

 

3.2. AVL 트리 클래스

public class AVLTree<T> where T : IComparable
{
    private AVLNode<T> Root;

    // 노드 삽입
    public void Insert(T value)
    {
        Root = Insert(Root, value);
    }

    private AVLNode<T> Insert(AVLNode<T> node, T value)
    {
        if (node == null)
            return new AVLNode<T>(value);

        // 삽입 위치 결정
        if (value.CompareTo(node.Value) < 0)
            node.Left = Insert(node.Left, value);
        else if (value.CompareTo(node.Value) > 0)
            node.Right = Insert(node.Right, value);
        else
            return node; // 중복 값은 삽입하지 않음

        // 높이 갱신
        node.Height = 1 + Math.Max(GetHeight(node.Left), GetHeight(node.Right));

        // 균형 인수 계산
        int balance = GetBalanceFactor(node);

        // LL 회전
        if (balance > 1 && value.CompareTo(node.Left.Value) < 0)
            return RightRotate(node);

        // RR 회전
        if (balance < -1 && value.CompareTo(node.Right.Value) > 0)
            return LeftRotate(node);

        // LR 회전
        if (balance > 1 && value.CompareTo(node.Left.Value) > 0)
        {
            node.Left = LeftRotate(node.Left);
            return RightRotate(node);
        }

        // RL 회전
        if (balance < -1 && value.CompareTo(node.Right.Value) < 0)
        {
            node.Right = RightRotate(node.Right);
            return LeftRotate(node);
        }

        return node;
    }

    // 오른쪽 회전
    private AVLNode<T> RightRotate(AVLNode<T> y)
    {
        AVLNode<T> x = y.Left;
        AVLNode<T> T2 = x.Right;

        // 회전 수행
        x.Right = y;
        y.Left = T2;

        // 높이 갱신
        y.Height = Math.Max(GetHeight(y.Left), GetHeight(y.Right)) + 1;
        x.Height = Math.Max(GetHeight(x.Left), GetHeight(x.Right)) + 1;

        return x;
    }

    // 왼쪽 회전
    private AVLNode<T> LeftRotate(AVLNode<T> x)
    {
        AVLNode<T> y = x.Right;
        AVLNode<T> T2 = y.Left;

        // 회전 수행
        y.Left = x;
        x.Right = T2;

        // 높이 갱신
        x.Height = Math.Max(GetHeight(x.Left), GetHeight(x.Right)) + 1;
        y.Height = Math.Max(GetHeight(y.Left), GetHeight(y.Right)) + 1;

        return y;
    }

    private int GetHeight(AVLNode<T> node)
    {
        return node == null ? 0 : node.Height;
    }

    private int GetBalanceFactor(AVLNode<T> node)
    {
        return node == null ? 0 : GetHeight(node.Left) - GetHeight(node.Right);
    }

    // 중위 순회
    public void InOrderTraversal()
    {
        InOrderTraversal(Root);
        Console.WriteLine();
    }

    private void InOrderTraversal(AVLNode<T> node)
    {
        if (node != null)
        {
            InOrderTraversal(node.Left);
            Console.Write(node.Value + " ");
            InOrderTraversal(node.Right);
        }
    }
}

 

3.3. 실행 예시

public class Program
{
    public static void Main()
    {
        var avlTree = new AVLTree<int>();

        avlTree.Insert(10);
        avlTree.Insert(20);
        avlTree.Insert(30);
        avlTree.Insert(40);
        avlTree.Insert(50);
        avlTree.Insert(25);

        Console.WriteLine("In-order Traversal of AVL Tree:");
        avlTree.InOrderTraversal();
    }
}

 

3.4. 실행 결과

In-order Traversal of AVL Tree:
10 20 25 30 40 50

 

4. AVL 트리의 응용

  • 데이터베이스 인덱스
    데이터 검색 및 삽입 작업에서 성능을 극대화하기 위해 사용됩니다.
  • 네트워크 라우팅 테이블
    빠르고 효율적인 데이터 검색을 보장하기 위해 사용됩니다.
  • 사전 및 키 값 저장소
    키 기반 데이터 검색에 활용됩니다.

AVL 트리는 균형을 유지하여 최적의 성능을 보장하는 강력한 자료구조입니다. 이진 탐색 트리의 단점을 보완하면서도 트리의 균형을 유지하는 데 초점을 맞춘 AVL 트리는, 특히 데이터 삽입과 삭제가 빈번히 일어나는 상황에서 유용합니다.

저작자표시 비영리 변경금지