红黑树概念(concept)

树型结构主要用于搜索，一直是科学领域的重要演算法，当中探讨了树可能遇到的问题：树的成长可能偏向于一边，也就是不平衡现象。

二叉树是常见且广泛使用的一种树，面临其可能退化成链表的潜藏缺点，在使用上难免让人担心其效率。此外，在一些应用上，可能不希望这样的不平衡的可能性发生。所以具有自动平衡左右数量分布效果的演算算法早在 1962 年被提出，称为 AVL 树。这种平衡成长的二叉搜索树被称为自平衡二叉搜索树。

接下来，介绍同为自平衡二叉搜索树的红黑树对平衡性的要求比 AVL 树还要宽松。红黑树是利用节点颜色来检查二叉树每条路径的高度是否差不多，因为发明者定下了以下规则：

树上的每个结点(node) 只能是 红色 或 黑色。
1.
根节点(root) 一定是黑色。
1.
叶子节点(leaf) 一定是 黑色 的 空值节点 (NULL)。
1.
任一路径上不能有两个连续的红色。注意：黑色节点的子节点颜色没有限制。
1.
从任何节点出发，其下至叶节点所有路径的黑色节点数目相同。

满足上述的二叉树，相比一般的二叉树更能保持平衡性，往后套用二叉树的算法来查找时能更快速、方便的到达目的地，套用算法的时间复杂度为 O(logn)，因为红黑树保证最长路径不会超过最短路径的两倍（由规则 4 和规则 5）。原因是：当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（规则4限定了不能出现两个连续的红色节点）。而规则5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的 2 倍。

如下是一个红黑树示例图：

注意：null 节点是指每个叶节点都有两个空的并且颜色为黑的 NULL 节点，一般在示例图中需要它的时候就可以把它看成两个黑色的节点，不需要的时候可以忽视它。

红黑树与AVL的比较：

红黑树和 AVL 树的算法时间复杂度相同，但红黑树不追求完全平衡，换来的是增删节点时转转次数的降低，任何不平衡都会在三次旋转之内解决，但AVL是严格平衡树，旋转次数比红黑树多。插入节点失衡时，AVL 和 RBTree 都是最多两次旋转实现复衡 (O(1))，但删除节点失衡时，AVL 需要维护从被删除节点到根节点路径上所有节点的平衡 (O(logN))，而红黑树最多只需要 3 次 (O(1))，所以 RBTree 在内容极多时优于 AVL，RBTree 的功能、性能、空间开销综合更好。红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在 STL 的 set 和 map 等容器中被优先使用。

因为红黑树也是一种二叉树，所以例如：插入结点、删除结点、查询结点等针对红黑树的操作与二叉树的操作前段演算法相同，只是在每次操作完后可能会让树的结构改变而可能无法满足红黑树的规则，进而可能不具有平衡的性质。为了在操作后仍是一颗红黑树，需要通过变色和旋转调整来满足红黑树的规则。

红黑树插入(Insertion)

在新增的操作上，新插入的节点一律为红色，因此如果插入的节点着色为黑色，那必然有可能导致某条路径上的黑色节点数量大于其他路径上的黑色节点数量，因此默认插入的节点必须是红色的，目的是希望红黑树维持上面规则5的约束，也就是任一根节点到叶子节点黑色节点数目相同，但是也可能违反出了规则5外的其他规则，所以做完二叉树新增操作后，需要以新增的节点开始向上检查红黑树是否符合各项规则。

首先先明确以下各个节点的叫法：

红黑树的插入会有以下几种情况，因为不同情况会采取不同的修正过程：

• 情况1：当红黑树为空树时，新插入红色节点成为根节点，必须将其变成黑色。

• 情况2：插入新的红色节点的父节点为黑色，并不会影响红黑树的平衡，直接插入即可。

• 情况3：插入的新的红色节点的父节点是红色，若叔叔结点为红色，则祖父结点一定为黑色，将祖父结点变为红色，而父节点和叔叔结点变为黑色。因为红色结点上移，出现连续的红色节点，形成了情况4，这将再情况4中说明。

• 情况4：插入的新的红色节点的父节点是红色，如果叔叔节点是黑色，且新的节点在父节点右边，则先以父节点进行左旋转，形成了情况5，在情况5中处理。

• 情况5：插入新的红色节点的父节是红色 ，如果叔叔节点是黑色，且新节点在父节点左边，则先将父节点变成黑色，但是违反了规则5（黑色节点数目不相同），必须再将祖父节点变成红色，以祖父节点进行右旋（直觉上，节点F的左边路径会多一个黑色节点，可以通过右旋把黑色转掉）。

注意：以上都在讨论新插入的红色节点的父节点是红色，且父节点是祖父节点的左分支情况，如果是在右分支，其处理是镜像的，只需要左右互换一下就可以了。

红黑树删除(Deletion)

首先要了解 AVL 的删除操作：

如果删除的是叶子节点，可以直接删除。
1.
如果被删除的元素有一个子节点，可以将子节点直接移动到被删除元素的位置。
1.
如果有两个子节点，这时候就可以把被删除的元素的右分支的最小点（也就是被删除元素左分支的最左边节点）和被删除的元素互换，然后再将被删除元素删除。

但是红黑树加入颜色后，被删除元素和后继元素互换只是值互换，并不是互换颜色。

红黑树的删除操作上，删除一个节点可能会违反规则，需要向上检查红黑树是否符合各项规则，修正红黑树可能会有以下几种情况：

情况1：当被删除节点为黑且为根节点时，直接删除。
*
情况2：被删除的是红色的节点，不违反任何规则，直接删除。
*
情况3：被删除的节点是黑色，但是递补上来的节点是红色，直接将该递补上来的节点变为黑色即可。

情况4：被删除的节点为黑色，且兄弟节点为红色，需要将兄弟节点变为黑色，父节点变为红色，再以父节点进行左旋。形成了情况5，在情况5中处理。

情况5：被删除的节点为黑色，若兄弟节点为黑色，且兄弟的左孩子节点与右孩子节点都是黑色时，这时如果父节点为红色，将兄弟节点变为红色，父节点变为黑色即可。

情况6：被删除的节点为黑色，且兄弟节点为黑色，兄弟节点的左孩子节点为红色，这时需要把兄弟节点变为红色，兄弟节点的左孩子节点变为黑色，再以兄弟节点进行右旋操作。形成了情况7，在情况7中处理。

情况7：被删除的节点为黑色，且兄弟节点为黑色，兄弟节点的右孩子节点为红色，这时需要把兄弟节点变为父节点的颜色，并把父节点和兄弟节点的右孩子节点变为黑色，再以父节点进行左旋即可。

注意：以上都在讨论删除红黑树的一个节点，且被删除节点是父节点左分支情况，如果是在右分支上，其处理是镜像的。

红黑树的总结(Conclusion)

红黑树的步骤是可以推导出来的，因为把一个平衡但通过插入或删除操作破坏了平衡的红黑树再次平衡，通过转转和变色使其符合红黑树的 5 条规则，旋转操作是为了符合二叉树左小右大的性质，交换颜色是为了保持红黑树的 5 条性质。时刻记得红黑树的一切操作是为了上面的5条规则。

红黑树的实现(Implement)

红黑树的节点类型定义如下：

template <typename Type>
struct RBTNode
{
    Color color;     //颜色
    Type key;        //关键字
    RBTNode *left;   //左孩子
    RBTNode *right;  //右孩子
    RBTNode *parent; //父结点
};

下面给出红黑树的 C++ 完整实现代码：

#include <iostream>
#include <assert.h>

using namespace std;

typedef enum
{
    RED = 0,
    BLACK
} Color;

//红黑树结点类型
template <typename Type>
struct RBTNode
{
    Color color;     //颜色
    Type key;        //关键字
    RBTNode *left;   //左孩子
    RBTNode *right;  //右孩子
    RBTNode *parent; //父结点
};

//红黑树类型
template <typename Type>
class RBTree
{
public:
    //构造函数
    RBTree()
    {
        Nil = BuyNode();
        root = Nil;
        Nil->color = BLACK;
    }
    //析构函数
    ~RBTree()
    {
        destroy(root); //销毁创建的非Nil结点
        delete Nil;    //最后删除Nil结点
        Nil = NULL;
    }

    //中序遍历
    void InOrder() { InOrder(root); }

    //插入
    //1.BST方式插入
    //2.调整平衡
    bool Insert(const Type &value)
    {
        RBTNode<Type> *pr = Nil; //pr用来记住父节点
        RBTNode<Type> *s = root; //定义变量s指向根
        while (s != Nil)
        {
            if (value == s->key)
            {
                return false;
            }
            pr = s; //每次记住s的父节点
            if (value < s->key)
            {
                s = s->left;
            }
            else
            {
                s = s->right;
            }
        }
        //循环后s==Nil
        s = BuyNode(value); //申请结点
        if (pr == Nil)      //如果父节点pr是根节点，第一次root指向Nil，所以pr==Nil
        {
            root = s;
            root->parent = pr;
        }
        else //如果父节点不是根节点
        {
            if (value < pr->key)
            {
                pr->left = s;
            }
            else
            {
                pr->right = s;
            }
            s->parent = pr; //设置新结点s的父节点
        }
        //调整平衡
        Insert_Fixup(s);
        return true;
    }

    //删除key结点(先查找，再调用内部删除)
    void Remove(Type key)
    {
        RBTNode<Type> *t;
        if ((t = Search(root, key)) != Nil)
        {
            Remove(t);
        }
        else
        {
            cout << "Key is not exist." << endl;
        }
    }

    //中序遍历打印结点详细的结点颜色
    void InOrderPrint() { InOrderPrint(root); }

protected:
    //申请结点结点，将结点的颜色初始化为红色，初始化结点的关键字，其他的初始化为空
    RBTNode<Type> *BuyNode(const Type &x = Type())
    {
        RBTNode<Type> *s = new RBTNode<Type>();
        assert(s != NULL);
        s->color = RED;
        s->left = s->right = s->parent = Nil;
        s->key = x;
        return s;
    }

    //中序遍历
    void InOrder(RBTNode<Type> *root)
    {
        if (root != Nil)
        {
            InOrder(root->left);
            cout << root->key << " ";
            InOrder(root->right);
        }
    }

    /* 左转，对z结点左转 * zp zp * / \ * z z * / \ ===> / \ * lz y lz y * / \ / \ * ly ry ly ry */
    void LeftRotate(RBTNode<Type> *z)
    {
        RBTNode<Type> *y = z->right; //用y指向要转动的z结点
        z->right = y->left;
        if (y->left != Nil) //y所指结点的左结点不为空
        {
            y->left->parent = z;
        }
        y->parent = z->parent;
        if (root == z) //z就是根节点
        {
            root = y;
        }
        else if (z == z->parent->left) //z在左结点
        {
            z->parent->left = y;
        }
        else //z在右结点
        {
            z->parent->right = y;
        }
        y->left = z;
        z->parent = y;
    }

    /* 右转，对z结点进行右转 * zp zp * / \ * z z * / \ ===> / \ * y rz y rz * / \ / \ * ly ry ly ry */
    void RightRotate(RBTNode<Type> *z)
    {
        RBTNode<Type> *y = z->left;
        z->left = y->right;
        if (y->right != Nil)
        {
            y->right->parent = z;
        }
        y->parent = z->parent;
        if (root == z) //如果z是根结点
        {
            root = y;
        }
        else if (z == z->parent->left) //z在左结点
        {
            z->parent->left = y;
        }
        else //z在右结点
        {
            z->parent->right = y;
        }
        y->right = z;
        z->parent = y;
    }

    //插入后的调整函数
    void Insert_Fixup(RBTNode<Type> *s)
    {
        RBTNode<Type> *uncle;           //叔结点（父结点的兄弟结点）
        while (s->parent->color == RED) //父节点的颜色也为红色
        {
            if (s->parent == s->parent->parent->left) //父节点是左结点
            {
                uncle = s->parent->parent->right;

                if (uncle->color == RED) //叔结点为红色
                {
                    //父节点和叔结点都变为黑色
                    s->parent->color = BLACK;
                    uncle->color = BLACK;
                    //祖父结点变为红色
                    s->parent->parent->color = RED;
                    //将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色
                    s = s->parent->parent;
                }
                else //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑)
                {
                    if (s == s->parent->right) //如果调整的结点在右结点
                    {
                        s = s->parent; //先将s指向s的父结点
                        LeftRotate(s); //再左转
                    }
                    //如果调整的结点在左结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转
                    s->parent->color = BLACK;
                    s->parent->parent->color = RED;
                    RightRotate(s->parent->parent);
                }
            }
            else
            {
                if (s->parent == s->parent->parent->right) //父节点是右结点
                {
                    uncle = s->parent->parent->left;
                    if (uncle->color == RED) //叔结点为红色
                    {
                        //父节点和叔结点都变为黑色
                        s->parent->color = BLACK;
                        uncle->color = BLACK;
                        //祖父结点变为红色
                        s->parent->parent->color = RED;
                        //将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色
                        s = s->parent->parent;
                    }
                    else //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑)
                    {
                        if (s == s->parent->left) //如果调整的结点在左结点
                        {
                            s = s->parent;  //先将s指向s的父结点
                            RightRotate(s); //再右转
                        }
                        //如果调整的结点在右结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转
                        s->parent->color = BLACK;
                        s->parent->parent->color = RED;
                        LeftRotate(s->parent->parent);
                    }
                }
            }
        }
        root->color = BLACK; //最后始终将根节点置为黑色
    }

    //查找key结点
    RBTNode<Type> *Search(RBTNode<Type> *root, Type key) const
    {
        if (root == Nil) //root为空，或key和根的key相同
        {
            return Nil;
        }

        if (root->key == key)
        {
            return root;
        }
        if (key < root->key)
        {
            return Search(root->left, key);
        }
        else
        {
            return Search(root->right, key);
        }
    }

    /* 将u的子节点指针指向u改变指向v，将v的父节点改变为指向u的父节点 * up * \ * u * / \ * ul ur * / \ * v ulr * \ * rv */
    void Transplant(RBTNode<Type> *u, RBTNode<Type> *v)
    {
        if (u->parent == Nil) //u的父节点为空
        {
            root = v; //直接令根root为v
        }
        else if (u == u->parent->left) //u父节点不为空，且u在左子树
        {
            u->parent->left = v;
        }
        else //u在左子树
        {
            u->parent->right = v;
        }
        v->parent = u->parent;
    }

    /* 找到最左结点(最小) * xp * \ * x * / \ * xl xr * / \ * xll xlr */
    RBTNode<Type> *Minimum(RBTNode<Type> *x)
    {
        if (x->left == Nil)
        {
            return x;
        }
        return Minimum(x->left);
    }

    //删除红黑树结点z
    void Remove(RBTNode<Type> *z)
    {
        RBTNode<Type> *x = Nil;
        RBTNode<Type> *y = z;    //y记住传进来的z结点
        Color ycolor = y->color; //
        if (z->left == Nil)      //z只有右孩子
        {
            x = z->right;
            Transplant(z, z->right);
        }
        else if (z->right == Nil) //z只有右孩子
        {
            x = z->left;
            Transplant(z, z->left);
        }
        else //右左孩子和右孩子
        {
            y = Minimum(z->right); //y是z右子树的的最左子树
            ycolor = y->color;
            x = y->right;
            if (y->parent == z) //z的右子结点没有左节点或为Nil
            {
                x->parent = y;
            }
            else //z的右子结点有左节点或为Nil
            {
                Transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }
            Transplant(z, y);
            //改变指向
            y->left = z->left;
            z->left->parent = y;
            y->color = z->color;
        }
        if (ycolor == BLACK)
        {
            Remove_Fixup(x);
        }
    }

    //红黑树删除调整
    void Remove_Fixup(RBTNode<Type> *x)
    {
        while (x != root && x->color == BLACK) //当结点x不为根并且它的颜色不是黑色
        {
            if (x == x->parent->left) //x在左子树
            {
                RBTNode<Type> *w = x->parent->right; //w是x的兄结点

                if (w->color == RED) //情况1
                {
                    w->color = BLACK;
                    x->parent->color = RED;
                    LeftRotate(x->parent);
                    w = x->parent->right;
                }
                if (w->left->color == BLACK && w->right->color == BLACK) //情况2
                {
                    w->color = RED;
                    x = x->parent;
                }
                else
                {
                    if (w->right->color == BLACK) //情况3
                    {
                        w->color = RED;
                        w->left->color = BLACK;
                        RightRotate(w);
                        w = x->parent->right;
                    }
                    //情况4
                    w->color = w->parent->color;
                    w->parent->color = BLACK;
                    w->right->color = BLACK;
                    LeftRotate(x->parent);
                    x = root; //结束循环
                }
            }
            else //x在右子树
            {
                RBTNode<Type> *w = x->parent->left;
                if (w->color == RED) //情况1
                {
                    w->parent->color = RED;
                    w->color = BLACK;
                    RightRotate(x->parent);
                    w = x->parent->left;
                }
                if (w->right->color == BLACK && w->right->color == BLACK) //情况2
                {
                    w->color = RED;
                    x = x->parent;
                }
                else
                {
                    if (w->left->color == BLACK) //情况3
                    {
                        w->right->color = BLACK;
                        w->color = RED;
                        LeftRotate(w);
                        w = x->parent->left;
                    }
                    //情况4
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->left->color = BLACK;
                    RightRotate(x->parent);
                    x = root; //结束循环
                }
            }
        }
        x->color = BLACK;
    }

    //销毁红黑树
    void destroy(RBTNode<Type> *&root)
    {
        if (root == Nil)
        {
            return;
        }
        if (root->left != Nil)
        {
            destroy(root->left);
        }
        if (root->right != Nil)
        {
            destroy(root->right);
        }
        delete root;
        root = NULL;
    }

    //中序遍历打印结点详细的结点颜色
    void InOrderPrint(RBTNode<Type> *node)
    {
        if (node == Nil)
        {
            return;
        }
        if (node->left != NULL)
        {
            InOrderPrint(node->left);
        }
        cout << node->key << "(" << ((node->color == BLACK) ? "BLACK" : "RED") << ")"
             << " ";
        if (node->right != Nil)
        {
            InOrderPrint(node->right);
        }
    }

private:
    RBTNode<Type> *root; //根指针
    RBTNode<Type> *Nil;  //外部结点，表示空结点，黑色的
};

int main(int argc, char *argv[])
{
    RBTree<int> rb;

    int arr[] = {10, 7, 8, 15, 5, 6, 11, 13, 12};
    int n = sizeof(arr) / sizeof(int);
    for (int i = 0; i < n; i++)
    {
        rb.Insert(arr[i]);
    }

    rb.InOrder();
    cout << endl;
    rb.InOrderPrint();
    cout << endl;
    rb.Remove(10);
    rb.InOrder();
    cout << endl;
    rb.Remove(21);
    return 0;
}