红黑树详解(二)红黑树的插入(附动图和案例)

---

摘要:

    在很多源码涉及到大量数据处理的时候，通常都是用红黑树这一数据结构。红黑树是一种自平衡的二叉查找树，它能在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，获得较高的查找性能。本文将使用图文详细的分析红黑树的插入

​ 回顾一下红黑树的五条性质

• 1.节点不是红色就是黑色
• 2.根节点是黑色
• 3.叶子节点(NIL)为黑色
• 4.每个红色节点的两个子节点都是黑色。（(从每个叶子到根的所有路径上不能有两个连续的红色节点）
• 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

​ 红黑树的插入分为两个步骤，找到插入的位置以及插入后的平衡。找到插入的位置与二叉查找树的查找类似，本文终点讲找到位置后进行插入的平衡。

​ 找到插入的位置后，对于要插入的结点，我们通常都设置它为红色。为什么这么做呢，因为如果插入结点我们设置为黑色，那么插入位置所在子树的黑色结点总是多1.必须要做自平衡，而如果插入结点为红色，就不会这样。因此我们插入结点都设置为红色。

​

​ 插入后可能会破坏红黑树的性质，就需要自平衡。在此之前设置一些结点的叫法，插入结点的结点为p，插入结点的祖父结点为pp，插入结点的父结点的兄弟结点为s。如图所示

​

​ 所有的插入情形如下

1.红黑树为空树

这种情况比较简单，根据性质2（根节点是黑色），把插入结点调为黑色，并设置为根结点就行了

2.插入结点的父结点为黑结点

这种情况是最简单的，因为黑色的父结点插入一个红色的子结点，并不会破坏红黑树的结构，因此直接插入，不需要操作。

3.插入结点的父结点为红结点

插入结点的父结点为红结点，必定会破坏红黑树的性质4（每个红色节点的两个子节点都是黑色），

3.1插入结点的叔叔结点为红色

根据性质4，祖父结点不能为红色，必定为黑色。我们可以将父亲结点p和叔叔结点s变黑色，祖父结点变红色就能解决问题。但是只是局部的平衡，祖父结点变红色还可能因为祖父结点的父结点为红色而破坏红黑树平衡，因此还需要将祖父结点pp作为插入结点继续向上的平衡。

• 把祖父结点pp变红色
• 把父结点p和叔叔结点变黑色
• 把pp作为新的插入结点

3.2插入结点的父结点p是祖父结点pp的左子结点，插入结点的叔叔结点s不存在或为黑色

这里可能会有疑问，既然父结点为红，为什么叔叔结点会为黑色，这样叔叔结点所在子树的黑色结点数目就多一了。其实还有可能类似于上述3.1请假向上平衡所产生的情况，因此插入结点的叔叔结点是有可能为黑色的。

由于左边子树结点比右边少，我们就需要右旋向右边去借.

3.2.1 插入结点是父结点p的左子结点

因为把pp右旋后是黑色破坏了黑色结点的数量，因此还需要将pp变红。p则需要变为原来pp的颜色，即黑色。

• 对pp右旋
• p变黑，pp变红

3.2.2插入结点是父结点p的右子结点

这种情况我们发现对插入结点的父结点p进行左旋，就变成情况3.2.1了，然后按照3.2.1进行处理

• 对p左旋
• 转到情况3.2.1处理

3.3插入结点的父结点p是祖父结点pp的右子结点，插入结点的叔叔结点s不存在或为黑色

这种情况就是3.2情况的对称情况，这里有一个小技巧,把3.2的情况的左右对换就是3.3情况了

3.3.1插入结点是父结点p的右子结点

这种情况和3.2.1类似，因为是对称的，只要把左变成右，右变成左就行了。

• 对pp左旋
• p变黑，pp变红

3.3.2插入结点是父结点p的左子结点

这种情况是和3.2.2类似，我们对p右旋，转为情况3.3.1

• 对p右旋
• 转到情况3.3.1处理

实战中尝试

往下图红黑树中插入0，红黑树的变化过程

找到插入位置，在92的左边。插入红色结点0

插入结点0的父结点92是红结点，且叔叔结点96为红，符合情况3.1,按照情况3.1处理(注意此时把94作为新的插入结点)， 处理后如下

插入结点94的父结点97为红色，且父结点为祖父结点100的左子结点，叔叔结点98为黑色。符合情况3.2.1，处理后如下

插入结点94的父结点97为黑色，不用操作，整个流程结束.

整个过程如下

---

下期带来红黑树最难的删除操作，对于右疑问或者右错误的地方欢迎留下评论一起讨论