红黑树


为什么要使用红黑树

当冲突的链表长度超过8个时,链表结构就会转为红黑树结构,这样做的好处是避免在极端条件的情况下冲突链表过长而导致查询效率非常慢
红黑树是一种近似平衡的二叉查找树,其主要的优点就是平衡,即左右子树高度几乎一致,以此来防止树退化为链表,通过这种方式来保障查找的时间复杂度为log(n)

红黑树

红黑树

红黑树要求
1.每个节点或者是黑色,或者是红色
2.根节点是黑色
3.每个叶子结点(这里的叶子结点不是传统的叶子结点,是指为空的叶子结点)是黑色
4.如果一个结点是红色的,则它的子结点必须是黑色的
5.从一个结点到该结点的子孙结点的所有路径上包含相同数目的黑结点
6.新加入到红黑树的节点为红色节点

在树的结构发生改变时,往往会破坏红色节点的孩子和父亲都不能是红色的和从任意节点到其子树中每个叶子结点的路径有相同数量的黑色节点这两个条件,需要通过调整使得查找树重新满足红黑树的条件

调整方式

颜色调整

转换节点的颜色

结构调整

左旋

左旋

序号 步骤
1 Y的左孩子设为X的右孩子,即β的父亲为X
2 将X的父亲设为Y的父亲
2.1 若X的父亲为空,则Y为根节点
2.2 X为他父亲的左节点,则Y为X父亲的左节点;X为他父亲的右节点,则Y为X父亲的右节点
3 X设为Y的左节点,即X的父亲为Y
static final class TreeNode extends LinkedHashMap.Entry {
    //指向父节点的指针 		TreeNode parent;
    //指向左孩子的指针 TreeNode left;
    //指向右孩子的指针 TreeNode right;
    //前驱指针,跟next属性相反的指向 TreeNode prev;
    //是否为红色节点 boolean red;
    //左旋方法如下
    static  TreeNode rotateLeft(TreeNode root,
                                            TreeNode x) {
        TreeNode y, parent, β;//x表示要调整的节点,y表示x的右节点,parent表示x的parent节点,β表示x的右孩子的左孩子节点
        //判断y,如果y为空则旋转没有意义
        if (y != null && (β = y.left) != null) {
            //设置的β父亲为x,β为x的右节点
            if ((β = y.left) != null)
                x.right = β;
            //判断x的父亲,为空,y为根节点,根节点的话就设置为黑色
            if ((parent = x.parent ) == null)
                (root = y).red = false;
                //判断x节点是左儿子还是右儿子
            else if (parent.left == x)
                parent.left = y;
            else
                parent.right = y;
            y.left = x;
            x.parent = y;
        }
        return root;
    }
}
右旋

右旋
右旋和左旋的原理相同

插入新节点调整

插入
插入新节点为红色是为了不违背特性5
当前节点(即,被插入节点)的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色
(1) 将“父节点”设为黑色。
(2) 将“叔叔节点”设为黑色。
(3) 将“祖父节点”设为“红色”。
(4) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作

调整
“当前节点”和“父节点”都是红色,违背“特性(4)”。将“父节点”设置“黑色”以解决这个问题。
但是,将“父节点”由“红色”变成“黑色”之后,违背了“特性(5)”:因为,包含“父节点”的分支的黑色节点的总数增加了1。 解决这个问题的办法是:将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”。关于这里,说明几点:第一,为什么“祖父节点”之前是黑色?这个应该很容易想明白,因为在变换操作之前,该树是红黑树,“父节点”是红色,那么“祖父节点”一定是黑色。 第二,为什么将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”;能解决“包含‘父节点’的分支的黑色节点的总数增加了1”的问题。这个道理也很简单。“包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”,既然这样,我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题; 但是,这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”,现在我们已知“叔叔节点”是“红色”,将“叔叔节点”设为“黑色”就能解决这个问题。 所以,将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”;就解决了该问题。
按照上面的步骤处理之后:当前节点、父节点、叔叔节点之间都不会违背红黑树特性,但祖父节点却不一定。若此时,祖父节点是根节点,直接将祖父节点设为“黑色”,那就完全解决这个问题了;若祖父节点不是根节点,那我们需要将“祖父节点”设为“新的当前节点”,接着对“新的当前节点”进行分析。


红黑树的查询

红黑树查询

红黑树的删除
被删除的D节点为红色。这种情况,则与D相关的颜色以及结构关系必然只有如下一种情况

D节点为红色
因为D为红色,所以P为黑色,同时DR不可能为红色(否则违反性质4)。同时由于性质5,则DR必为Nil,否则就D树来说,经过DR与不经过DR的路径的黑节点数必不相同。现在要删除D节点,只需要直接将D节点删除,并将DR作为P的左子节点

被删除的D节点为黑色

D为黑色
由于删除的D为黑色,删除后P的左子树的黑节点数必少1,此时刚好DR为黑色,并且删除后DR可以占据D的位置,然后再将DR的颜色改为黑色,刚好可以填补P左子树所减少的黑节点数。

被删除的D为黑色,且DR为Nil



转换后,虽然对于P树的左子树的黑节点数仍然会比右子树的黑节点数少1,但此时DR的兄弟(以前的S节点)现在已经变为SL,即已经由红色变为黑色,并且非常重要的此时的DR的兄弟节点SL的子结点(即:DR的两个侄子节点),要不就是红色节点要不就必为Nil节点,而这种情况正是D为黑色、S也黑色的情况

所有图片来源于网络。


文章作者: dinggc
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 dinggc !
评论
 上一篇
答辩知识架构及企业OA项目开发汇总 答辩知识架构及企业OA项目开发汇总
1.Vue框架 MVVM架构,model,view,viewmodel,model和view之间无法直接交互,通过viewmodel进行交互,创建新的模板,在模板中使用js函数创建监听器,使用vm_patch渲染页面完成数据模板的绑定,当数
下一篇 
hexo插件及优化 hexo插件及优化
hexo常用插件及优化 这里使用的主题为matery,闪烁之狐,matery主题的github仓库,作者提供的文档里已经给出了像代码高亮,拼音转换等插件,所以本文介绍的是除了作者提供的之外的其他简约插件。 matery使用需知 背景粒子和彩
  目录