红黑树（Red-Black Tree）

作者: None_Ling | 来源:发表于2017-12-18 16:58 被阅读35次

问题精选-数据结构
数据结构-红黑树
红黑树详解
数据结构与算法-红黑树
红黑树详解
红黑树
二叉树 - 红黑树
红黑树
JAVA8 TreeMap学习笔记
TreeMap集合方法API实例演示

定义

红黑树，本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

性质

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
通过红黑树的这五个特性可以保证：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

image.png

操作

红黑树本质上还是一颗二叉查找树，所以在插入/删除的操作上还是和普通二叉树插入的方式一致，只是在插入/删除完成后需要完成一些着色和旋转的Fix操作，来保证二叉树自平衡，由于Fix操作达到自平衡的程度和操作的差异，所以自平衡二叉树也衍生了很多种类。

插入操作的FixUp

修复情况有三种：

插入修复Case1

如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
如下图所示：

Case1修复前

Case1修复后

插入修复Case2

当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的右子

Case2修复前

Case2修复后

插入修复Case3

当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的左子

Case3修复前

Case3修复后

插入Fixup代码如下：

    /** From CLR */
    private void fixAfterInsertion(TreeMapEntry<K,V> x) {
        //  新插入节点先默认为红色
        x.color = RED;
        //  只有当插入节点的父节点是红色，才需要进行Fixup
        while (x != null && x != root && x.parent.color == RED) {
        //  如果是父节点是祖父节点的左子树    
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
        //  得到父节点的兄弟节点-Uncle节点
                TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));
        //  如果Uncle为红色的话，说明父节点、子节点、Uncle节点都是红色
                if (colorOf(y) == RED) {
        //  则将父节点和Uncle节点设置成黑色
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
        //  将祖父节点修改成红色
                    setColor(parentOf(parentOf(x)), RED);
        //  再检查祖父节点与其父节点的特性
                    x = parentOf(parentOf(x));
                } else {
        //  如果Uncle是黑色的话，因为原来没有叶子节点的时候，默认的nil是黑色的，如果加了一个红色节点，则会破坏性质5，导致到叶子节点的黑色节点数量不一致
        
        //  如果插入的节点是右子树,则先将父节点左旋，也就是旋转后，将原有的父节点做为新插入节点
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
        //  将该节点的父节点设置成BLACK
                    setColor(parentOf(x), BLACK);
        //  将祖父节点设置成红色
                    setColor(parentOf(parentOf(x)), RED);
        //  再将祖父节点右转，因为Uncle节点必然是黑色的，所以当父节点着成红色、右旋后，就可以保证旋转后的树能够保持左右子树平衡
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
          //  如果是父节点是祖父节点的右子树
          //  得到父节点的兄弟节点，Uncle节点
                TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        //  最后更新根节点的颜色为黑色
        root.color = BLACK;
    }

删除操作的FixUp

删除的FixUp会有四种情况（N为待删除的节点）
而对于删除操作的Fixup只针对黑节点的删除，因为红色节点被删除，并不会影响红黑树的所有特性，只有当黑节点被删除的时候，可能会影响特性4或者特性5.
因为黑节点被删除后，可能该节点还有红色的子节点链接后，会导致两个红色节点，而且也会影响从根节点到每个叶子节点的黑色节点的个数。

而对于黑节点丢失的修复方案有以下两种，其中Sib为Sibling-兄弟节点：

从Parent转，将Sib节点从黑色变成红色相当于从Parent开始到左右子树的黑色节点都减少1，接着往Parent递归调整，如果遇到Paren为红色节点时，则将Parent的红色节点变成黑色，来达到整颗树的从Parent的角度来平衡黑色节点数量，如果Parent还是黑色的话，则看是否可以从Parent的Sib获取，如果不能获取的话，则再继续往根节点的路径找
从Sib拿，将Sib的红色节点拿过来转成黑色，填补缺失的那个黑色节点。如果Sib有红色节点可以转的话，则整个红黑树从根节点到叶子节点的黑色节点数不会改变。

PS：从Parent转的方案，有可能会把从根节点到叶子节点的黑节点数量减少，因为如果一直遍历直到根节点都没有红色节点的话，由于将Sib节点从黑变成了红，也就相当于整体的所有左右子树的黑色节点都减少1

直到遇到红色的Parent，将该节点着成黑色来填补-1的黑节点树或者遇到Root节点，将整体的从根到叶子节点黑节点数量-1

所以对于红黑树删除的Rebalance-FixUp操作对应的上面两种方案：
Case1是为了平衡左右子树的高度，并且为将Sib为红色的情况转成Sib为黑色的情况
方案1从Parent的红色节点转成黑色节点对应着Case2
方案2从Sib拿红色节点转成黑色节点对应着Case3&Case4