레드블랙 트리(Red Black Tree) (변형이진탐색트리)

레드 블랙 트리는 효율적인 탐색을 위해 BST의 height를 낮추는방식으로 고안된 트리이다.

다음의 3 가지 조건을 만족해야 한다.

1. 루트 노드와 외부 노드는 Black 노드이다
2. Red 노드가 연속해서 올 수 없다
3. 루트로부터 외부 노드로 까지의 가는 경로에서 count 되는 Black 노드의 수는 같다 (최대 경로는 최소 경로의 두배 이하이다)

그리고 이러한 조건을 만족시키기 위해 삽입 시에는 Red 노드로 삽입을 고정시키는 것이 유리하다

(블랙 노드로 삽입시 조건 3을 위배시키기 쉬워서 이런 경우에는 복잡한 처리를 수행해야 하기 때문)

Red 노드로 삽입 후에는 조건 2만 체크를 하면 된다.

조건 2를 만족시키기 위해 4가지 Case가 있는데 다음과 같다.(right에 삽입되었을 경우를 합치면 총 8가지 case)

• LLb - Red 노드가 연속해서 왼쪽 자식의 노드로 오고 조부모(g) 노드의 반대 자식 노드가 Black일 경우
• LLr - Red 노드가 연속해서 왼쪽 자식의 노드로 오고 조부모(g) 노드의 반대 자식 노드가 Red일 경우
• LRr - Red 노드가 왼쪽 자식의 노드, 오른쪽 자식의 노드로 오고 조부모(g) 노드의 반대 자식 노드가 Red일 경우
• LRb - Red 노드가 왼쪽 자식의 노드, 오른쪽 자식의 노드로 오고 조부모 노드의 반대 자식 노드가 Black일 경우

각각의 경우에서 다른 자식 노드가 Red 일 경우 색깔만 다시 칠해준다(recoloring)

각각의 경우에서 다른 자식 노드가 Black 일 경우 재조정을 해준다(restructuring)

조정법

• LLr - gu 노드를 레드로 pu 노드를 블랙, 다른 자식 노드(guR)를 블랙 처리 (처리 후에 양쪽 경로로 가는 길에 black 노드 수 같음)
• LRr - gu 노드를 레드로 u 노드를 블랙, 다른 자식 노드(guR)를 블랙 처리 (처리 후에 양쪽 경로로 가는 길에 black 노드 수 같음)
• LLb - pu 노드가 중간으로 가고 gu 노드를 rch로, 자식 노드를 lch로 두는 방식으로 재조정
• LRb - u(손자) 노드가 중간으로 가고 gu 노드를 rch로, 부모 노드를 lch로 두는 방식으로 재조정

이렇게 새로 노드가 삽입되면 *ub = 1을 주고 재귀적으로 들어온 순서로 다 체크를 해주면서 루트까지간다

루트에 도달 후에는 루트 색깔을 검정색으로 변화시켜준다(혹시나 처리 과정 중에 루트 색깔이 빨강으로 변화할수 있음)

// C program for Red-Black Tree insertion
#include<stdio.h>
#include<stdlib.h>
 
//A Red-Black tree node structure
struct node
{
    int data;     // for data part
    char color;  // for color property
 
    //links for left, right children and parent
    struct node *left, *right, *parent;
};
 
 
// Left Rotation
void LeftRotate(struct node **root,struct node *x)
{
    //y stored pointer of right child of x
    struct node *y = x->right;
 
    //store y's left subtree's pointer as x's right child
    x->right = y->left;
 
    //update parent pointer of x's right
    if (x->right != NULL)
        x->right->parent = x;
 
    //update y's parent pointer
    y->parent = x->parent;
 
    // if x's parent is null make y as root of tree
    if (x->parent == NULL)
        (*root) = y;
 
    // store y at the place of x
    else if (x == x->parent->left)
        x->parent->left = y;
    else    x->parent->right = y;
 
    // make x as left child of y
    y->left = x;
 
    //update parent pointer of x
    x->parent = y;
}
 
 
// Right Rotation (Similar to LeftRotate)
void rightRotate(struct node **root,struct node *y)
{
    struct node *x = y->left;
    y->left = x->right;
    if (x->right != NULL)
        x->right->parent = y;
    x->parent =y->parent;
    if (x->parent == NULL)
        (*root) = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else y->parent->right = x;
    x->right = y;
    y->parent = x;
}
 
// Utility function to fixup the Red-Black tree after standard BST insertion
void insertFixUp(struct node **root,struct node *z)
{
    // iterate until z is not the root and z's parent color is red
    while (z != *root && z->parent->color == 'R')
    {
        struct node *y;
 
        // Find uncle and store uncle in y
        if (z->parent == z->parent->parent->left)
            y = z->parent->parent->right;
        else
            y = z->parent->parent->left;
 
        // If uncle is RED, do following
        // (i)  Change color of parent and uncle as BLACK
        // (ii) Change color of grandparent as RED
        // (iii) Move z to grandparent
        if (y->color == 'R')
        {
            y->color = 'B';
            z->parent->color = 'B';
            z->parent->parent->color = 'R';
            z = z->parent->parent;
        }
 
        // Uncle is BLACK, there are four cases (LL, LR, RL and RR)
        else
        {
            // Left-Left (LL) case, do following
            // (i)  Swap color of parent and grandparent
            // (ii) Right Rotate Grandparent
            if (z->parent == z->parent->parent->left &&
                z == z->parent->left)
            {
                char ch = z->parent->color ;
                z->parent->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                rightRotate(root,z->parent->parent);
            }
 
            // Left-Right (LR) case, do following
            // (i)  Swap color of current node  and grandparent
            // (ii) Left Rotate Parent
            // (iii) Right Rotate Grand Parent
            if (z->parent == z->parent->parent->left &&
                z == z->parent->right)
            {
                char ch = z->color ;
                z->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                LeftRotate(root,z->parent);
                rightRotate(root,z->parent->parent);
            }
 
            // Right-Right (RR) case, do following
            // (i)  Swap color of parent and grandparent
            // (ii) Left Rotate Grandparent
            if (z->parent == z->parent->parent->right &&
                z == z->parent->right)
            {
                char ch = z->parent->color ;
                z->parent->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                LeftRotate(root,z->parent->parent);
            }
 
            // Right-Left (RL) case, do following
            // (i)  Swap color of current node  and grandparent
            // (ii) Right Rotate Parent
            // (iii) Left Rotate Grand Parent
            if (z->parent == z->parent->parent->right &&
                z == z->parent->left)
            {
                char ch = z->color ;
                z->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                rightRotate(root,z->parent);
                LeftRotate(root,z->parent->parent);
            }
        }
    }
    (*root)->color = 'B'; //keep root always black
}
 
// Utility function to insert newly node in RedBlack tree
void insert(struct node **root, int data)
{
    // Allocate memory for new node
    struct node *z = (struct node*)malloc(sizeof(struct node));
    z->data = data;
    z->left = z->right = z->parent = NULL;
 
     //if root is null make z as root
    if (*root == NULL)
    {
        z->color = 'B';
        (*root) = z;
    }
    else
    {
        struct node *y = NULL;
        struct node *x = (*root);
 
        // Follow standard BST insert steps to first insert the node
        while (x != NULL)
        {
            y = x;
            if (z->data < x->data)
                x = x->left;
            else
                x = x->right;
        }
        z->parent = y;
        if (z->data > y->data)
            y->right = z;
        else
            y->left = z;
        z->color = 'R';
 
        // call insertFixUp to fix reb-black tree's property if it
        // is voilated due to insertion.
        insertFixUp(root,z);
    }
}
 
// A utility function to traverse Red-Black tree in inorder fashion
void inorder(struct node *root)
{
    if (root == NULL)
        return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}
 
/* Drier program to test above function*/
int main()
{
    struct node *root = NULL;
    insert(&root,10);
    insert(&root,20);
    insert(&root,40);
    insert(&root,30);
    insert(&root,50);
    insert(&root,35);
    insert(&root,25);
    insert(&root,37);
    printf("inorder Traversal Is : ");
    inorder(root);
 
    return 0;
}

구현 : https://gist.github.com/VictorGarritano/5f894be162d39e9bdd5c