레드-블랙 트리 (Red-Black Tree)

레드-블랙 트리(Red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 레드-블랙 트리는 이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다.

Balanced Search Tree로 많이 쓰이는 Red-Black Tree(이하 RB Tree)를 C 언어로 구현.
구현하는 추상 자료형(Abstract Data Type)은 ordered set, multiset.

구현 범위

1. tree = new_tree(): RB Tree 구조체 생성
2. delete_tree(tree): RB Tree 구조체가 차지했던 메모리 반환
3. tree_insert(tree, key): key 추가
4. ptr = tree_find(tree, key): RB Tree 내 해당 key가 있는지 탐색하여 있으면 node pointer 반환; 없으면 NIL 반환
5. tree_erase(tree, ptr): ptr로 지정된 node 삭제 및 메모리 반환
6. ptr = tree_min(tree): RB Tree 중 최소값을 가진 node pointer 반환
7. ptr = tree_max(tree): RB Tree 중 최대값을 가진 node pointer 반환
8. tree_to_array(tree, array, n): RB Tree의 내용을 key 순서대로 주어진 array 반환; array의 크기는 n으로 주어지며 tree의 크기가 n보다 큰 경우에는 순서대로 n개 까지만 반환

레드-블랙 트리의 구조

A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color, red or black.

These colors are used to ensure that the tree remains balanced during insertions and deletions.

Rules that every red-black tree follows:
1. Every node has a color either red or black.
2. The root of the tree is always black.
3. There are no adjacent red nodes (A red node cannot have a red parent or red child.
4. Every path from a node (including root) to any of its descendants NULL nodes has the same number of black nodes.

레드-블랙 트리의 특성

1. 루트 노드에서 리프 노드로 가는 경로의 검은 노드의 수는 모두 같다.
2. 새로 삽입되는 노드는 리프 노드에 위치하며 붉은 노드이다.
3. 부모의 두 자식 노드가 모두 붉은 노드이면 부모를 빨간색 노드로 바꾸고 자식은 검은 노드로 바꿀 수 있다.
4. 붉은 노드는 자식이 없거나 있다면 두 개의 검은 노드이다.
5. 검은 노드는 자식이 없거나 있다면 하나의 붉은 노드나 두 개의 붉은 노드나 두 개의 검은 노드이다. 즉, 단 하나의 검은 노드를 가질 수 없다.

레드-블랙 트리의 동작

1. 상향 색 변환 (Color Promotion)

부모 노드의 두 자식 노드가 모두 붉은 노드이면 부모 노드를 붉은 노드로 바꾸고 자식 노드는 검은 노드로 바꿀 수 있다.

2. 하향 색 변환 (Color Demotion)

부는 노드가 붉은 노드이면 부모 노드를 검은 노드로 바꾸고 자식 노드를 붉은 노드로 바꿀 수 있다.

3. 우회전 (Right Rotation)

4. 좌회전 (Left Rotation)

레프트 로테이션의 핵심은 y의 왼쪽 자식 노드가 x의 오른쪽 자식 노드가 되는 것이다.

x의 오른쪽 자식 노드가 된 y의 부모 노드를 변경한다.

레드-블랙 트리의 삽입 (Insertion)

삽입 알고리즘

1. 왼쪽 서브트리 < 부모 노드 < 오른쪽 서브트리 규칙에 의해 하향 탐색
2. 하향 탐색을 하면서 상향 색 변환. (붉은 노드가 연속될 경우 회전한다.)
3. 리프 노드에 도달하면 붉은 노드로 자료를 삽입한다. (붉은 노드가 연속될 경우 회전한다.)

여섯 가지 경우의 수 존재
세 가지 경우는 z의 부모 노드가 왼쪽 자식 노드인 경우, 세 가지는 z의 부모 노드가 오른쪽 자식 노드인 경우

z의 부모 노드가 왼쪽 자식 노드일 때

첫번째 경우는 부모와 삼촌 노드가 모두 붉은 노드
붉은 노드를 위로 이동시킨다. 루트 노드까지 이동하면 검은 노드로 바꿔준다.

두번째 경우는 삼촌 노드가 검은 노드이고 z가 오른쪽 자식 노드인 경우
세번째 경우는 삼촌 노드가 검은 노드이고 z가 왼쪽 자식 노드인 경우

두번째 경우에서 레프트 로테이션을 하면 세번째 경우와 같아진다.

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    struct node *parent;
    struct node *left;
    struct node *right;
    int data;
    int color;
} node;

typedef struct rbtree
{
    node *root;
    node *NIL;
} rbtree;

node *new_node(int data)
{
    node *n = malloc(sizeof(node));

    n->parent = NULL;
    n->left = NULL;
    n->right = NULL;
    n->data = data;
    n->color = 1;

    return n;
}

rbtree *new_rbtree()
{
    rbtree *t = malloc(sizeof(rbtree));
    node *nil_node = malloc(sizeof(node));

    nil_node->parent = NULL;
    nil_node->left = NULL;
    nil_node->right = NULL;
    nil_node->data = 0;
    nil_node->color = 0;
    t->NIL = nil_node;
    t->root = t->NIL;

    return t;
}

void left_rotation(rbtree *t, node *x)
{
    // x의 오른쪽 자식 노드 y 선언
    node *y = x->right;

    // y의 왼쪽 자식 노드를 x의 오른쪽 자식 노드로 변경
    x->right = y->left;

    // y의 왼쪽 자식 노드가 NIL 노드가 아니면 y의 왼쪽 자식 노드의 부모 노드를 x로 변경
    if (y->left != t->NIL)
        y->left->parent = x;

    // y의 부모 노드를 x의 부모 노드로 변경
    y->parent = x->parent;

    // x의 부모 노드가 NIL 노드이면 트리의 루트 노드를 y로 변경
    if (x->parent == t->NIL)
        t->root = y;
    // x가 부모 노드의 왼쪽 자식 노드이면 x의 부모 노드의 왼쪽 자식 노드를 y로 변경
    else if (x == x->parent->left)
        x->parent->left = y;
    // x가 부모 노드의 오른쪽 자식 노드이면 x의 부모 노드의 오른쪽 자식 노드를 y로 변경
    else
        x->parent->right = y;

    // y의 왼쪽 자식 노드를 x로 변경
    y->left = x;
    // x의 부모 노드를 y로 변경
    x->parent = y;
}

void right_rotation(rbtree *t, node *x)
{
    // x의 왼쪽 자식 노드 y 선언
    node *y = x->left;

    // y의 오른쪽 자식 노드를 x의 왼쪽 자식 노드로 변경
    x->left = y->right;

    // y의 오른쪽 자식 노드가 NIL 노드가 아니면 y의 오른쪽 자식 노드의 부모 노드를 x로 변경
    if (y->right != t->NIL)
        y->right->parent = x;

    // y의 부모 노드를 x의 부모 노드로 변경
    y->parent = x->parent;

    // x의 부모 노드가 NIL 노드이면 트리의 루트 노드를 y로 변경
    if (x->parent == t->NIL)
        t->root = y;
    // x가 x의 부모 노드의 왼쪽 자식 노드이면 x의 부모 노드의 왼쪽 자식 노드를 y로 변경
    else if (x == x->parent->left)
        x->parent->left = y;
    // x가 x의 부모 노드의 오른쪽 자식 노드이면 x의 부모 노드의 오른쪽 자식 노드를 y로 변경
    else
        x->parent->right = y;

    // y의 오른쪽 자식 노드를 x로 변경
    y->right = x;
    // x의 부모 노드를 y로 변경
    x->parent = y;
}

void insertion_fixup(rbtree *t, node *z)
{
    // z의 부모 노드가 붉은 노드인 경우
    while (z->parent->color == 1)
    {
        // z의 부모 노드가 왼쪽 자식 노드인 경우
        if (z->parent == z->parent->parent->left)
        {
            // z의 오른쫀 삼촌 노드 y 선언
            node *y = z->parent->parent->right;

            // 삼촌 노드 y가 붉은 노드인 경우
            if (y->color == 1)
            {
                // z의 부모 노드를 검은 노드로 변환
                z->parent->color = 0;
                // z의 삼촌 노드 y를 검은 노드로 변환
                y->color = 0;
                // z의 조부모 노드를 붉은 노드로 변환
                z->parent->parent->color = 1;
                // z를 z의 조부모 노드로 변경
                z = z->parent->parent;
            }
            else
            {
                // z가 부모 노드의 오른쪽 자식인 경우
                if (z == z->parent->right)
                {
                    // z에 z의 부모 노드 저장
                    z = z->parent;
                    // 레프트 로테이션 실행
                    left_rotation(t, z);
                }
                // z의 부모 노드를 검은 노드로 변환
                z->parent->color = 0;
                // z의 조부모 노드를 붉은 노드로 변환
                z->parent->parent->color = 1;
                // 라이트 로테이션 실행
                right_rotation(t, z->parent->parent);
            }
        }
        // z의 부모 노드가 오른쪽 자식 노드인 경우
        else
        {
            // z의 왼쪽 삼촌 노드 y 선언
            node *y = z->parent->parent->left;

            if (y->color == 1)
            {
                // z의 부모 노드를 검은 노드로 변환
                z->parent->color = 0;
                // z의 삼촌 노드 y를 검은 노드로 변환
                y->color = 0;
                // z의 조부모 노드를 붉은 노드로 변환
                z->parent->parent->color = 1;
                // z를 z의 조부모 노드로 변경
                z = z->parent->parent;
            }
            else
            {
                // z가 부모 노드의 왼쪽 자식 노드인 경우
                if (z == z->parent->left)
                {
                    // z에 z의 부모 노드 저장
                    z = z->parent;
                    // 라이트 로테이션
                    right_rotation(t, z);
                }
                // z의 부모 노드를 검은 노드로 변환
                z->parent->color = 0;
                // z의 조부모 노드를 붉으 노드로 변환
                z->parent->parent->color = 1;
                // 레프트 로테이션 실행
                left_rotation(t, z->parent->parent);
            }
        }
    }
    // 트리의 루트 노드롤 검은 노드로 변환
    t->root->color = 0;
}

void insertion(rbtree *t, node *z)
{
    // 트리의 NIL인 노드 y 선언
    node *y = t->NIL;
    // 트리의 루트 노드 temp 선언
    node *temp = t->root;

    // temp가 트리의 NIL이 아니면 반복문 실행
    while (temp != t->NIL)
    {
        // y는 temp를 저장
        y = temp;
        // z의 data가 temp의 data보다 작으면 temp에 temp의 왼쪽 자식 노드 저장
        if (z->data < temp->data)
            temp = temp->left;
        // z의 data가 temp의 data보다 크면 temp에 temp의 오른쪽 자식 노드 저장
        else
            temp = temp->right;
    }

    // z의 부모 노드를 y로 변경
    z->parent = y;

    // y는 트리의 NIL이면 트리의 루트 노드를 z로 변경
    if (y == t->NIL)
        t->root = z;
    // z의 data가 y의 data보다 작으면 y의 왼쪽 자식 노드를 z로 변경
    else if (z->data < y->data)
        y->left = z;
    // z의 data가 y의 data보다 크면 y의 오른쪽 자식 노드를 z로 변경
    else
        y->right = z;

    // z의 왼쪽 자식 노드를 트리의 NIL로 변경
    z->left = t->NIL;
    // z의 오른쪽 자식 노드를 트리의 NIL로 변경
    z->right = t->NIL;
    // z의 색깔을 빨강으로 변경
    z->color = 1;

    insertion_fixup(t, z);
}

void inorder(rbtree *t, node *n)
{
    // 노드 n이 트리의 NIL이 아니면 n의 왼쪽 자식 노드를 출력 후 오른쪽 자식 노드를 출력
    if (n != t->NIL)
    {
        inorder(t, n->left);
        printf("%d \n", n->data);
        inorder(t, n->right);
    }
}

int main()
{
    // 새로운 레드-블랙 트리 생성
    rbtree *t = new_rbtree();

    node *a, *b, *c, *d, *e, *f, *g, *h, *i, *j, *k, *l, *m;

    a = new_node(10);
    b = new_node(20);
    c = new_node(30);
    d = new_node(100);
    e = new_node(90);
    f = new_node(40);
    g = new_node(50);
    h = new_node(60);
    i = new_node(70);
    j = new_node(80);
    k = new_node(150);
    l = new_node(110);
    m = new_node(120);

    insertion(t, a);
    insertion(t, b);
    insertion(t, c);
    insertion(t, d);
    insertion(t, e);
    insertion(t, f);
    insertion(t, g);
    insertion(t, h);
    insertion(t, i);
    insertion(t, j);
    insertion(t, k);
    insertion(t, l);
    insertion(t, m);

    inorder(t, t->root);

    return 0;
}