【数据结构】红黑树

参考博文

http://www.voidcn.com/article/p-bxexkenz-bkd.html

http://www.voidcn.com/article/p-rtxkhfuv-dk.html

http://www.voidcn.com/article/p-zlvnvhog-dk.html

http://www.voidcn.com/article/p-mpzapwzu-dk.html

可视化数据结构

http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

#define DeBUG
#include <iostream>
#include <queue>
#include <stack>
#include <malloc.h>
using namespace std ;
#define zero {0}
#define RED 0
#define BLACK 1

struct RBTree
{
    RBTree *right;
    RBTree *left;
    RBTree *parent;
    bool color;
    int key;
    RBTree(int d)
    {
        key = d;
        color = RED;
        right = left = NULL;
        parent = NULL;
    }
};
void PreOrder(RBTree *p)
{
    if (p != NULL)
    {
        printf("(%d)%s ",p->key,p->color == BLACK ? "黑" : "红");
        PreOrder(p->left);
        PreOrder(p->right);
    }
}
void InOrder(RBTree *p)
{
    if (p != NULL)
    {
        InOrder(p->left);
        printf("(%d)%s ",p->color == BLACK ? "黑" : "红");
        InOrder(p->right);
    }
}
void PostOrder(RBTree *p)
{
    if (p != NULL)
    {
        PostOrder(p->left);
        PostOrder(p->right);
        printf("(%d)%s ",p->color == BLACK ? "黑" : "红");
    }
}
int Depth(RBTree *current)//深度
{
    int Depthleft;
    int Depthright;
    int dp = 0;
    if (current == NULL)
    {
        return 0;
    }
    else
    {
        Depthleft = Depth(current->left);
        Depthright = Depth(current->right);
        dp = 1 + (Depthright >= Depthleft ? Depthright : Depthleft);
    }
    return dp;
}
void layerOrder(RBTree *p)
{
    if (p != NULL)
    {
        queue<RBTree *>st;
        st.push(p);
        while (!st.empty())
        {
            RBTree *now = st.front();
            st.pop();
            if ( now->parent != NULL)
            {
                if (now->parent->right == now)
                    printf("(%d->%d)%s ",now->parent->key,now->key,now->color == BLACK ? "黑" : "红");
                else
                    printf("(%d<-%d)%s ",now->color == BLACK ? "黑" : "红");
            }
            else
                printf("(%d-%d)%s ",now->color == BLACK ? "黑" : "红");
            if (now->left != NULL)
            {
                st.push(now->left);
            }
            if (now->right != NULL)
            {
                st.push(now->right);
            }
        }
    }
    printf("n");
}
//左旋
/*-----------------------------------------------------------
|   node           right
|   /      ==>    /  
|   a  right     node  y
|       /        / 
|       b  y     a   b
-----------------------------------------------------------*/
RBTree *LeftRotate(RBTree *node,RBTree *root)
{
    RBTree *right = node->right;
    if (node->right = right->left)
    {
        right->left->parent = node;
    }
    right->left = node;
    if ( right->parent = node->parent)
    {
        if (node == node->parent->right)
            node->parent->right = right;
        else
            node->parent->left = right;
    }
    else
        root = right;
    node->parent = right;
    return root;
}
//右旋
/*-----------------------------------------------------------
|       node            left
|       /              / 
|    left  y   ==>    a    node
|    /                    / 
|   a   b                 b   y
-----------------------------------------------------------*/
RBTree *RightRotate(RBTree *node,RBTree *root)
{
    RBTree *left = node->left;
    if (node->left = left->right)
    {
        left->right->parent = node;
    }
    left->right = node;
    if (left->parent = node->parent)
    {
        if (node == node->parent->right)
            node->parent->right = left;
        else
            node->parent->left = left;
    }
    else
        root = left;
    node->parent = left;
    return root;
}
RBTree *Search(int key,RBTree *root,RBTree **parent)
{
    RBTree *node = root;
    int ret;
    while (node)
    {
        if (parent)
            *parent = node;
        ret = node->key - key;
        if (0 < ret)
            node = node->left;
        else if (0 >= ret)//key唯一时取消=
            node = node->right;
        else
            return node;
    }
    return NULL;
}
RBTree *GetNode(int key,RBTree *root)
{
    RBTree *node = root;
    int ret;
    while (node)
    {
        ret = node->key - key;
        if (0 < ret)
            node = node->left;
        else if (0 > ret)
            node = node->right;
        else
            return node;
    }
    return NULL;
}

RBTree *RB_insert_rebalance(RBTree *node,RBTree *root)
{
    RBTree *parent,*gparent,*uncle;
    while ((parent = node->parent) && parent->color == RED)
    {
        // if(node->key==8)
        // {
        //         layerOrder(root);
        //        printf("n");
        // }

        gparent = parent->parent;
        if (parent == gparent->left)
        {
            uncle = gparent->right;
            if (uncle && uncle->color == RED)//情况1
            {
                uncle->color = BLACK;
                parent->color = BLACK;
                gparent->color = RED;
                node = gparent;
            }
            else//情况2,3，右黑叔叔
            {
                if (parent->right == node)
                {
                    root = LeftRotate(parent,root);
                    swap(parent,node);
                }
                parent->color = BLACK;
                gparent->color = RED;
                root = RightRotate(gparent,root);
            }
        }
        else//对称情况
        {
            uncle = gparent->left;
            if (uncle && uncle->color == RED)
            {
                uncle->color = BLACK;
                parent->color = BLACK;
                gparent->color = RED;
                node = gparent;
            }
            else//左黑叔叔
            {
                if (parent->left == node)
                {
                    root = RightRotate(parent,node);
                }
                parent->color = BLACK;
                gparent->color = RED;
                root = LeftRotate(gparent,root);
            }
        }
    }
    root->color = BLACK;
    return root;
}
RBTree *Insert(int key,RBTree *root)
{
    RBTree *parent = NULL,*node;
    if (Search(key,root,&parent))
    {
        //return root;//通过键值唯一确定一个数据
    }
    node = new RBTree(key);
    node->parent = parent;
    if (parent)
    {
        if (parent->key > key)
            parent->left = node;
        else
            parent->right = node;
    }
    else
        root = node;
    return RB_insert_rebalance(node,root);
}
RBTree *RB_del_rebalance(RBTree *node,RBTree *parent,RBTree *root)
{
    RBTree *other,*o_left,*o_right;
    while ((!node || node->color == BLACK) && node != root)
    {
        if (parent->left == node)
        {
            other = parent->right;
            if (other->color == RED) //情况1：x兄弟节点是红色
            {
                other->color = BLACK;
                parent->color = RED;
                root = LeftRotate(parent,root);
                other = parent->right;
            }
            else if ((!other->left || other->left->color == BLACK) &&
                     (!other->right || other->right->color == BLACK))
                //情况2：x的兄弟节点为黑色且w的两个孩子为黑色
            {
                other->color = RED;
                node = parent;
                parent = node->parent;
            }
            else
            {
                //情况3：x的兄弟w是黑色的，且w的左孩子是红色，w的右孩子是黑色。
                if (!other->right || other->right->color == BLACK
                   )
                {
                    if ((o_left = other->left))
                    {
                        o_left->color = BLACK;
                    }
                    other->color = RED;
                    root = RightRotate(other,root);
                    other = parent->right;
                }
                //情况4：x的兄弟节点w是黑色，且w的右孩子为红
                other->color = parent->color;
                parent->color = BLACK;
                //change
                other->right->color = BLACK;
                root = LeftRotate(parent,root);
                node = root;
                break;
            }
        }
        else
        {
            other = parent->left;
            if (other->color == RED) //1
            {
                other->color = BLACK;
                parent->color = RED;
                root = RightRotate(parent,root);
                other = parent->left;
            }
            //2
            if ((!other->left || other->left->color == BLACK) &&
                    (!other->right || other->right->color == BLACK))
            {
                other->color = RED;
                node = parent;
                parent = node->parent;
            }
            else
            {
                //3
                if (!other->left || other->left->color == BLACK)
                {
                    if ((o_right = other->right))
                    {
                        o_right->color = BLACK;
                    }
                    other->color = RED;
                    root = LeftRotate(other,root);
                    other = parent->left;
                }
                //4
                other->color = parent->color;
                parent->color = BLACK;
                //change
                other->left->color = BLACK;
                root = RightRotate(parent,root);
                node = root;
                break;
            }
        }
    }
    if (node)
        node->color = BLACK;
    return root;
}
RBTree *delnode(int key,RBTree *root)
{
    RBTree *child,*parent,*old,*left,*right,*node;
    bool color;
    if (!(node = GetNode(key,root)))
    {
        printf("key %d is not exist!n",key);
        return root;
    }
    old = node;
    if (node->left && node->right)
    {
        node = node->left;
        while ((right = node->right) != NULL)
            //用左边的最右节点替代
        {
            node = right;
        }
        child = node->left;
        parent = node->parent;
        color = node->color;
        if (child)
        {
            child->parent = parent;
        }
        if (parent)
        {
            if (parent->left == node)
                parent->left = child;
            else
                parent->right = child;
        }
        else
            root = child;
        if (node->parent == old)
            parent = node;
        node->parent = old->parent;
        node->color = old->color;
        node->right = old->right;
        node->left = old->left;
        if (old->parent)
        {
            if (old->parent->left == old)
                old->parent->left = node;
            else
                old->parent->right = node;
        }
        else
            root = node;
        if (old->left)
            old->left->parent = node;
        if (old->right)
            old->right->parent = node;
    }
    else
    {
        if (node->left == NULL)
            child = node->right;
        else if (node->right == NULL)
            child = node->left;
        parent = node->parent;
        color = node->color;
        if (child)
            child->parent = parent;
        if (parent)
        {
            if (parent->left == node)
                parent->left = child;
            else
                parent->right = child;
        }
        else
            root = child;
    }
    delete(old);
    if (color == BLACK)
        root = RB_del_rebalance(child,parent,root);
    return root;
}
int main()
{
#ifdef DeBUGs
    freopen("C:UsersSkyDesktop1.in","r",stdin);
#endif
    char op[10];
    RBTree *root = NULL;
    // int N = 15;
    // for (int i = 1; i <= N; i++)
    // {
    //     root = Insert(i,root);
    // }
    // layerOrder(root);
    // PreOrder(root);
    // puts("");
    // InOrder(root);
    // puts("");
    // PostOrder(root);
    // puts("");
    // printf("深度%dn",Depth(root));
    int key;
    do
    {
        printf("请输入操作（i）插入（d）删除:n");
        scanf("%s",op);
        if (op[0] == 'd')
        {
            printf("输入数值：");
            scanf("%d",&key);
            root = delnode(key,root);
            printf("删除后结果：（层序遍历）n");
            layerOrder(root);
            printf("深度%dn",Depth(root));
        }
        else
        {
            printf("输入数值：");
            scanf("%d",&key);
            root = Insert(key,root);
            printf("插入后结果：（层序遍历）n");
            layerOrder(root);
            printf("深度%dn",Depth(root));
        }
    }
    while (true);
    return 0;
}