图解红黑树-算法导论-java实现基于HashMap1.8

代码链接: 整体代码

红黑树的定义

Note:假如一个节点没有字节点或者是父节点,则该节点相应指针属性为nil

1.每个节点或者是红色的,或者是黑色的.
2.根节点是黑色的.
3.每个叶节点(nil)是黑色的.
4.假如一个节点是红色的,则它的两个子节点都是黑色的.
5.对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点.

先定义一下代码中的数据结构

public class RBTree<Key extends Comparable<Key>, Value> {        private static final boolean RED = true;    private static final boolean BLACK = false;        private Node root;       //头节点        private class Node {        Key key;              //使用来比较的键        Value value;          //使用来保存真正的值        Node left, right;     //左右子节点        /* 能否是红节点 true表示红节点(与父亲节点的链接为红色链接) false表示黑节点(与父亲节点的链接为黑色链接) */        Node parent;        boolean red;                Node(Key key, Value value, boolean color) {            this.key = key;            this.value = value;            this.red = color;        }                public String toString() {            return "[" + key + "," + value + "," + (red?"RED":"BLACK") + "]";        }    }        private boolean isRed(Node h) {        if (h == null) return false;        return h.red == RED;    }}

基础知识:旋转

左旋转:

image.png

代码:

/* 左旋转 */    private Node rotateLeft(Node root, Node p) {        Node r, pp, rl;        if (p != null && (r = p.right) != null) {            if ((rl = p.right = r.left) != null) rl.parent = p;            if ((pp = r.parent = p.parent) == null) {                (root = r).red = false;            } else if (pp.right == p) {                pp.right = r;            } else {                pp.left = r;            }            p.parent = r;            r.left = p;        }        return root;    }

右旋转

image.png

代码:

/* 右旋转 */    private Node rotateRight(Node root, Node p) {        Node l, pp, lr;        if (p != null && (l = p.left) != null) {            if ((lr = p.left = l.right) != null) lr.parent = p;            if ((pp = l.parent = p.parent) == null) (root = l).red = false;            else if (pp.left == p) pp.left = l;            else pp.right = l;                        l.right = p;            p.parent = l;        }        return root;    }

插入

插入主要分两步:

1.先按照二叉搜索的做法把一个新节点插入到红黑树中.
2.而后再从该节点向上进行调整

插入到红黑树中

这个就比较简单了,插入的元素key

假如key小于当前节点,那进入左子树
假如key大于当前节点,那进入右子树,
假如key等于当前节点,相当于升级该节点,直接返回
假如当前节点为null,则表示这个是要插入的地方

    public void put(Key key, Value value) {        root = put(root, key, value);        if (root != null) root.red = BLACK;    }        /* 把key插入到红黑树中, */    private Node put(Node h, Key key, Value value) {        if (h == null) return new Node(key, value, RED);        for (Node p = h; ; ) {            int cmp = key.compareTo(p.key);            Node xp = p;            if ((p = (cmp < 0 ? p.left : p.right)) == null || cmp == 0) {  //生成节点 起始节点颜色是红色                if (cmp == 0) {   //升级节点信息                    xp.value = value;                    break;                }                Node node = new Node(key, value, RED);                 if (cmp < 0) xp.left = node;  //新生成的节点在左侧                else xp.right = node;         //新生成的节点在右侧                node.parent = xp;                                root = balance_insertion(node); //调整节点                break;            }        }        return root;    }

调整添加节点

为什么选择每次插入的节点都是红色呢?是由于假如父节点是黑色那就不需要做调整了,由于它不会影响红黑树的五个性质.

p : 当前节点
xp : 当前节点的父亲节点
xpp: 当前节点的父亲节点的父亲节点
xppr: 当前节点的父亲节点的父亲节点的右孩子,也就是当前节点的叔叔节点

所以我的重点是放在父节点是红节点的时候会出现什么样的情况?
现在我们探讨的都是xp是xpp的左孩子(右孩子是同样的思想和思路),并且p和xp是红色节点,xpp是黑色节点

情况1: xppr是红色的

操作:
xp和xppr设置为黑色,把xpp设置为红色.
当前节点设置为xpp,向上传递红色,继续检查

tree_put_1.png

情况2: xppr是黑色的并且p是xp的左孩子

操作:
xp设置为黑色,把xpp设置为红色,而后对xpp右旋
当前节点没有变化,其实它的父亲已经变为黑色,向上传递后基本就结束调整了

tree_put_1(2).png

情况3: xppr是黑色的并且p是xp的右孩子

操作:
把当前节点的红色左旋到左侧去,而后就转化成了情况2

tree_put_1(3).png

对应代码

我针对代码的情况花了下面这张图:

TreeNode(1).png

/**     *      * @param root 红黑树的根节点(注意红黑树根节点不肯定是链表的头节点)     * @param x    新插入到红黑树中的节点     * @return     返回红黑树的根节点     */    private Node balanceInsertion(Node root, Node x) {            /*             * 先将新插入的节点x的元素设置为红色  (关于红黑树的基本知识假如有不了解的能参考我的另一篇博客图解红黑树)             * xp = x.parent x的父亲             * xpp = x.parent.parent x的父亲的父亲             * xppl = x.parent.parent.left x的父亲的父亲的左孩子             * xppr = x.parent.parent.right x的父亲的父亲的右孩子             * 插入的时候大情况分为4种:             * 1. xp是null,表明x是根节点,因而直接把x的颜色设置为黑色返回就可             * 2. xp是黑节点或者者xp是根节点都能直接返回根节点,简单解释一下:             *    - 假如xp是黑节点,又由于插入的x是红节点,因而不会影响整棵树的平衡性能直接返回             *    - 假如xp是根节点,此时不论xp是黑节点或者者是红节点,最终xp都会变成黑节点由于它是根节点,所以也能直接返回             * Note:假如1,2都没有发生,那么此时需要注意到x是红节点 xp也是红节点 还有一点由于xp是红节点,那xpp必然是黑节点             * 3. 假如xp是xpp的左链接             *    3(1).假如xpp的右链接xppr是红节点那表明xpp的两个孩子同时是红节点,因而直接颜色转换,而后x=xpp依次向上递归             *    3(2).假如xppr不是红节点             *         3(2)(1). 假如x是xp的右孩子,那需要通过一次左旋转来把2个红节点旋转在左边             *         3(2)(2). (不论是通过旋转到左边还是本身就是在左边)目前两个2节点都在左边,通过一次右旋转后继续for循环操作             * 4. 假如xp是xpp的右链接             *    3(1).假如xpp的左链接xppl是红节点那表明xpp的两个孩子同时是红节点,因而直接颜色转换,而后x=xpp依次向上递归             *    3(2).假如xppl不是红节点             *         3(2)(1). 假如x是xp的左孩子,那需要通过一次右旋转来把2个红节点旋转在右边             *         3(2)(2). (不论是通过旋转到右边还是本身就是在右边)目前两个2节点都在右边,通过一次左旋转继续for循环操作             *                   */        x.red = true;        for (Node xp, xpp, xppl, xppr;;) {            if ((xp = x.parent) == null) {                       // 情况1                x.red = false;                return x;            }            else if (!xp.red || (xpp = xp.parent) == null)       // 情况2                return root;            if (xp == (xppl = xpp.left)) {                       // 情况3                if ((xppr = xpp.right) != null && xppr.red) {    // 情况3(1)                    xppr.red = false;                    xp.red = false;                    xpp.red = true;                    x = xpp;                }                else {                                           // 情况3(2)                    if (x == xp.right) {                         // 情况3(2)(1)                        root = rotateLeft(root, x = xp);                        xpp = (xp = x.parent) == null ? null : xp.parent;                    }                    if (xp != null) {                           // 情况3(2)(2)                        xp.red = false;                        if (xpp != null) {                            xpp.red = true;                            root = rotateRight(root, xpp);                        }                    }                }            }            else {                                             // 情况4                if (xppl != null && xppl.red) {                // 情况4(1)                    xppl.red = false;                    xp.red = false;                    xpp.red = true;                    x = xpp;                }                else {                                          // 情况4(2)                    if (x == xp.left) {                         // 情况4(2)(1)                        root = rotateRight(root, x = xp);                        xpp = (xp = x.parent) == null ? null : xp.parent;                    }                    if (xp != null) {                           // 情况4(2)(2)                        xp.red = false;                        if (xpp != null) {                            xpp.red = true;                            root = rotateLeft(root, xpp);                        }                    }                }            }        }    }

图解插入过程:

TreeNode_put(2).png

删除

我先假设已经理解过二叉查找/搜索树的删除过程,假如不了解的话请先移步二叉查找树 Java实现.
我们先分三步走:

1. 先找到这个被删除的节点
2. 删除这个节点并且使用子节点取代这个删除节点的位置
3. 替代的节点有可可以会造成不满足红黑树的性质,这一步属于调整

假如看不懂的话没关系,接下来会一步步来分析这三个步骤.

1.寻觅节点

删除一定得先找到这个被删除的节点,这个不使用多说,直接看代码就行.

    private Node findNode(Key key) {        Node p;        for (p = root; p != null; ) {            int cmp = key.compareTo(p.key);            if (cmp < 0) p = p.left;            else if (cmp > 0) p = p.right;            else return p;        }        return null;    }

2. 找到取代的位置

p: 被删除节点
x: 替代节点

同二叉搜索树一样,有三种情况需要分析.

1.假如被删除节点p没有左右孩子,替代节点暂时是他自己,至于为什么,在调整的时候会分析.
2.假如被删除节点p只有一个孩子,替代节点是他的不为nil的子节点.
3.假如被删除节点p左右都有孩子,先找到p的右子树的最小节点,而后交换,情况3就变成了情况1或者者2.

文字假如难以了解,就看下面的图.

tree_del(1).png

对应代码:

final Node removeTreeNode(Node h) {        if (h == null) return null;        // 在红黑树中删除 删除后后继点放在replacement        Node p = h, pl = h.left, pr = h.right, replacement;        if (pl != null && pr != null) {            /**             * 整个部分就是在做一件事:就是把p与后继节点交换而后变化成了删除情况的1,2 并且找到对应的替代点replacement             */            Node s = pr, sl;            while ((sl = s.left) != null)                 s = sl;            boolean c = s.red;            s.red = p.red;            p.red = c; // 交换颜色            Node sr = s.right;            Node pp = p.parent;            if (s == pr) { // p是s的直接父亲                p.parent = s;                s.right = p;            } else {                Node sp = s.parent;                if ((p.parent = sp) != null) {                    if (s == sp.left)                        sp.left = p;                    else                        sp.right = p;                }                if ((s.right = pr) != null)                    pr.parent = s;            }            p.left = null;            if ((p.right = sr) != null)                sr.parent = p;            if ((s.left = pl) != null)                pl.parent = s;            if ((s.parent = pp) == null)                root = s;            else if (p == pp.left)                pp.left = s;            else                pp.right = s;            if (sr != null)     //假如找到的后继节点的右节点不为空(由于后继节点的左节点一定是空的),替代节点就为后继节点的右孩子                replacement = sr;            else                //假如后继节点左右孩子都是空 那替代节点就暂时是它本身                replacement = p;        } else if (pl != null)  //假如右节点为空 替代节点是左节点            replacement = pl;        else if (pr != null)    //假如左节点为空 替代节点是右节点            replacement = pr;        else                    //假如左右节点都空 替代节点是其本身            replacement = p;        /**         * 假如替代节点不是本身的话即可以直接删除p了,由于后续调整的事情跟p没有任何关系了         * 假如替代节点是本身的话需要先做完调整而后再删除         */        if (replacement != p) {              Node pp = replacement.parent = p.parent;            if (pp == null)                root = replacement;            else if (p == pp.left)                pp.left = replacement;            else                pp.right = replacement;            p.left = p.right = p.parent = null;        }                Node r = p.red ? root : balanceDeletion(root, replacement);        if (replacement == p) { // 删除p            Node pp = p.parent;            p.parent = null;            if (pp != null) {                if (p == pp.left)                    pp.left = null;                else if (p == pp.right)                    pp.right = null;            }        }        return root;    }

调整节点

我们先了解第一个事情:假如被删除的节点p是一个红色节点,会不会对整棵树有所影响.

性质1. 没有影响,由于没有改变任何一个节点的颜色的事情发生过
性质2. 没有影响,由于删除的节点是红色,所以不可可以是根节点,因而对根节点没有影响.
性质3. 没有影响,由于没有改变任何叶节点.
性质4. 由于我们删除的是红节点p,那么p的父亲和孩子都是黑节点,所以替代的节点是黑色节点,与父亲节点连上后也不会影响.
性质5. 由于p是红色节点,所以不会影响经过p的所有路径上的黑色节点的数目,因而也不影响.

既然对整棵树都没有影响,所以即可以直接删除,比方上图情况1中能直接删除节点X.—也就是不需要进行调整

那假如删除的节点p是一个黑色节点呢?

答案是有影响,

性质2. 假如p的一个红色的孩子成为新的根节点成为了根节点,就会产生影响.
性质4. 假如p的父亲节点和孩子节点都是红色的,就违背了性质4.
性质5.由于p是黑色节点,所以p的所有祖先的所有经过p的路径上的黑色节点的数目减少了1,因而违背了性质5.

del_1(1).png

当将p删除时,将其黑色下推给节点x,那x在原有的颜色基础上再加了一层黑色,这样能满足性质5,但是不可以满足性质1,由于节点x可可以既不是红色又不是黑色,违背了性质1

删除的所有情况

为了方便了解后面的情况,我们现在假设替代节点x是继承了节点p的黑色,从而x在原有的颜色基础上再加了外面一层黑色,这个不是真实存在的,是为了说明后面的情况所虚拟出来的一个概念(不了解没关系,继续看,后面会分析到为什么要虚拟出来这样的一个概念)

我们把从p节点继承来的黑色加上x的颜色存为组合,比方x的颜色是红色就叫黑-红组合,x的颜色是黑色就叫黑-黑组合.

简单的三种情况

1. 假如x是空节点或者者是根节点,那直接返回
2. 假如x的父亲节点是空,也就是x是新的根节点,无论x原来的颜色是红或者黑,直接把x的颜色设置为黑色返回就可.
3. 假如x的节点是红色,那就是黑-红组合,直接把x变成黑色既可,看下图中的例子.

tree_del_condition(1).png

            if (x == null || x == root)                return root;            else if ((xp = x.parent) == null) {                x.red = false;                return x;            } else if (x.red) {                x.red = false;                return root;            }

黑-黑组合中的四种情况

p : 被删除节点
x : 替代节点
xp: x的父亲节点
w: x的兄弟节点
c: 表示任意颜色
Note: 现在假设x在x父亲节点xp的左侧(右侧是同样的思想和思路)

情况1.黑-黑 x兄弟节点w是红色

操作:
xp的颜色变为红色
w的颜色变为黑色
对xp左旋转

了解:
是为了把情况1转换成情况2或者者情况3或者者情况4.

tree_del_condition_1.png

      if ((xpr = xp.right) != null && xpr.red) {   //情况1:黑-黑 兄弟节点w是红色                xpr.red = false;                xp.red = true;                root = rotateLeft(root, xp);                            xpr = (xp = x.parent) == null ? null : xp.right;  //升级xp和xpr     }

情况2.黑-黑 x兄弟节点w是黑色并且w的两个子节点都是黑色的

操作:
1.x移到xp的位置
2.把w的颜色变为红色

了解:
把x移到xp的位置是为了把x的黑色传递给父亲节点,此时看看发生了哪些变化?

1. x只剩下了自己的颜色
2. xp的祖先到xp左侧的nil节点经过的黑色节点没有变化,但是xp的祖先到xp右侧的nil节点都加了1,这个1是来自xp中的黑色节点,所以需要把xp右孩子w的颜色设置为红色就可.
3.产生新的x,xp,w

通过下图能帮助了解:

del_black_black_2.png

    Node sl = xpr.left, sr = xpr.right;    if ((sr == null || !sr.red) && (sl == null || !sl.red)) {  //情况2:黑-黑 x的兄弟节点xpr是黑色并且它的两个字节点是黑色的            xpr.red = true;            x = xp;    }

情况3.黑-黑 x兄弟节点w是黑色并且w的左孩子是红色的,w的右孩子是黑色的

操作:
w的颜色变为红色
w的左孩子颜色变为黑色
对w右旋转

了解:
是为了把情况3转换成情况4.

red_black_black_3(1).png

       if (sr == null || !sr.red) {  //情况3:黑-黑 x的兄弟节点xpr是黑色并且它的左孩子是红色,右孩子是黑色或者者空            if (sl != null)                sl.red = false;                xpr.red = true;                root = rotateRight(root, xpr);                xpr = (xp = x.parent) == null ? null : xp.right;             }       }

情况4.黑-黑 x兄弟节点w是黑色并且w的右孩子是红色的,w的左孩子的颜色任意

操作:
xp与w颜色互换
w的右孩子颜色变为黑色
xp左旋

了解:
xp与w颜色互换为了保证w的左右孩子那一侧经过的黑节点数量没有变化.
xp左旋是让经过x那一侧的黑色节点数量加1,
xp旋转后会对原价w左孩子没有影响(由于w左孩子已经被旋转到xp的右侧了),但是对w的右孩子的经过的黑色节点数量减1了,因而需要把w的右孩子颜色变为黑色.(下图中有例子,能比照着看看效果)

del_black_black_4.png

                       if (xpr != null) {             //情况4:黑-黑 x的兄弟节点xpr是黑色并且它的右孩子是红色,左孩子能为任意颜色或者者空                            xpr.red = (xp == null) ? false : xp.red;                            if ((sr = xpr.right) != null)                                sr.red = false;                        }                        if (xp != null) {                            xp.red = false;                            root = rotateLeft(root, xp);                        }                        x = root;   //能直接到根节点了

对应的删除调整代码

  private Node balanceDeletion(Node root, Node x) {        for (Node xp, xpl, xpr;;) {            if (x == null || x == root)                return root;            else if ((xp = x.parent) == null) {                x.red = false;                return x;            } else if (x.red) {                x.red = false;                return root;            } else if ((xpl = xp.left) == x) { // 左链接                if ((xpr = xp.right) != null && xpr.red) {   //情况1:黑-黑 x的兄弟节点是红色                    xpr.red = false;                    xp.red = true;                    root = rotateLeft(root, xp);                                xpr = (xp = x.parent) == null ? null : xp.right;  //升级xp和xpr                }                if (xpr == null)                    x = xp;                else {                    Node sl = xpr.left, sr = xpr.right;                    if ((sr == null || !sr.red) && (sl == null || !sl.red)) {  //情况2:黑-黑 x的兄弟节点xpr是黑色并且它的两个字节点是黑色的                        xpr.red = true;                        x = xp;                    } else {                        if (sr == null || !sr.red) {  //情况3:黑-黑 x的兄弟节点xpr是黑色并且它的左孩子是红色,右孩子是黑色或者者空                            if (sl != null)                                sl.red = false;                            xpr.red = true;                            root = rotateRight(root, xpr);                            xpr = (xp = x.parent) == null ? null : xp.right;                        }                        if (xpr != null) {             //情况4:黑-黑 x的兄弟节点xpr是黑色并且它的右孩子是红色,左孩子能为任意颜色或者者空                            xpr.red = (xp == null) ? false : xp.red;                            if ((sr = xpr.right) != null)                                sr.red = false;                        }                        if (xp != null) {                            xp.red = false;                            root = rotateLeft(root, xp);                        }                        x = root;   //能直接到根节点了                    }                }            } else { // symmetric                if (xpl != null && xpl.red) {                    xpl.red = false;                    xp.red = true;                    root = rotateRight(root, xp);                    xpl = (xp = x.parent) == null ? null : xp.left;                }                if (xpl == null)                    x = xp;                else {                    Node sl = xpl.left, sr = xpl.right;                    if ((sl == null || !sl.red) && (sr == null || !sr.red)) {                        xpl.red = true;                        x = xp;                    } else {                        if (sl == null || !sl.red) {                            if (sr != null)                                sr.red = false;                            xpl.red = true;                            root = rotateLeft(root, xpl);                            xpl = (xp = x.parent) == null ? null : xp.left;                        }                        if (xpl != null) {                            xpl.red = (xp == null) ? false : xp.red;                            if ((sl = xpl.left) != null)                                sl.red = false;                        }                        if (xp != null) {                            xp.red = false;                            root = rotateRight(root, xp);                        }                        x = root;                    }                }            }        }    }

总结

到此红黑树算是分析完了,因为完整代码有点多,我就不贴完整代码了,有兴趣的人能去RBTree.java里下载,里面有简单的测试.

参考:

1. 算法导论
2. java1.8 源代码