红黑树自平衡总结

红黑树性质：

•     根节点为黑色
•     节点不是红色就是黑色
•     每个叶子节点NIL为黑色
•     红色节点的两个子节点一定都是黑色
•     任意一个节点到叶子节点的路径都包含相同数量的黑色节点，俗称：黑高
•     （如果一个节点的存在黑子节点，那么该节点肯定有两个子节点）

当前节点为I，父节点为P，P节点的兄弟节点为U，P的父节点为PP（祖父节点）
1、当前节点为空，直接插入即可
2、插入的节点已经存在，直接替换即可
3、插入节点的父节点为【黑色节点】，找到父节点，直接插入即可。不会影响完美黑平衡
4、插入节点的父节点为【红色节点】
    4.1、叔叔节点存在，且为【红色节点】
    由红黑树的性质可知：红色节点不能相连，=》祖父节点肯定为黑色节点
    此时红黑层数情况是【黑红红】，最简单的处理方式就是改成【红黑红】
    处理方式：
        将P和U改为黑色
        PP改为红色
        将PP节点设置为当前节点，进行后续处理
    4.2、叔叔节点不存在或者叔叔节点是【黑色节点】且插入节点的父节点是祖父节点的左子节点
        4.2.1、插入节点为其父节点的左子节点（这个时候是LL双红的情况：当前节点为红色，当前节点的父节点为红色，当前节点为其父节点的左子节点）
        处理方式：
                变颜色：将P节点设置为黑色，将PP节点设置为红色
                对PP节点进行右旋
        4.2.2、插入节点为其父节点的右子节点（这个时候是LR双红的情况：当前节点为红色，当前节点的父节点为红色，当前节点为其父节点的右子节点）
        处理方式：
            对P节点进行左旋，这个时候就会变成LL双红
            此时按照4.2.1的处理方式处理
    4.3、叔叔节点不存在或者叔叔节点是【黑色节点】且插入节点的父节点为祖父节点的右子节点
        4.3.1、插入节点为其父节点的右子节点（这个时候是RR双红的情况：当前节点为红色，当前节点的父节点为红色，当前节点为其父节点的右子节点）
        处理方式：
            变颜色：将P节点设置为黑色，将PP节点设置为红色
            对PP节点进行左旋
        4.3.2、插入节点为其父节点的左子节点（这个时候是RL双红的情况：当前节点为红色，当前节点的父节点为红色，当前节点为其父节点的左子节点）
        处理方式：
            对P节点进行右旋，这个时候变成RR双红
            此时按照4.3.1的方式进行处理

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/113634022