彻底搞懂红黑树

红黑树性质

1、每个结点或是红色的,或是黑色的 2、根节点是黑色的 3、每个叶结点(NIL)是黑色的 4、如果一个节点是红色的,则它的两个儿子都是黑色的。 5、对于每个结点,从该结点到其叶子结点构成的所有路径上的黑结点个数相同。

和AVL树的比较

AVL树是一棵严格的平衡树,它所有的子树都满足二叉平衡树的定义。因此AVL树高被严格控制在XXX,因此AVL树的查找比较高效。但AVL树插入、删除结点后旋转的次数比红黑树多。

红黑树用非严格的平衡来降低插入删除时旋转的次数。

因此,如果你的业务中查找远远多于插入、删除,那选AVL树; 如果查找、插入、删除频率差不多,那么选择红黑树。

插入过程

默认插入的结点为红色。为何? 因为红黑树中黑节点至少是红节点的两倍,因此插入节点的父节点为黑色的概率较大,而此时并不需要作任何调整,因此效率较高。

1. 父为黑

插入后无需任何操作。由于黑节点个数至少为红节点的两倍,因此父为黑的情况较多,而这种情况在插入后无需任何调整,这就是红黑树比AVL树插入效率高的原因!

2. 父为红

父为红的情况破坏了红黑树的性质,此时需要根据叔叔的颜色来做不同的处理。

  1. 叔叔为红

此时很简单,只需交换爸爸、叔叔和爷爷的颜色即可。 此时若爷爷节点和太爷爷节点颜色相同,再以爷爷节点为起始节点,进行刚才相同的操作,即:根据爷爷的兄弟颜色做相应的操作。

  1. 叔叔为黑 此时较为复杂,分如下四种情况: a)爸爸在左、叔叔在右、我在左

以爸爸为根节点,进行一次R旋转。 b)爸爸在左、叔叔在右、我在右

先以我为根节点,进行一次L旋转; 再以我为根节点,进行一次R旋转。 c)叔叔在左、爸爸在右、我在左

先以我为根节点,进行一次R旋转; 再以我为根节点,进行一次L旋转。 d)叔叔在左、爸爸在右、我在右

以爸爸为根节点,进行一次L旋转。


删除过程

二叉搜索树的删除

若删除二叉搜索树的节点A,实际上删除的是二叉搜索树中序遍历的前驱节点,注意: 1. 这个被删除节点要么就是一个叶子节点, 2. 要么有且仅有一个左孩子 然后将孩子顶替它原来的位置,最后将被删的节点值覆盖待删除的那个节点A。

红黑树按照二叉搜索树的方式删除节点,之后再进行相应的旋转操作,使得删除后的树仍然是一棵红黑树。

定义

  1. 待删除节点:要删除的那个节点
  2. 实际删除节点:待删除节点的中序遍历前驱

红黑树实际删除节点的性质

  1. 实际删除节点要么是叶子节点,要么有且仅有一个左孩子;
  2. 若为叶子节点,必为红色;
  3. 若实际删除节点还有孩子,则该必为左孩子; a)若左孩子为红色,则实际删除节点必为黑色; b)若左孩子为黑色,则实际删除节点红黑均可以。

约定

  1. 蓝色箭头:表示判定点
  2. 在删除操作开始前,蓝色箭头首先指向实际删除节点。
  3. 『实际删除节点』在图中以『父』表示。

旋转过程开始:

1. 父为红色(待删节点为叶子)

直接删除父节点即可:

2. 父为黑 子为红(待删节点为黑、待删节点子节点为红+左孩子)

用子节点覆盖父节点,并保持父节点的颜色:

3. 父为黑 子为黑(待删节点和子节点均为黑)

3.1. 叔叔为红

PS:叔叔为红,则爷爷必为黑!

  1. 父在左 叔在右 a)子节点覆盖父节点 b)进行一次左旋
  1. 父在右 叔在左 a)子节点覆盖父节点 b)进行一次右旋

3.2. 叔叔为黑

PS:叔叔、爸爸都为黑,那爷爷颜色就不确定了!

  1. 祖父红 两个侄子黑 以下两种情况操作一致: 1.子覆盖父(删除) 2.交换祖父和叔叔的颜色。 a)父在左 叔在右

b)父在右 叔在左 同上。

  1. 祖父黑 两个侄子黑 以下两种情况操作一致: 1. 祖父染成子节点的颜色; 2. 子节点染成黑色; 3. 叔叔染成红色 a)父在左 叔在右

b)父在右 叔在左

  1. 祖父颜色随意 至少有一个红侄 a)红侄为左左(叔左、红侄左) 1. 红侄进行一次右旋 2. 红侄染成黑色 3. 交换叔叔和祖父的颜色

b)红侄为左右(叔左、红侄右) 1. 红侄进行一次右旋+左旋 2. 红侄染成父节点颜色; 3. 父节点染成黑色

c)红侄为右左(叔右、红侄左) 1. 红侄进行一次右旋+左旋 2. 红侄染成父节点颜色; 3. 父节点染成黑色;

d)红侄为右右(叔右、红侄右) 1. 红侄进行一次左旋 2. 叔叔染成父节点颜色; 3. 红侄染成黑色;

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

When Math meets Android Animation (3)

当数学遇上动画:讲述ValueAnimator、TypeEvaluator和TimeInterpolator之间的恩恩怨怨(3)

822
来自专栏Golang语言社区

完全二叉树判断,简单而复杂

今天有个人问我如何判断一棵树是完全二叉树。我一下子想不出怎么解决这个问题,按照定义, 严蔚敏那本教材上的说法:一个深度为k,节点个数为 2^k - 1 的二叉树...

2953
来自专栏hightopo

HTML5实现3D和2D可视化QuadTree四叉树碰撞检测

1206
来自专栏鸿的学习笔记

写给开发者的机器学习指南(十二)

此代码加载DJI数据,并将其添加到已经包含我们自己的股票市场指数的图形上。但是,当我们执行这段代码时,结果如下。

892
来自专栏HT

HTML5实现3D和2D可视化QuadTree四叉树碰撞检测

QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域...

2129
来自专栏钟绍威的专栏

jdk源码分析红黑树——插入篇1.插入root2.父黑3.父红4.父红,叔红5.1父红,叔黑,外侧子孙5.2父红,叔黑,内侧子孙

红黑树是自平衡的排序树,自平衡的优点是减少遍历的节点,所以效率会高。如果是非平衡的二叉树,当顺序或逆序插入的时候,查找动作很可能会遍历n个节点 红黑树的规则很容...

1816
来自专栏desperate633

LeetCode 337. House Robber III分析通过上面的问题的一步步分析,我们更好的理解了动态规划的意义,并且将算法优化到最佳

Paste_Image.png Maximum amount of money the thief can rob = 3 + 3 + 1 =...

562
来自专栏开发 & 算法杂谈

凸包问题之GrahamScan解法

当沿着Convex hull逆时针漫游时,总是向左转在极坐标系下按照极角大小排列,然后逆时针方向漫游点集,去除非Convex hull顶点(非左 转点)。

734
来自专栏HT

HT for Web可视化QuadTree四叉树碰撞检测

QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域...

2489
来自专栏拭心的安卓进阶之路

重温数据结构:深入理解红黑树

读完本文你将了解到: 什么是红黑树 黑色高度 红黑树的 5 个特性 红黑树的左旋右旋 指定节点 x 的左旋 右图转成左图 指定节点 y 的右旋左图转成右图 红...

2799

扫码关注云+社区