균형 이진 탐색 트리의 개념 및 구현

균형 이진 탐색 트리(Balanced Binary Search Tree, BST)는 일반 이진 탐색 트리(Binary Search Tree)의 단점을 보완하여, 삽입, 삭제, 탐색 작업의 시간 복잡도를 O(log N)으로 유지할 수 있도록 설계된 자료구조입니다. 이번 포스팅에서는 균형 이진 탐색 트리의 개념, 종류, 동작 원리, 그리고 C# 구현을 통해 자세히 알아보겠습니다.

---

1. 균형 이진 탐색 트리란?

이진 탐색 트리(BST)는 왼쪽 서브트리에는 현재 노드보다 작은 값이, 오른쪽 서브트리에는 큰 값이 위치하는 계층적 자료구조입니다. 하지만 일반 BST는 삽입/삭제 시 트리가 한쪽으로 치우칠 가능성이 있어 최악의 경우 O(N) 시간 복잡도가 발생합니다.

1.1. 균형 조건

균형 이진 탐색 트리는 트리의 높이(height)가 최소화되도록 설계되었습니다.

• 균형 트리의 정의: 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지되는 트리.

---

2. 균형 이진 탐색 트리의 종류

1. AVL 트리
   • 이름: Adelson-Velsky and Landis 트리
   • 특성: 각 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 1을 초과하지 않도록 유지.
   • 회전 연산(삽입/삭제 시 필요): LL, RR, LR, RL
2. 레드-블랙 트리 (Red-Black Tree)
   • 특성: 노드가 빨강 또는 검정으로 칠해지며, 특정 규칙에 따라 트리가 균형을 유지.
   • 주로 C++ STL의 std::map 및 std::set에 활용.
3. B-트리
   • 다진 트리 구조로, 하나의 노드가 여러 자식을 가질 수 있음.
   • 데이터베이스와 파일 시스템에 주로 사용.

---

3. AVL 트리의 동작 원리

AVL 트리는 삽입, 삭제 시 자동으로 트리를 재구성하여 균형을 유지합니다.

3.1. 회전 연산

회전은 트리의 균형을 복구하는 데 사용되는 연산입니다.

• 단순 회전: LL(왼쪽-왼쪽), RR(오른쪽-오른쪽)
• 이중 회전: LR(왼쪽-오른쪽), RL(오른쪽-왼쪽)

3.2. 균형 인수

균형 인수(Balance Factor)는 노드의 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이로 계산됩니다.

• 균형 인수의 범위: -1, 0, 1

---

4. C# 구현: AVL 트리

4.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로 초기화
    }
}

 

---

4.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 balanceFactor = GetBalanceFactor(node);

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

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

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

        // RL 회전
        if (balanceFactor < -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);
        }
    }
}

 

---

4.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();
    }
}

 

---

4.4. 실행 결과

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

 

5. 균형 이진 탐색 트리의 응용 분야

1. 데이터베이스 인덱싱
   균형 트리는 빠른 데이터 검색을 보장하여 데이터베이스의 인덱스 구조로 자주 사용됩니다.
2. 파일 시스템
   파일 검색 속도를 높이기 위해 디렉토리 구조에서 활용됩니다.
3. 온라인 검색 엔진
   문자열 탐색 및 색인화를 빠르게 처리하기 위한 기본 구조로 사용됩니다.

---

균형 이진 탐색 트리는 데이터의 삽입, 삭제, 검색이 빈번히 일어나는 시스템에서 높은 성능을 보장하는 강력한 자료구조입니다. 특히, AVL 트리와 같은 균형 유지 메커니즘을 이해하면 데이터 구조 설계와 최적화에 큰 도움이 됩니다.