C# 자료구조 :: 레드블랙트리

// 노드의 색을 나타내는 열거형(enum)
public enum NodeColor
{
    Red,
    Black
}

// 레드-블랙 트리에서 각 노드를 나타내는 Node 클래스
public class Node<T> where T : IComparable
{
    public T Value { get; set; } // 노드에 저장된 값
    public NodeColor Color { get; set; } // 노드의 색 (빨간색 또는 검정색)
    public Node<T> Left { get; set; } // 왼쪽 자식
    public Node<T> Right { get; set; } // 오른쪽 자식
    public Node<T> Parent { get; set; } // 부모 노드

    // 값으로 노드를 초기화하는 생성자, 기본 색상은 빨간색
    public Node(T value)
    {
        Value = value;
        Color = NodeColor.Red;
    }
}

 

//newNode가 current.Value보다 작으면

if(newNode.Value.CompareTo(current.Value) < 0)

public class RedBlackTree<T> where T : IComparable
{
    private Node<T> root; // 레드-블랙 트리의 루트

    // 레드-블랙 트리에 값을 삽입하는 메서드
    public void Insert(T value)
    {
        Node<T> newNode = new Node<T>(value); // 새 노드 생성
        if (root == null)
        {
            root = newNode;
            root.Color = NodeColor.Black; // 루트는 항상 검정색이어야 함
        }
        else
        {
            Insert(root, newNode); // 트리에 노드를 삽입
            FixInsert(newNode); // 삽입 후 트리의 레드-블랙 속성을 유지하도록 조정
        }
    }

    // 새로운 노드를 올바른 위치에 삽입하는 재귀 메서드
    private void Insert(Node<T> current, Node<T> newNode)
    {
        if (newNode.Value.CompareTo(current.Value) < 0)
        {
            if (current.Left == null)
            {
                current.Left = newNode;
                newNode.Parent = current;
            }
            else
            {
                Insert(current.Left, newNode);
            }
        }
        else
        {
            if (current.Right == null)
            {
                current.Right = newNode;
                newNode.Parent = current;
            }
            else
            {
                Insert(current.Right, newNode);
            }
        }
    }

    // 삽입 후 트리를 조정하여 레드-블랙 속성을 유지하는 메서드
    private void FixInsert(Node<T> node)
    {
        while (node != root && node.Parent.Color == NodeColor.Red)
        {
            if (node.Parent == node.Parent.Parent.Left)
            {
                Node<T> uncle = node.Parent.Parent.Right;
                if (uncle != null && uncle.Color == NodeColor.Red)
                {
                    node.Parent.Color = NodeColor.Black;
                    uncle.Color = NodeColor.Black;
                    node.Parent.Parent.Color = NodeColor.Red;
                    node = node.Parent.Parent;
                }
                else
                {
                    if (node == node.Parent.Right)
                    {
                        node = node.Parent;
                        RotateLeft(node);
                    }
                    node.Parent.Color = NodeColor.Black;
                    node.Parent.Parent.Color = NodeColor.Red;
                    RotateRight(node.Parent.Parent);
                }
            }
            else
            {
                Node<T> uncle = node.Parent.Parent.Left;
                if (uncle != null && uncle.Color == NodeColor.Red)
                {
                    node.Parent.Color = NodeColor.Black;
                    uncle.Color = NodeColor.Black;
                    node.Parent.Parent.Color = NodeColor.Red;
                    node = node.Parent.Parent;
                }
                else
                {
                    if (node == node.Parent.Left)
                    {
                        node = node.Parent;
                        RotateRight(node);
                    }
                    node.Parent.Color = NodeColor.Black;
                    node.Parent.Parent.Color = NodeColor.Red;
                    RotateLeft(node.Parent.Parent);
                }
            }
        }
        root.Color = NodeColor.Black;
    }

    // 트리의 균형을 맞추기 위한 좌회전
    private void RotateLeft(Node<T> node)
    {
        Node<T> right = node.Right;
        node.Right = right.Left;

        if (right.Left != null)
        {
            right.Left.Parent = node;
        }

        right.Parent = node.Parent;

        if (node.Parent == null)
        {
            root = right;
        }
        else if (node == node.Parent.Left)
        {
            node.Parent.Left = right;
        }
        else
        {
            node.Parent.Right = right;
        }

        right.Left = node;
        node.Parent = right;
    }

    // 트리의 균형을 맞추기 위한 우회전
    private void RotateRight(Node<T> node)
    {
        Node<T> left = node.Left;
        node.Left = left.Right;

        if (left.Right != null)
        {
            left.Right.Parent = node;
        }

        left.Parent = node.Parent;

        if (node.Parent == null)
        {
            root = left;
        }
        else if (node == node.Parent.Right)
        {
            node.Parent.Right = left;
        }
        else
        {
            node.Parent.Left = left;
        }

        left.Right = node;
        node.Parent = left;
    }

    // 레드-블랙 트리에서 값을 검색하는 메서드
    public bool Search(T value)
    {
        return Search(root, value);
    }

    // 트리에서 값을 검색하는 재귀 메서드
    private bool Search(Node<T> node, T value)
    {
        if (node == null)
        {
            return false;
        }

        int comparison = value.CompareTo(node.Value);
        if (comparison == 0)
        {
            return true;
        }
        else if (comparison < 0)
        {
            return Search(node.Left, value);
        }
        else
        {
            return Search(node.Right, value);
        }
    }
}