RedBlackTree.cpp

#include "RedBlackTree.h"
#include <limits.h>

RedBlackTree::RedBlackTree()
{
    this->nil = new RBNode(INT_MIN, BLACK);
    this->nil->left = this->nil->right = this->nil->parent = this->nil;
    this->root = this->nil;
    this->root->left = this->root->right = this->root->parent = this->nil;
}

void RedBlackTree::Insert(RBNode* z)
{
    RBNode* y = this->nil;
    RBNode* x = this->root;

    while (x != this->nil)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;
    if (y == this->nil)
        this->root = z;
    else if (z->key < y->key)
    {
        y->left = z;
    }
    else
    {
        y->right = z;
    }
    z->left = this->nil;
    z->right = this->nil;
    z->color = RED;

    InsertFixup(z);
}

void RedBlackTree::InsertFixup(RBNode* z)
{
    RBNode* y;

    while (z->parent->color == RED)
    {
        if (z->parent == z->parent->parent->left)
        {
            y = z->parent->parent->right;
            if (y->color == RED)
            {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else
            {
                if (z == z->parent->right)
                {
                    z = z->parent;
                    this->LeftRotate(z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                RightRotate(z->parent->parent);
            }
        }
        else
        {
            y = z->parent->parent->left;
            if (y->color == RED)
            {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else
            {
                if (z == z->parent->left)
                {
                    z= z->parent;
                    this->RightRotate(z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                LeftRotate(z->parent->parent);
            }
        }
    }
    this->root->color = BLACK;
}

RBNode* RedBlackTree::Delete(RBNode* z)
{
    RBNode *y, *x;

    if (z->left == this->nil || z->right == this->nil)
        y = z;
    else
        y = TreeSuccessor(z);
    if (y->left != this->nil)
        x = y->left;
    else
        x = y->right;
    x->parent = y->parent;
    if (y->parent == this->nil)
    {
        this->root = x;
    }
    else if (y == y->parent->left)
    {
        y->parent->left = x;
    }
    else
        y->parent->right = x;
    if (y != z)
    {
        z->key = y->key;
        // COPY ?????
    }
    if (y->color == BLACK)
        this->DeleteFixup(x);
    return y;
}

void RedBlackTree::DeleteFixup(RBNode* x)
{
    RBNode* w;

    while (x != this->root && x->color == BLACK)
    {
        if (x = x->parent->left)
        {
            w = x->parent->right;
            if (w->color == RED)
            {
                w->color = BLACK;
                x->parent->color = RED;
                this->LeftRotate(x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK)
            {
                w->color = RED;
                x = x->parent;
            }
            else
            {
                if (w->right->color == BLACK)
                {
                    w->left->color = BLACK;
                    w->color = RED;
                    this->RightRotate(w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                this->LeftRotate(x->parent);
                x = this->root;
            }
        }
        else
        {
            w = x->parent->left;
            if (w->color == RED)
            {
                w->color = BLACK;
                x->parent->color = RED;
                this->RightRotate(x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK)
            {
                w->color = RED;
                x = x->parent;
            }
            else
            {
                if (w->left->color == BLACK)
                {
                    w->right->color = BLACK;
                    w->color = RED;
                    this->LeftRotate(w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                this->RightRotate(x->parent);
                x = this->root;
            }
        }
    }
    x->color = BLACK;
}

void RedBlackTree::LeftRotate(RBNode* x)
{
    RBNode* y = x->right; // set y
    x->right = y->left; // turn y's left subtree into x's right subtree
    if (y->left != this->nil)
        y->left->parent = x;
    y->parent = x->parent; // link x parent to y

    if (x->parent == this->nil)
    {
        this->root = y;
    }
    else if (x == x->parent->left)
    {
        x->parent->left = y;
    }
    else
    {
        x->parent->right = y;
    }
    y->left = x; // put x on y's left
    x->parent = y;
}

void RedBlackTree::RightRotate(RBNode* x)
{
    RBNode* y = x->left; // set y
    x->left = y->right; // turn y's right subtree into x's left subtree
    if (y->right != this->nil)
        y->right->parent = x;
    y->parent = x->parent; // link x parent to y

    if (x->parent == this->nil)
    {
        this->root = y;
    }
    else if (x == x->parent->right)
    {
        x->parent->right = y;
    }
    else
    {
        x->parent->left = y;
    }
    y->right = x; // put x on y's right
    x->parent = y;
}

RBNode* RedBlackTree::TreeSuccessor(RBNode* x)
{
    if (x->right != this->nil)
        return this->TreeMinimum(x->right);
    RBNode* y = x->parent;
    while (y != this->nil && x == y->right)
    {
        x = y;
        y = y->parent;
    }
    return y;
}

RBNode* RedBlackTree::TreeMinimum(RBNode* x)
{
    while (x->left != this->nil)
        x = x->left;
    return x;
}

RBNode* RedBlackTree::TreeSearch(RBNode* x, int key)
{
    while (x != this->nil && key != x->key)
    {
        if (key < x->key)
            x = x->left;
        else x = x->right;
    }
    return x;
}

void RedBlackTree::InorderTreeWalk(RBNode* x)
{
    if (x != this->nil)
    {
        InorderTreeWalk(x->left);
        cout << x->key << " " << ((x->color == RED) ? "RED"  : "BLACK") << ", ";
        InorderTreeWalk(x->right);
    }
}

void RedBlackTree::Print()
{
    InorderTreeWalk(this->root);
}