결과
이진 탐색 트리
1. 정의
2. 최악의 경우
Red-Black Tree
속성
C# 구현
유니티에서 구현시 주의 사항

결과

결과 미리보기입니다.😆

VS Code에서 내부적으로 Red Black Tree를 사용하고 있습니다. Text Editor 개발에 앞서 개념 이해와 제네릭한 구현을 먼저 진행합니다.
관심이 있으시면 한번 아래 링크를 클릭 해보세요.🥺
Challenging projects every programmer should try - Text Editor(3)

이진 탐색 트리

정말 오랜만에 자료구조 공부를 하게되어 어디서부터 접근해야할지 고민이 되었는데요.
트리라는 자료구조에 대해 안다고 생각하고 이진 탐색 트리부터 설명을 하겠습니다.

정의

001

각 노드에 값이 있다.
값들은 전순서가 있다.
노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

출처 - 위키백과

탐색 트리라고 해봤자 별 다른 내용이 있는게 아니라 부모 노드의 오른쪽 노드는 부모 노드보다 큰 값, 왼쪽 노드는 부모 노드보다 작은 값이 들어 있어
특정 값을 찾을 때 최선의 경우 예를들어 균형 트리나, 완전 이진 트리 같은 경우 O(log n)의 성능을 가집니다.

최악의 경우

트리 모양이 1자로 된 경우와 같이 최악의 경우에는 O(n)의 성능을 가집니다.

이러한 최악의 경우를 방지하기 위해 트리에서 추가나 제거시 자체적으로 밸런스를 유지하도록 구현할 수 있는데 이를 Self-balancing binary search tree라 합니다. 이러한 구현체 중 하나로 Red-Black Tree가 있습니다.

Red-Black Tree

속성

002

Red-Black Tree는 위에서 정의한 조건에 추가적인 조건이 추가됩니다.

노드는 레드 혹은 블랙 중의 하나이다.
모든 리프 노드들(NIL)은 블랙이다.
레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
(결론) 노드 N이 정확히 하나의 자식을 가지고 있다면, 그 자식은 빨간색이어야 합니다. 만약 그 자식이 검은색이라면, 그 NIL 후손들은 N의 NIL 자식과 다른 검은 깊이에 위치하게 되어 규칙 4를 위반하게 됩니다.

이 속성에 대해서 영어 문서와 한글 문서가 다르게 되어 있습니다.
한글 문서에서는 “2번에 루트 노드는 블랙이다.”로 되어 있는데 영어 문선에서는 이러한 말이 따로 없습니다. 영어 출처 - 위키백과
한국어 출처 - 위키백과
이 차이는 루트 노드만 존재할 때 차이가 있습니다.
저는 영어 문서 기준으로 구현을 진행하도록 하겠습니다.

Some authors, e.g. Cormen & al.,[18] claim “the root is black” as fifth requirement but not Mehlhorn & Sanders[17] or Sedgewick & Wayne.[16]: 432–447 Since the root can always be changed from red to black, this rule has little effect on analysis. This article also omits it, because it slightly disturbs the recursive algorithms and proofs.

제 블로그뿐만 아니라 다른 블로그도 같이 보시는 분들은 주의해주세요!

C# 구현

위키를 참고하여 작성하였습니다. C#으로 goto 문을 사용하지 않고 구현해보았습니다.
수정이 필요한 부분이 보이면 말씀 부탁드립니다.😐

노드

다양하게 확장해서 사용하기 위해 Generic Class로 구현하였습니다.

public static class Constants
{
    public static readonly int LEFT = 0;
    public static readonly int RED = 0;
    public static readonly int RIGHT = 1;
    public static readonly int BLACK = 1;
}

public class Node<T> where T : IComparable
{
    public Node<T> Parent { get; set; }

    public Node<T>[] Child { get; set; }
    public int Color { get; set; }
    public T Value { get; set; }

    public Node()
    {
        Child = new Node<T>[2];
        Color = RED;
    }

    public Node<T> Left
    {
        get 
        { 
            return Child[LEFT]; 
        }
        set 
        {
            Child[LEFT] = value; 
        }
    }

    public Node<T> Right
    {
        get
        {
            return Child[RIGHT];
        }
        set
        {
            Child[RIGHT] = value;
        }
    }

    public void SwapValue(Node<T> node)
    {
        (Value, node.Value) = (node.Value, Value);
    }
}

Operation

추가와 삭제 구현을 하기전에 일부 동작들을 미리 구현해줍니다.

회전

003 By Nomen4Omen - Own work, CC BY-SA 3.0 de, Link

회전 동작을 먼저 구현하여 이후 추가나 삭제 동작에서 사용할 수 있습니다. 하나의 함수로 만들 수 있습니다.

/// <summary>
/// 회전
/// <para>
/// https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
/// </para>
/// </summary>
/// <param name="x">서브 트리의 루트 노드</param>
/// <param name="dir">회전 방향</param>
private Node<T> Rotate(Node<T> exRoot, int dir)
{
    Node<T> parent = exRoot.Parent;
    Node<T> newRoot = exRoot.Child[1 - dir];

    // 새 루트 노드가 없으면 회전 X
    if (newRoot == null)
    {
        return exRoot;
    }

    // 자식 교환
    exRoot.Child[1 - dir] = newRoot?.Child[dir];
    if (exRoot.Child[1 - dir] != null)
    {
        exRoot.Child[1 - dir].Parent = exRoot;
    }

    // 루트 변경
    newRoot.Child[dir] = exRoot;
    exRoot.Parent = newRoot;

    // 서브 트리의 부모 노드와 연결
    newRoot.Parent = parent;
    if (parent != null)
    {
        parent.Child[exRoot == parent.Child[dir] ? dir : 1 - dir] = newRoot;
    }
    else
    {
        Root = newRoot;
    }

    return newRoot;
}

가장 왼쪽에 있는 자식 노드 찾기

private Node<T> GetLeftmostChild(Node<T> node)
{
    if (node.Left == null)
        return node;
    else
        return GetLeftmostChild(node.Left);
}

노드 검색

private bool Search(Node<T> node, T value, out Node<T> found, out Node<T> parent)
{
    if (node.Value.CompareTo(value) == 0)
    {
        found = node;
        parent = node.Parent;
        return true;
    }
    else if (node.Value.CompareTo(value) > 0)
    {
        if (node.Left == null)
        {
            found = null;
            parent = node;
            return false;
        }
        else
        {
            return Search(node.Left, value, out found, out parent);
        }
    }
    else
    {
        if (node.Right == null)
        {
            found = null;
            parent = node;
            return false;
        }
        else
        {
            return Search(node.Right, value, out found, out parent);
        }
    }
}

노드 추가

004 출처 - 위키백과

위의 표를 통해 아래와 같이 구현할 수 있습니다.

public void Insert(T value)
{
    if (Root == null)
    {
        var node = new Node<T> 
        { 
            Value = value
        };
        Root = node;
        return;
    }

    if (Search(Root, value, out _, out Node<T> parent))
    {
        // 중복
        return;
    }
    else
    {
        var node = new Node<T>
        {
            Value = value
        };

        if (parent.Value.CompareTo(node.Value) > 0)
        {
            node.Parent = parent;
            parent.Left = node;
        }
        else
        {
            node.Parent = parent;
            parent.Right = node;
        }

        RebalanceAfterInsertion(node, node.Parent);

        return;
    }
}

private void RebalanceAfterInsertion(Node<T> node, Node<T> parent)
{
    // case 1
    // parent is black
    if (parent.Color == BLACK)
    {
        return;
    }
    else
    {
        Node<T> grandparent = parent.Parent;
        // case 4
        // parent is root
        if (grandparent == null)
        {
            parent.Color = BLACK;
            return;
        }

        var dir = grandparent.Left == parent ? LEFT : RIGHT;
        Node<T> uncle = grandparent.Child[1 - dir];
        if (uncle == null || uncle.Color == BLACK)
        {
            // case 5
            // inner grandchild
            if (node == parent.Child[1 - dir])
            {
                Rotate(parent, dir);
                node = parent;
                parent = grandparent.Child[dir];
                // fall through to case 6
            }
            // case 6
            // outer grandchild
            Rotate(grandparent, 1 - dir);
            parent.Color = BLACK;
            grandparent.Color = RED;
            return;
        }

        // case 2
        parent.Color = BLACK;
        uncle.Color = BLACK;
        grandparent.Color = RED;
        node = grandparent;

        var newParent = node.Parent;
        if (newParent != null)
        {
            RebalanceAfterInsertion(node, newParent);
        }

        // case 3
        // n is root and red
        return;
    }
}

노드 삭제

005 출처 - 위키백과

위의 표를 통해 아래와 같이 구현할 수 있습니다.
영어 주석들은 위키에서 참고한 문구를 가리킵니다.

public void Delete(T value)
{
    if (Root == null)
    {
        return;
    }

    if (Search(Root, value, out Node<T> found, out _))
    {
        DeleteNode(found);
        return;
    }
}

private void DeleteNode(Node<T> node)
{
    // When the deleted node has 2 children (non-NIL), 
    // then we can swap its value with its in-order successor (the leftmost child of the right subtree), 
    // and then delete the successor instead. 
    // Since the successor is leftmost, it can only have a right child (non-NIL) or no child at all.
    if (node.Left != null && node.Right != null)
    {
        var leftmostChild = GetLeftmostChild(node.Right);
        node.SwapValue(leftmostChild);
        DeleteNode(leftmostChild);
        return;
    }
    else if (node.Left == null && node.Right == null)
    {
        var parent = node.Parent;
        // When the deleted node has no children (both NIL) and is the root, 
        // replace it with NIL. The tree is empty.
        if (parent == null)
        {
            Root = null;
            return;
        }

        // When the deleted node has no children (both NIL), and is red, 
        // simply remove the leaf node.
        var dir = parent.Left == node ? LEFT : RIGHT;
        parent.Child[dir] = null;
        if (node.Color == RED)
        {
            return;
        }

        // When the deleted node has no children (both NIL), and is black, 
        // deleting it will create an imbalance, and requires a fixup, as covered in the next section.
        DeleteWhileLooping(parent, dir);
        return;
    }
    else
    {
        // When the deleted node has only 1 child (non-NIL). In this case, 
        // just replace the node with its child, and color it black.
        // The single child(non - NIL) must be red according to conclusion 5, 
        // and the deleted node must be black according to requirement 3.

        var childDir = node.Left != null ? LEFT : RIGHT;
        node.Child[childDir].Parent = node.Parent;

        if (node.Parent == null)
        {
            Root = node.Child[childDir];
        }
        else
        {
            var parentDir = node.Parent.Left == node ? LEFT : RIGHT;
            node.Parent.Child[parentDir] = node.Child[childDir];
        }

        node.Child[childDir].Color = BLACK;
        return;
    }
}

private void DeleteWhileLooping(Node<T> parent, int dir)
{
    // case 1
    // 코드 상으로만 존재??
    if (parent == null)
        return;

    // S cannot be a NIL node in the first iteration, 
    // because it must have black height one, which was the black height of N before its deletion, 
    // but C and D may be NIL nodes
    var sibling = parent.Child[1 - dir];
    var distantNephew = sibling.Child[1 - dir];
    var closeNephew = sibling.Child[dir];

    // case 3
    if (sibling.Color == RED)
    {
        D3(parent, sibling, closeNephew, dir);
        return;
    }

    // case 6
    // D red && S black:
    if (distantNephew != null && distantNephew.Color == RED)
    {
        D6(parent, sibling, distantNephew, dir);
        return;
    }

    // case 5
    if (closeNephew != null && closeNephew.Color == RED)
    {
        D5(parent, sibling, closeNephew, dir);
        return;
    }

    // case 4
    // P red && S+C+D black:
    if (parent.Color == RED)
    {
        D4(parent, sibling);
        return;
    }

    // case 2
    // Case_D2 (P+C+S+D black):
    sibling.Color = RED;
    var node = parent;
    parent = node.Parent;
    if (parent != null)
    {
        dir = parent.Left == node ? LEFT : RIGHT;
        DeleteWhileLooping(parent, dir);
    }

    return;
}

private void D3(Node<T> parent, Node<T> sibling, Node<T> closeNephew, int dir)
{
    Rotate(parent, dir);
    parent.Color = RED;
    sibling.Color = BLACK;
    sibling = closeNephew; // != NIL
    // now: P red && S black
    var distantNephew = sibling!.Child[1 - dir]; // distant nephew

    // case 6
    // D red && S black:
    if (distantNephew != null && distantNephew.Color == RED)
    {
        D6(parent, sibling, distantNephew, dir);
        return;
    }

    closeNephew = sibling.Child[dir]; // close nephew
    // case 5
    if (closeNephew != null && closeNephew.Color == RED)
    {
        D5(parent, sibling, closeNephew, dir);
        return;
    }

    // Otherwise C+D considered black.
    // fall through to Case_D4
    // case 4
    // P red && S+C+D black:
    if (parent.Color == RED)
    {
        D4(parent, sibling);
        return;
    }
}

private void D6(Node<T> parent, Node<T> sibling, Node<T> distantNephew, int dir)
{
    Rotate(parent, dir);
    sibling.Color = parent.Color;
    parent.Color = BLACK;
    distantNephew.Color = BLACK;
    return;
}

private void D5(Node<T> parent, Node<T> sibling, Node<T> closeNephew, int dir)
{
    Rotate(sibling, 1 - dir);
    sibling.Color = RED;
    closeNephew.Color = BLACK;
    var distantNephew = sibling;
    sibling = closeNephew;
    // now: D red && S black
    // fall through to Case_D6
    D6(parent, sibling, distantNephew, dir);
    return;
}

private void D4(Node<T> parent, Node<T> sibling)
{
    sibling.Color = RED;
    parent.Color = BLACK;
    return;
}

유니티에서 구현시 주의 사항

유니티에서는 MonoBehaviour를 상속 받는 클래스는 Generic 클래스로 사용할 수 없습니다.
따라서 Wrapping을 하던가 타입을 정해서 사용해주어야 합니다.

최종 결과는 페이지 맨 위에 있습니다.😆
결과

Red-Black_Tree

BST

← Previous Post