红黑树

红黑树的特征如下

每个结点不是红色就是黑色 不可能有连在一起的红色结点 根结点都是黑色 每个红色结点的两个子结点都是黑色 任一结点到其子树中每个叶子节点的路径都有相同数量的黑色结点

那么问题来了,如何在删除和插入数据的时候保证以上性质呢,红黑树的策略就是改变颜色和旋转,改变颜色很好理解,那么旋转是什么呢?

旋转分为左旋和右旋

左旋

如下图所示左图为旋转前,右图是旋转后,是以5为根结点从左向右旋转,就是逆时针旋转

右旋

如下图所示左图为旋转前,右图是旋转后,是以5为根结点从右向左旋转,就是顺时针旋转

旋转和颜色变换规则

1.变颜色的情况:当前结点的父亲是红色,且它的祖父结点的另一个子结点(叔叔结点)也是红色。

(1)把父节点设为黑色 (2)把叔叔也设为黑色 (3)把祖父也就是父亲的父亲设为红色 (4)把指针定义到祖父结点设为当前要操作的

2.左旋:当前父结点是红色,叔叔是黑色的时候,且当前的结点是右子树,以父结点作为左旋。不需要改变颜色。

3.右旋:当前父结点是红色,叔叔是黑色的时候,且当前的结点是左子树。

(1)把父结点变为黑色 (2)把祖父结点变为红色 (爷爷) (3)以祖父结点旋转(爷爷)

插入数据示例

假设有如下的红黑树,符合红黑树的特征

现在插入数据6,颜色假设为红色,这样就不符合红黑树的特征,所以就要对其进行变换

变换过程如下:

1.因为父结点7和叔叔结点10都是红色,所以首先颜色变换,将父结点7和叔叔结点10变为黑色,祖父结点8变为红色,当前结点变为祖父结点8,依然不符合红黑树特征,继续变换

2.因为父结点5为红色,叔叔结点20为黑色,且当前结点为右子树,那么对父结点5进行左旋操作,并且当前结点设置为父结点5,依然不符合红黑,继续变换

3.因为父结点8为红色,叔叔结点20为黑色,当前结点为左子树,那么先将父结点8变为黑色,祖父结点15变为红色,那么再对祖父结点15进行右旋操作,同样当前结点变为祖父结点15,至此现在的红黑树已经符合特征,变换完成

可以看出变换完的红黑树结构依然稳定,所以红黑树就解决了插入和删除的问题

红黑树的应用

JDK HashMap JDK TreeMap JDK TreeSet Windows文件搜索

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【数据分析可视化】公式、坐标轴

    瑞新
  • Linux的体系结构

    less命令 与 more命令 非常类似,但less命令 可以更加随意地浏览文件,而且 less 在查看之前不会加载整个文件。

    瑞新
  • 【力扣】_92反转链表II

    瑞新
  • 30 张图带你彻底理解红黑树

    本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难...

    智能算法
  • 想了解概率图模型?你要先理解图论的基本定义与形式

    选自Dev To 作者:vaidehijoshi等 机器之心编译 参与:蒋思源、李泽南 图论一直是数学里十分重要的学科,其以图为研究对象,通常用来描述某些事物之...

    机器之心
  • 漫画:什么是AVL树?(修订版)

    对于AVL树的每一个结点,平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的...

    小灰
  • 漫画:什么是平衡二叉树?

    对于AVL树的每一个结点,平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的...

    小灰
  • 红黑树(一):构建红黑树

    前两篇文章谈了B-Tree和B+Tree,它们属于多路平衡树,所有叶子结点都在同一层,除了这两种平衡树, 我们熟知的还有平衡二叉树和红黑树。这一篇文章就来看看如...

    每天学Java
  • BTree,B-Tree,B+Tree,B*Tree都是什么

           3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

    阳光岛主
  • 漫画:什么是红黑树?(下篇)

    上周,我们初步介绍了红黑树存在的意义,以及红黑树的插入操作,没看过的小伙伴可以点击下面链接:

    小灰

扫码关注云+社区

领取腾讯云代金券