레드-블랙 트리의 개념 및 구현

레드-블랙 트리는 균형 이진 탐색 트리(Balanced Binary Search Tree) 중 하나로, 삽입과 삭제 과정에서 트리의 균형을 유지하기 위해 색상 속성을 활용하는 자료구조입니다. 이번 포스팅에서는 레드-블랙 트리의 개념, 동작 원리, 주요 규칙, 그리고 C# 구현을 통해 레드-블랙 트리를 상세히 알아보겠습니다.

---

1. 레드-블랙 트리란?

레드-블랙 트리는 노드에 레드(Red)와 블랙(Black)이라는 색상을 부여하여 트리의 균형을 유지하는 이진 탐색 트리입니다. 균형을 유지하기 위한 몇 가지 규칙을 기반으로 동작하며, 효율적인 삽입, 삭제, 검색 연산을 제공합니다.

---

1.1. 레드-블랙 트리의 특징

1. 시간 복잡도
   • 삽입, 삭제, 탐색 모두 O(log N)의 시간 복잡도를 가집니다.
2. 균형 유지 규칙
   레드-블랙 트리는 다음 다섯 가지 규칙을 따릅니다:
   • 모든 노드는 레드 또는 블랙 중 하나의 색을 가진다.
   • 루트 노드는 항상 블랙이다.
   • 모든 리프 노드(NIL)는 블랙이다.
   • 레드 노드의 자식 노드는 항상 블랙이다. (즉, 레드 노드는 연속될 수 없다.)
   • 모든 경로에서 리프 노드까지 가는 블랙 노드의 개수는 같다.

---

2. 레드-블랙 트리의 동작 원리

2.1. 삽입 연산

1. 새로운 노드를 레드로 삽입합니다.
2. 삽입 후 트리가 규칙을 위반하면 다음 중 하나의 재구성을 수행합니다:
   • 색상 변경 (Recoloring)
     부모와 삼촌 노드의 색을 변경하고, 할아버지 노드를 기준으로 다시 검사합니다.
   • 회전 (Rotation)
     LL, RR, LR, RL과 같은 트리 회전 연산을 통해 규칙을 복구합니다.

2.2. 삭제 연산

1. 삭제된 노드의 자리에 NIL 노드를 추가해 균형을 유지합니다.
2. 필요 시 재구성을 수행하여 트리 규칙을 유지합니다.

---

3. C#을 활용한 레드-블랙 트리 구현

3.1. 레드-블랙 노드 클래스

public enum NodeColor { Red, Black }

public class RedBlackNode<T> where T : IComparable
{
    public T Value { get; set; }
    public NodeColor Color { get; set; }
    public RedBlackNode<T> Left { get; set; }
    public RedBlackNode<T> Right { get; set; }
    public RedBlackNode<T> Parent { get; set; }

    public RedBlackNode(T value)
    {
        Value = value;
        Color = NodeColor.Red; // 새 노드는 항상 레드로 삽입
        Left = null;
        Right = null;
        Parent = null;
    }
}

---

3.2. 레드-블랙 트리 클래스

public class RedBlackTree<T> where T : IComparable
{
    private RedBlackNode<T> Root;

    // 삽입 연산
    public void Insert(T value)
    {
        var newNode = new RedBlackNode<T>(value);
        Root = Insert(Root, newNode);
        FixInsert(newNode);
    }

    private RedBlackNode<T> Insert(RedBlackNode<T> root, RedBlackNode<T> node)
    {
        if (root == null)
            return node;

        if (node.Value.CompareTo(root.Value) < 0)
        {
            root.Left = Insert(root.Left, node);
            root.Left.Parent = root;
        }
        else if (node.Value.CompareTo(root.Value) > 0)
        {
            root.Right = Insert(root.Right, node);
            root.Right.Parent = root;
        }

        return root;
    }

    // 삽입 후 균형 복구
    private void FixInsert(RedBlackNode<T> node)
    {
        while (node != Root && node.Parent.Color == NodeColor.Red)
        {
            var parent = node.Parent;
            var grandParent = parent.Parent;

            if (parent == grandParent.Left)
            {
                var uncle = grandParent.Right;

                // Case 1: 삼촌 노드가 레드
                if (uncle != null && uncle.Color == NodeColor.Red)
                {
                    parent.Color = NodeColor.Black;
                    uncle.Color = NodeColor.Black;
                    grandParent.Color = NodeColor.Red;
                    node = grandParent;
                }
                else
                {
                    // Case 2: 삼촌 노드가 블랙, LR 회전
                    if (node == parent.Right)
                    {
                        node = parent;
                        LeftRotate(node);
                    }
                    // Case 3: 삼촌 노드가 블랙, LL 회전
                    parent.Color = NodeColor.Black;
                    grandParent.Color = NodeColor.Red;
                    RightRotate(grandParent);
                }
            }
            else
            {
                var uncle = grandParent.Left;

                // Case 1: 삼촌 노드가 레드
                if (uncle != null && uncle.Color == NodeColor.Red)
                {
                    parent.Color = NodeColor.Black;
                    uncle.Color = NodeColor.Black;
                    grandParent.Color = NodeColor.Red;
                    node = grandParent;
                }
                else
                {
                    // Case 2: 삼촌 노드가 블랙, RL 회전
                    if (node == parent.Left)
                    {
                        node = parent;
                        RightRotate(node);
                    }
                    // Case 3: 삼촌 노드가 블랙, RR 회전
                    parent.Color = NodeColor.Black;
                    grandParent.Color = NodeColor.Red;
                    LeftRotate(grandParent);
                }
            }
        }

        Root.Color = NodeColor.Black;
    }

    // 좌회전
    private void LeftRotate(RedBlackNode<T> node)
    {
        var temp = node.Right;
        node.Right = temp.Left;

        if (temp.Left != null)
            temp.Left.Parent = node;

        temp.Parent = node.Parent;

        if (node.Parent == null)
            Root = temp;
        else if (node == node.Parent.Left)
            node.Parent.Left = temp;
        else
            node.Parent.Right = temp;

        temp.Left = node;
        node.Parent = temp;
    }

    // 우회전
    private void RightRotate(RedBlackNode<T> node)
    {
        var temp = node.Left;
        node.Left = temp.Right;

        if (temp.Right != null)
            temp.Right.Parent = node;

        temp.Parent = node.Parent;

        if (node.Parent == null)
            Root = temp;
        else if (node == node.Parent.Right)
            node.Parent.Right = temp;
        else
            node.Parent.Left = temp;

        temp.Right = node;
        node.Parent = temp;
    }

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

    private void InOrderTraversal(RedBlackNode<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 rbTree = new RedBlackTree<int>();

        rbTree.Insert(10);
        rbTree.Insert(20);
        rbTree.Insert(30);
        rbTree.Insert(15);
        rbTree.Insert(25);

        Console.WriteLine("In-order Traversal of Red-Black Tree:");
        rbTree.InOrderTraversal();
    }
}

---

3.4. 실행 결과

In-order Traversal of Red-Black Tree:
10 15 20 25 30

---

4. 레드-블랙 트리의 응용

• 데이터베이스 인덱싱
  빠른 검색과 업데이트를 보장하기 위해 사용됩니다.
• OS 메모리 관리
  가상 메모리 및 커널 데이터 구조에서 활용됩니다.
• 자바의 TreeMap 및 TreeSet
  내부적으로 레드-블랙 트리를 사용하여 데이터 정렬을 보장합니다.

---

 

레드-블랙 트리는 다양한 환경에서 사용되는 강력한 균형 이진 탐색 트리입니다.
레드-블랙 트리를 이해하면 데이터의 삽입, 삭제, 검색 연산의 효율성을 높이는 데 큰 도움을 줄 수 있습니다.