在亿级数据中只需要进行几十次的比较就能查找到目标,这就是红黑树的魅力。

在学习红黑树之前,要先理解一下二叉查找树(Binary Search Tree)。

二叉树

二叉查找树的特性:

  • 左子树上所有节点的值均 <= 它的父节点的值
  • 左子树上所有节点的值均 >= 它的父节点的值
  • 左右子树也分别称为二叉排序树
经典的二叉树

二叉树的查找

我们从上面这颗二叉树中来查找值为12的节点。

  1. 首先,查看根节点值为9,小于12,所以查看右孩子值为13的节点
  2. 其次,因为12<13,所以查找它的左孩子值为11的节点
  3. 接着,12>11,所以查看它的右孩子,发现正是要查找的值为12的节点

这种正是二叉树的查找的思想,最大查找次数为二叉树的高度。

二叉树的插入

插入也是类似查找的方法,一层一层的比较,找到合适的位置进行插入

二叉树的缺点

假设初始的二叉树如下

初始的二叉树

接下来依次插入7,6,5,4,3,依照二叉树的特性,就会变成如下图

插入后的二叉树

这样的话,在查找很多节点就变成线性的了,性能就大打折扣了。

红黑树

如何解决二叉树多次插入新节点导致的不平衡呢?红黑树就应运而生了。

红黑树特性

红黑树是一种自平衡的二叉树,除了有二叉树的特性外,还有一些特有的属性

  1. 节点是黑色或者红色
  2. 根节点是黑色
  3. 每个叶子节点(NIL)都是黑色
  4. 每个红色节点的两个叶子一定是黑色
  5. 任意一节点到每个叶子节点的路径都包含相同数量的黑色节点

根据性质5可以推断出,如果一个节点存在黑子节点,那么该节点肯定有两个子节点

一颗简单的红黑树

红黑树并不是一个完美平衡二叉查找树,从上图可以看到,根节点P的左子树显然比右子树高,但是左子树和右子树的黑节点的层树是相等的,也即任意一个节点到每个叶子节点的路径都包含数量相同的黑节点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡

我们先约定一下红黑树个节点的叫法,选取当前节点为D节点,它的相关节点叫法如下图

红黑树节点的叫法

红黑树如何实现自平衡?

红黑树实现自平衡靠的三个基本操作:左旋,右旋,变色

  • 左旋:以某个节点作为旋转支点(P点),其右子节点(V点)变成旋转节点的父节点,右子节点的左子节点(R点)变成旋转节点的右子节点,左子节点(F点)保持不变。
左旋示意图
  • 右旋:以某个节点作为旋转支点(P点),其左子节点(F点)变成旋转节点的父节点,左子节点的右子节点(K点)变成旋转节点的左子节点,右子节点(V点)保持不变。
右旋示意图
  • 变色:节点的颜色由红变黑或由黑变红。

左旋只影响旋转接点和其右子节点的结构,右旋影响旋转接点和其左子节点的结构。但是旋转过后,红黑树的颜色就不平衡了,需要配合变色来达到新的平衡。

红黑树的查找

因为红黑树是一颗二叉平衡树,所以查找和二叉树的查找无异,上面已经介绍过了,就不再说明了。

由于红黑树总保持黑色完美平衡,所以她的查找最坏时间复杂度为O(2logN),也即整颗树刚好红黑相隔的时候。

红黑树插入

插入操作分为两步:

  1. 查找插入的位置(这个和查找的操作一致)
  2. 插入后自平衡

红黑树有红黑二色,那么插入的节点是什么颜色呢?

红色。理由很简单,红色在父节点存在未黑色节点时,红黑树的黑色平衡没有被破坏,不需要做自平衡操作。但是如果插入节点时黑色,那么插入位置所在的子树黑色节点总是多1,必须做自平衡。

这里做了做了所有插入情景的总结(看不清请点击放大看)

红黑树插入情景总结

插入情景1,2,3

情景1,2,3比较简单,看图不再做说明。

插入情景4:插入节点的父节点为红色

插入节点的父节点为红色,那么父节点不可能为根节点,因为根节点是黑色的。下面的各种情景都是在这个前提下展开的

插入情景4.1:叔叔节点存在并且为红色

如下两图,插入I,因为不能同时存在两个相连的红节点,所以需要自平衡,最简单的方式就是将黑红红变色为红黑红。

插入情景4.1-1
插入情景4.1-2

变色后,PP节点变成红色,如果父节点是黑色,那么不需再做其他处理;如果父节点是红色,还需将PP当做新的插入节点,继续做自平衡处理,直到平衡位置。

这里有一种特殊情况,如果PP为根节点,那么必须把PP设置为黑色,那么结构变为黑黑红。从根节点到叶子节点的路径中,黑色节点增加了,这也是唯一一种会增加黑色节点层数的插入情景。

这里可以总结出另外一个特点,红黑树的生长是自底向上的。而普通的二叉树的生长是自顶向下的。

插入情景4.2:叔叔节点不存在或为黑节点,并且插入节点的父节点是祖父节点的左子节点

因为父节点为红色的前提下,叔叔节点非红,那么肯定就是叶子节点(NIL),因为如果为黑色节点,那么叔叔节点所在的子树的黑色节点就比父节点所在的子树多了,不满足性质5。

插入情景4.2.1:插入节点为其父节点的左子节点
  1. 将P啥位置为黑色
  2. 将PP设置为红色
  3. 对PP进行右旋
插入情景4.2.1
插入情景4.2.2:插入节点为其父节点的右子节点
插入情景4.2.2

插入情景4.3:叔叔节点不存在或为黑节点,并插入节点的父节点是祖父节点的右子节点

这个情景跟4.2类似,就是方向反过来而已。

插入情景4.3.1:插入节点是其父节点的右子节点
插入情景4.3.1
插入情景4.3.2:插入节点是其父节点的左子节点
插入情景4.3.2

红黑树删除

删除操作也是相当复杂,是红黑树里最复杂的操作了。跟插入类似,也分为两部分工作:1.查找删除节点;2.删除后自平衡

总结如下,就不再详细讲解了

红黑树删除总结

练习题

1. 黑节点可以同时包含一个红子节点和一个黑子节点吗?

答案:可以,参考下图的F节点(满足性质5,从L到A或者L到G都是3个黑色节点)

习题1

2.请画出下图的插入自平衡过程

习题2

答案:DM变色 -> K变色 -> 对P进行右旋 -> P变色 -> U变色

参考文章:

https://www.jianshu.com/p/e136ec79235c
https://mp.weixin.qq.com/s/-8JFh5iLr88XA4AJ9mMf6g