首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >红黑树

红黑树

作者头像
搬砖俱乐部
发布2019-06-15 17:27:09
8670
发布2019-06-15 17:27:09
举报
文章被收录于专栏:BanzClubBanzClub

性质

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

旋转

红黑树的平衡操作是通过旋转操作来实现的,分为左旋和右旋:

  • 左旋

Y为根结点,A为Y的右孩子,以Y-A为轴进行左旋,A为新的根结点,Y为A的左孩子,A原左孩子B为旋转后Y的右子,Y的左子和A的右子不变。

代码实现

  • 右旋

Y为根结点,X为Y的左孩子,以Y-X为轴进行右旋,X为新的根结点,Y为X的右孩子,X原右孩子R为旋转后Y的左子,Y的右子和X的左子不变。

代码实现

插入

红黑树的插入操作包括二叉搜索树的插入操作(左小右大)和红黑树平衡插入操作,平衡操作主要是为了让红黑树重新满足红黑树属性。而平衡插入操作是在固定几种情况的步骤下完成,所以,红黑树插入的时间复杂度仍为O(logn)。

插入操作

1、类似于二叉搜索树,按照左小右大原则,插入新元素

2、将新元素着成红色(根据红黑树的性质,着成红色,破坏的性质较少,可以更快调整平衡)

插入平衡操作

3、平衡新树

新树可能不满足红黑树的性质,需要进行插入平衡操作。那平衡操作面对的场景包括哪些呢,下面先分析一下:

3.1、插入结点为根

根据性质2,直接变为黑色;

3.2、插入结点的父结点为黑色

发现没有违反红黑树的性质,仍然是一颗红黑树;

3.3、插入结点的父结点为红色,父结点为祖父结点的左孩子

3.3.1、祖父结点的另一个子结点(右子)为红色

新结点是其父结点的左子或者右子,此时破坏了性质4,将父结点、叔结点的颜色着为黑色、祖父结点着为红色,就能使其祖父之下的子树满足红黑树,将其祖父结点作为新结点,继续判断祖父以上的红黑树是否满足红黑树;

3.3.2、祖父结点的另一个子结点(右子)为黑色,当前结点为是其父结点的左子结点

以祖父结点和父结点为轴,进行右旋转,然后将原父结点(旋转后仍然为父结点)着为黑色,原祖父结点(旋转后为父结点的右子)着为红色,如下图:

3.3.3、祖父结点的另一个子结点(右子)为黑色,当前结点为是其父结点的右子结点

以父结点与当前结点为轴,进行左旋转,发现变成3.3.2的情况。

3.4、插入结点的父结点为红色,父结点为祖父结点的右孩子(与3.3互为对称操作)

HashMap的红黑树插入平衡算法

删除

红黑树的删除操作同样需要两个步骤:二叉树的删除操作和删除平衡操作。

下面先分析一下二叉树删除结点的场景(理解继承结点的概念):

1.1、删除结点无子结点

1.2、删除结点只有一个子结点

1.3、删除结点存在两个子结点,在左子树或者右子树中找到继承结点

继承结点其实就是替换删除结点的位置,也就是比删除结点的左子树中的结点大,比删除结点的右子树中的结点小,所以在左子树中找最大值,或者在右子树中找最小值。(注:无论找哪个子树都可以满足情况,本文参考《算法导论-第三版》,所以也找左子树中的最大值)

如果在左子树中找的话,一定是找其左子的右子,直到找不到右子,这个值为左子树中最大值;如果在右子树中找的话,一定是找其右子的左子,直到找不到左子,这个值为右子树中的最小值。

继承结点移动到删除结点位置,继承结点的子(一定只有一个子)为继承结点父结点的子。

《算法导论-第三版》找继承结点的代码实现

寻找左子树中的继承结点:

寻找右子树中的继承结点:

下面分析一下红黑树删除结点的场景(相比于二叉树,增加红黑树的属性,需要考虑颜色的平衡性):

2.1、删除结点无子结点(只有叶结点-Nil结点)

如果结点是红色,直接删除即可,将删除结点的一个叶结点(Nil结点)继承删除结点,此叶结点实际颜色应为黑-红色(红色继承自删除结点),此时直接去掉红色,仍然满足红黑树;

如果结点是黑色,将删除结点的一个叶结点(Nil结点)继承删除结点,此叶结点实际颜色应为黑-黑色,需要进行平衡操作

2.2、删除结点有一个子结点

此时删除结点只能是黑色,并且删除结点的子结点(唯一继承结点)只能是红色,此时继承结点为红-黑色,需进行平衡操作

2.3、删除结点有两个子结点

2.3.1、先找到继承结点;

2.3.2、继承结点继承删除结点;

2.3.3、类似于删除继承结点操作,即找继承结点的继承结点(注:此操作只会进行一层,因为继承结点只能包含一个子或者两个叶子,所以2.3退化成2.1、2.2的情况)

《算法导论-第三版》删除结点的代码实现

继承操作

下面分析一下平衡删除的场景

3.1、平衡结点是树的根结点

根据性质2,直接着为黑色,满足红黑树性质;

3.2、平衡结点是红色(红-黑),2.2情况之后

直接将其着为黑色,满足红黑树性质;

3.3、平衡结点为黑色(黑-黑的叶节点-Nil结点),平衡结点为其父结点的左子,2.1情况之后

3.3.1、平衡结点为黑-黑,兄弟结点为红色

3.3.2、平衡结点为黑-黑,兄弟结点为黑色,包含两个叶结点

3.3.3、平衡结点为黑-黑,兄弟结点为黑色,包含一个左子为红色,右子为叶结点

3.3.4、平衡结点为黑-黑,兄弟结点为黑色,包含一个右子为红色,左子为叶结点或为叶结点

3.4、平衡结点为黑色(黑-黑的叶节点-Nil结点),平衡结点为其父结点的右子,2.1情况之后(与3.3互为对称的操作)

情况3.3.1 和 3.3.4

情况3.3.2和3.3.3

《算法导论-第三版》找删除平衡的代码实现

HashMap的红黑树删除平衡算法


  • 《算法导论》第三版
  • 教你透彻了解红黑树
  • https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md
  • 红黑树实现-git地址
  • https://gitee.com/MoyouHu/java-core/tree/master/src/main/java/org/zoro/java/tree
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-12-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 BanzClub 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 性质
  • 旋转
  • 插入
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档