专栏首页每天学Java红黑树(一):构建红黑树

红黑树(一):构建红黑树

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

对于平衡二叉树的构建,可以参考小程序中的文章(C++版)。

平衡二叉树

红黑树

红黑树属于平衡二叉树,但是并非严格意义上的平衡二叉树,因为平衡二叉树要求节点的左右子树高度差不超过1, 而红黑树放弃了这种高度平衡,利用对结点上色的操作来保证树相对平衡,这其中原因大概是维护一个绝对平衡的二叉树代价太大, 在插入操作比较频繁的情况下,其性能上的收益并不大(HashMap采用红黑树而不是平衡二叉树的原因)。

但如果插入频率小或者只有一次构建,那么平衡二叉树的查询性能还是比红黑树高。

性质

1> 所有结点颜色是黑色或者红色

2> 根结点为黑色

3> 每个叶子结点为黑色(这里的叶子结点指的是为null的结点)

4> 红色结点的孩子结点必须是黑色结点

5> 任意一结点到每个叶子结点所经过的黑结点个数相同

从上面的性质我们大概知道红黑树的结构,树根为黑色,不存在连续的两个红色结点,每个子树分支的黑结点个数相同,如下图

平衡操作

同平衡二叉树一样,构建过程中,平衡逻辑是最关键的,通常情况下,我们插入的结点默认是红色,因为这样不会打破性质五,使得任一结点到每个叶子结点所经过的黑结点个数相同。

此时红黑树构建平衡分为4种情况:

情况一:红黑树为空树,此时插入结点充当根结点,上色为黑

情况二:插入结点已经存在,此时替换插入结点值即可

情况三:插入结点的位置,其父结点是黑色,此时平衡未打破,插入完成

情况四:插入结点的父结点是红色,此时平衡打破,需要进行平衡操作。

当情况四出现时候,说明需要进行平衡操作,此时操作逻辑如下:

  • 情况4.1:插入结点的父结点,不存在兄弟结点,且插入结点与父结点在方向上相同(同为左子树或右子树),此时需要进行右旋转或者左旋(根据父结点位置来决定, 图一是右旋转,图二是左旋)

图一的平衡过程是将-1设置为黑色,1设置为红色,以1结点为基准进行右旋

图二的平衡过程是将2设置为黑色,1设置为红色,然后以1结点为基本进行左旋。

注:也可以将-2/5设置为黑色,然后以1右旋/左旋,但是此时-1/2为红色,如果父结点为红色, 那么需要继续平衡

平衡结果:

  • 情况4.2:插入结点与父结点在结点方向上不同,父结点是右子树,插入结点是左子树或者父结点是左子树,插入结点是右子树,如下图,需要 先调整父结点,然后按照情况4.1进行调整
  • 情况4.3:插入结点的父结点,存在兄弟结点,此时由于性质5,那么改兄弟结点必然为红色,因为如果是黑色, 叔叔结点所在的子树的黑色结点就比插入结点的父结点所在子树的多了黑结点, 如下,如果1为黑色,那么性质5就被打破。此时平衡操作是:如果-1不是根结点,将-1设置为红色, -2和1设置为黑色,完成平衡,如果-1是根结点,那么只需要将-1和-2设置为红色即可。

平衡

构建过程

我们依次插入1,-1,-2,-3,2,5,4,3来看一下红黑树的构建的过程

插入1,构建根结点:情况一

插入-1,构建孩子结点:情况三

插入-2,失衡,情况4.1

插入-3,失衡,情况4.3

插入2,情况三,未失衡

插入5,失衡,情况4.1

插入4,失衡,情况4.3

插入3,失衡,情况4.1

到这里就构建完成了

相对于构建新增,红黑树的删除情况更为复杂,由于时间关系(这周只有一天休息加上绘图太费劲),留到下一次分享。

构建代码

红黑树构建源码

本文分享自微信公众号 - 每天学Java(gh_fddfb9d03324),作者:每天学Java

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-25

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关于索引以及B-Tree的实现

    对于多数的应用系统来说,查询数据的频率是远远高于写入或者更新数据的频率,在大数据量的场景中,常规的查询方式可能在效率上达不到预期, 此时我们需要对SQL查询语句...

    每天学Java
  • B+Tree实现图解

    与前一篇描述的B树相比,本篇文章所谈论的B+树在定义上似乎没有官方的定义,从论坛上看,目前还是对定义存在两点争论:

    每天学Java
  • 最短路径之弗洛伊德算法

    Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图...

    每天学Java
  • 约瑟夫环 队列+链表

    设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编...

    attack
  • 数据结构 | 每日一练(39)

    ——老子

    闫小林
  • 红黑树

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

    瑞新
  • 漫画:什么是AVL树?(修订版)

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

    小灰
  • 30 张图带你彻底理解红黑树

    小吴正在写红黑树的相关系列文章,不过内容太多,动画做起来比较慢,大家可以先看一下这篇红黑树的介绍,内容很不错。

    五分钟学算法
  • 漫画:什么是平衡二叉树?

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

    小灰
  • 30 张图带你彻底理解红黑树

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

    智能算法

扫码关注云+社区

领取腾讯云代金券