트리의 회전과 AVL 트리

AVL 트리 

• 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이가 1 이상 차이나지 않는 높이 이진 균형 트리
• 검색 속도 O(log n), 삽입/삭제 연산 속도 O(log n)\
• 왜 필요한가 ?  : 완전 편향된 트리가 존재할 수 있기 때문에 조정 해주어야 함

다음과 같은 모양의 트리가 있다면, 비효율적인 탐색

 AVL 트리를 구현하기 위해서는 우선 회전에 대해 알아야 한다. 

회전

• 트리가 한쪽으로 치우친 불균형 상태를 해결하기 위해 노드의 연결 관계를 재배치하는 작업
• 트리의 높이를 조정하여, 탐색 시간의 시간 복잡도를 유지함
• 특성( 왼쪽 자식 < 부모 < 오른쪽 자식)을 유지함

회전의 종류

• LL 회전 ( Left - Left Rotation) : 왼쪽 서브트리의 왼쪽 자식에서 불균형 발생시 오른쪽으로 회전
• RR 회전 (Right- Right) : 오른쪽 서브트리의 오른쪽 자식에서 불균형 발생시 왼쪽으로 회전
• LR 회전(Left - Right) : 왼쪽 서브트리의 오른쪽 자식에서 불균형 발생시 왼쪽으로 회전 후 오른쪽 회전
• RL 회전 (Right -Left) : 오른쪽 서브트리의 왼쪽 자식에서 불균형 발생시 오른쪽으로 회전 후 왼쪽 회전

예시

1. LL 회전

과정 : 부모(10)을 기준으로 오른쪽으로 회전함

           새로운 루트 5를 설정
           원래 루트(10)은 5의 오른쪽 자식이 됨

 

2. RR 회전

 

과정 : 부모(10)을 기준으로 왼쪽으로 회전함
          새로운 루트 20을 설정

          원래 루트(10)은 20의 왼쪽 자식이 됨

 

 

3.LR 회전

과정 :  왼쪽 자식(5)를 기준으로 왼쪽 회전

            부모(10)을 기준으로 오른쪽 회전

 

4. RL 회전

과정 : 오른쪽 자식(20)을 기준으로 오른쪽 회전

           부모(10)을 기준으로 왼쪽 회전

// AVL 트리 클래스
public class AVLTree<T> where T : IComparable<T>
{
    private AVLNode<T> root; // 트리의 루트 노드

    // 1. 노드의 높이를 가져오는 헬퍼 함수
    private int GetHeight(AVLNode<T> node)
    {
        return node == null ? 0 : node.Height;
    }

    // 2. 노드의 균형 팩터를 계산하는 함수
    private int GetBalance(AVLNode<T> node)
    {
        return node == null ? 0 : GetHeight(node.Left) - GetHeight(node.Right);
    }

    // 3. 오른쪽으로 회전 (Left Rotation)
    private AVLNode<T> RotateRight(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; // 새로운 루트 반환
    }

    // 4. 왼쪽으로 회전 (Right Rotation)
    private AVLNode<T> RotateLeft(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; // 새로운 루트 반환
    }

    // 5. 노드 삽입
    public void Insert(T key)
    {
        root = InsertNode(root, key); // 루트 노드에서 시작
    }

    private AVLNode<T> InsertNode(AVLNode<T> node, T key)
    {
        // 기본 BST 삽입
        if (node == null)
        {
            return new AVLNode<T>(key); // 새 노드 생성
        }

        if (key.CompareTo(node.Key) < 0)
        {
            node.Left = InsertNode(node.Left, key);
        }
        else if (key.CompareTo(node.Key) > 0)
        {
            node.Right = InsertNode(node.Right, key);
        }
        else
        {
            return node; // 중복 키는 삽입하지 않음
        }

        // 높이 업데이트
        node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;

        // 균형 확인 및 조정
        int balance = GetBalance(node);

        // LL(Left-Left) 불균형: 오른쪽으로 회전
        if (balance > 1 && key.CompareTo(node.Left.Key) < 0)
        {
            return RotateRight(node);
        }

        // RR(Right-Right) 불균형: 왼쪽으로 회전
        if (balance < -1 && key.CompareTo(node.Right.Key) > 0)
        {
            return RotateLeft(node);
        }

        // LR(Left-Right) 불균형: 왼쪽 회전 후 오른쪽 회전
        if (balance > 1 && key.CompareTo(node.Left.Key) > 0)
        {
            node.Left = RotateLeft(node.Left);
            return RotateRight(node);
        }

        // RL(Right-Left) 불균형: 오른쪽 회전 후 왼쪽 회전
        if (balance < -1 && key.CompareTo(node.Right.Key) < 0)
        {
            node.Right = RotateRight(node.Right);
            return RotateLeft(node);
        }

        return node; // 균형이 맞아졌으므로 현재 노드 반환
    }

    // 6. 트리 출력 (디버깅용)
    public void PrintTree()
    {
        PrintTree(root, "", true);
    }

    private void PrintTree(AVLNode<T> node, string indent, bool last)
    {
        if (node != null)
        {
            Console.WriteLine(indent + (last ? "└─ " : "├─ ") + node.Key);
            indent += last ? "   " : "│  ";
            PrintTree(node.Left, indent, false);
            PrintTree(node.Right, indent, true);
        }
    }
}

전체적인 과정은, 새로운 노드를 추가하면 높이를 검사해서 그것이 어떤 상태인지(LL,RR,LR,RL) 검사하고

그에 맞는 회전을 주어 올바른 트리를 유지하는 것이다. 회전만 이해하면 AVL 트리 자체는 어렵지 않으니

자세한 설명은 넘어간다.