• 144802

    文章

  • 854

    评论

  • 13

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

理解红黑树的变色及旋转


二叉查找树(Binary Search Tree)擅长数据的查找。它的特点是:

对于任意节点,它的左子树上的所有节点的值都小于它,而它的右子树上的所有节点的值都大于它。

红黑树(Red-Black Tree)本质上也是二叉查找树,但它额外引入了5个条件:

  1. 节点只能是黑色或红色;
  2. 根节点必须是黑色;
  3. 所有NIL节点都是黑色;
  4. 一条路径上不能出现相邻的两个红色节点;
  5. 在任何递归子树内,根节点到叶子节点的所有路径上包含相同数目的黑色节点。

NIL即Nothing In Leaf,它是一种虚拟节点,出现于任何实际子节点不足2个的节点上:

条件5提到的黑色节点,包括NIL节点。当插入的节点是黑色时,红黑树必定不满足条件5。而当插入的节点是红色时,红黑树反而仍有可能满足条件5。

因此,新插入红黑树的节点默认是红色。

在Java中,TreeMap实现了基于红黑树(Red-Black Tree)的NavigableMap接口。此映射根据其键的自然顺序进行排序,或者根据创建映射时提供的Comparator进行排序,具体取决于使用的构造方法。

TreeMap类中,putdelete方法分别依赖私有方法fixAfterInsertionfixAfterDeletion。前者用于对插入的节点进行调整,后者用于对删除的节点进行调整。

本文以fixAfterInsertion为例。以下是此方法的部分源码。

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;
    // 如果x不为空,也不是根节点,并且x的父节点的颜色是红色
    while (x != null && x != root && x.parent.color == RED) {
        // 如果x的父节点是x的祖父节点的左子节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 节点y是x的祖父节点的右子节点
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            // 如果y的颜色是红色
            if (colorOf(y) == RED) {
                // 设置x的父节点为黑色
                setColor(parentOf(x), BLACK);
                // 设置y的颜色为黑色
                setColor(y, BLACK);
                // 设置x的祖父节点为红色
                setColor(parentOf(parentOf(x)), RED);
                // 以x的祖父节点作为x,再次执行循环判断
                x = parentOf(parentOf(x));
                // 如果y的颜色是黑色
            } else {
                // 如果x是父节点的右子节点
                if (x == rightOf(parentO8f(x))) {
                    // 以x的父节点作为x
                    x = parentOf(x);
                    // 将x左旋
                    rotateLeft(x);
                }
                // 设置x的父节点为黑色
                setColor(parentOf(x), BLACK);
                // 设置x的祖父节点为红色
                setColor(parentOf(parentOf(x)), RED);
                // 将x的祖父节点右旋
                rotateRight(parentOf(parentOf(x)));
            }
            // 如果x的父节点是祖父节点的右子节点
        } else {
            ...
        }
    }
    root.color = BLACK;
}
// 此处不再给出rotateLeft、rotateRight方法的源码

当新插入节点a的父节点b也是红色时,有两种情形:

1)b的兄弟节点是黑色。

当a是b的右子节点,而b是a的祖父节点的左子节点时,红黑树的变化如图所示:

上图中的红黑树发生了两次旋转:

第一次,b向左旋转,成为a的左子节点。此时的情形与首次插入的a位于b的左侧的情形完全相同。

第二次,当前位置的a的父节点向右旋转,成为a的右子节点。

当a是b的左子节点,而b是a的祖父节点的右子节点时,红黑树的变化如图所示:

上图中的红黑树发生了两次旋转:

第一次,b向右旋转,成为a的右子节点。此时的情形与首次插入的a位于b的右侧的情形完全相同。

第二次,当前位置的a的父节点向左旋转,成为a的左子节点。

2)b的兄弟节点是红色。

此时,a、b、b的兄弟节点都是红色,红黑树的变化如图所示:

这种情形比较简单,将b、b的兄弟节点置为黑色,同时将a的祖父节点c置为红色,即可保持两分支的黑色节点数量相同。

由于c是红色,当c不是根节点并且c的父节点的颜色也是红色时,须继续依照以上两种情形向上判断并执行相应操作。


695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

0条评论

Loading...


发表评论

电子邮件地址不会被公开。 必填项已用*标注

自定义皮肤 主体内容背景
打开支付宝扫码付款购买视频教程
遇到问题联系客服QQ:419400980
注册梁钟霖个人博客