一、红黑树简介

        红黑树是一种自平衡的二叉查找树，是一种高效的查找树。在添加时，会自动调整输的结构，从而达到平衡的目的。平衡是为了查找时速度更快，能够在O(log(n))时间内完成查找，添加，删除。

二、为什么需要红黑树？

        对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间，视情况而定。那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。
 

三、 红黑树的定义

        左根右、根叶黑、不红红、黑路同

左根右：红黑树每一个节点都满足左子树小于根节点小于右子树。

根叶黑：根节点、叶子节点都为黑色

不红红：红黑树中不存在两个相邻的红节点。即爹跟儿子不同时为红。

黑路同：从任何一个节点，到叶子节点时，所经过的黑色节点数量相同

四、代码实现

#define RED     0
#define BLACK   1

typedef int KEY_TYPE;


#define RBTREE_ENTRY(name, type)\
    struct name{                \
        struct type *right;     \
        struct type *left;      \
        struct type *parent;    \
        unsigned char color;    \
    }

定义红黑树的左右指针，父节点，颜色


typedef struct _rbtree_node
{
    
    KEY_TYPE key;
    void *value;

定义位置和这个位置存储的数据


#if 1
    struct _rbtree_node *right;
    struct _rbtree_node *left;

    struct _rbtree_node *parent;

   
    unsigned char color;
#else
    RBTREE_ENTRY(,rbtree_node)node;

将红黑树的指针单独封装，与位置和数值做出区分。这样在定义多颗红黑树时，直接调用RBTREE_ENTRY(,rbtree_node)node;即可，避免了重复写代码。

#endif
} rbtree_node;




typedef struct _rbtree
{
    struct _rbtree_node *root;    //gen node
    struct _rbtree_node *nil;     //leaf node
} rbtree;

红黑树根节点、叶子节点单独定义，方便操作




void rbtree_left_rotate(rbtree *T, rbtree_node *x)
{

        左旋
    rbtree_node *y = x->right;

        y指向x的右孩子 （因为是左旋，所以指向右孩子）

    x->right = y->left;

x右指针指向y的左孩子
    if(y->left != T->nil)
    {
        y->left->parent = x;

        如果y的做孩子不是叶子节点的话，y左孩子的父节点指向x。因为红黑树中，叶子节点如果拥有父节点的话，会出许多问题。所以叶子结点没有父节点。
    }

    y->parent = x->parent;

       y的父节点指向x的爹。 y的辈分升级
    if(x->parent == T->nil)
    {
        T->root = y； 如果x的父节点为叶子节点，说明x是跟节点，左旋完毕后，x降辈分，y升辈分。所以y为新的根节点
    }else if(x == x->parent->left)
    {
        x->parent->left = y;

        第二种情况，如果x是x父节点的左孩子，则x的父节点的左指针指向y。也就是y成为x父节点的左孩子。
    }else
    {
        x->parent->right = y;

        第三种情况，如果x是x父节点的右孩子，则x的父节点的右指针指向y。也就是y成为x父节点的右孩子
    }

    y->left = x;
    x->parent = y;

最后y的左指针指向x，x的父指针指向y。爹变儿子，儿子变爹。

}


void rbtree_right_roate(rbtree *T,rbtree_node *y)
{
    rbtree_node *x = y->left;

    y->left = x->right;
    if(x->right != T->nil)
    {
        x->right->parent = y;
    }

    x->parent = y->parent;
    if(y->parent == T->nil)
    {
        T->root = x;
    }else if(y == y->parent->right)
    {
        y->parent->right = x;
    }else
    {
        y->parent->left = x;
    }

    x->right = y;
    y->parent = x;
    
}

右旋与左旋操作一致，只是正好全部反过来。


void rvtree_insert_fixup(rbtree *T, rbtree_node *z)
{

红黑树的变色
    // z == RED is qianti

插入节点的父节点为红色是前提，经过以下操作变色，插入节点与父节点颜色正常。爷节点变为新的节点，如果爷节点是黑色，则没有破坏红黑树结构，变色结束。如果爷节点为红色节点，则有可能破坏结构，继续以下操作。周而复始，一直到节点为黑色。
    while (z->parent->color == RED)
    {
        if (z->parent == z->parent->parent->left)
        {
            rbtree_node *y = z->parent->parent->right;

        如果插入节点的爹是爷的左孩子，则y指针指向爷的右孩子，也就是爹的右兄弟。

            if(y->color == RED)
            {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;

                z = z->parent->parent;  //z is red ever

        如果叔叔是红的，则爹变黑，插入节点变黑，爷变红。爷变为新的孩子节点，看看爷的爹，爷，叔的颜色是否满足规则。周而复始。
            }else

        

{   // y == BLACK

        叔不是红色的话，肯定是黑色。而且当前节点是它爹的左孩子的话，说明当前节点是爷的左孩子的左孩子，也就是LL型。
                if (z == z->parent->left)  //LL class
                {
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                
                rbtree_right_roate(T, z->parent->parent);

                爹变黑，爷变红。以爷为轴心，右旋一次。
                }
            }    
        }
    }
}


void rbtree_insert(rbtree *T, rbtree_node *z) 红黑树的插入
{

    rbtree_node *y = T->nil;
    rbtree_node *x = T->root;

y指向叶子，x指向根

    while (x != T->nil)
    {

        x不指向叶子，循环继续
        y = x;        y指向x，因为循环到最低层后，x一定会指向叶子节点。此时设置y指向x，x循环一次之后，y仍然指向当前节点，x指向下一层的孩子节点。也就是y会指向x的父节点。这样在循环到底时，x指向叶子节点，y指向上一层，也就是要插入的位置。

        
        if (z->key < x->key)
        {
            x = x->left;        如果要插入的值小于x的值，x指向左孩子


        }else if (z->key > x->key)
        {
            x = x->right；        如果大于，x指向右孩子
        }else 
        {
            //exist
            return ;         如果相等，不做处理
        }
    }

循环完成后，y会指向要插入的位置

    if (y == T->nil)
    {
        T->root = z;        如果y指向了叶子节点，说明是以可空树。则当前节点设置为根节点
    }else
    {

        if (y->key > z->key)        否则y指向的节点不是叶子节点，如果插入节点的数值小于y节点的值
        {
            y->left = z;        插入为左孩子
        }else
        {
            y->right = z;        否则插入为右孩子
        }
    }
   
    z->parent = y;        插入节点的父指针指向y。

}

总之，插入后，若新节点为根，直接染黑。

新节点不是根，染红。 若父节点为黑，则满足红黑树，不需要操作。

若父节点为红色，违反不红红。需要看叔叔颜色

叔叔为黑，旋转加染色：

        1.LL        右单旋，父爷互换，染色。也就是上面代码演示的

        2.RR        左单旋，父爷互换，染色。

        3.LR        左右双旋， 儿换爷，染色

        4.RL        右左双旋，儿换爷，染色

叔叔为红：染色 变新。

        叔父爷变色，爷当新节点，开始下一轮循环，看是否满足红黑树的定义。