看了这么多篇红黑树文章，你理解了嘛？( 二 ) _红黑树

（1）每个节点只有两种颜色：红色和黑色。
（2）根节点是黑色的。
（3）每个叶子节点（NIL）都是黑色的空节点。
（4）从根节点到叶子节点，不会出现两个连续的红色节点。
（5）从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。
这五条就是红黑树的特征，你每看一个特征最好重新看一遍图，这样可以加深理解。这五条特征看起来真的很复杂，不过正是由于这些复杂的特征才保证了红黑树的良好特性。如何保证的呢？我们从增删改查四个角度来一个一个分析一下：
1、查询节点
查询节点是最简单的一个，他的查找过程和二叉查找树一样，查找元素比当前节点大，就从右子树继续查找比较，查找元素比当前节点小，就从左子树继续查找比较。查找过程就不再赘述了。
2、插入节点
插入节点是最麻烦的一个，它分为三种情况。我们一种一种看，这样比较有条理性。
第一种情况：新节点没有父节点
没有父节点只有一种情况，就是插入的节点是整棵树第一个节点，也就是根节点，为此我们只需要把插入节点涂成黑色就OK了。这也就保证了性质2：根节点是黑色的。
第二种情况：新节点的父节点是黑色
为此我们举一个例子，比如说上面的红黑树中，我们插入节点14 。来看一下会发生什么情况？

文章插图

这种情况我们发现新插入节点14的父节点就是黑色的。现在为了保证红黑树的性质，我们对照每个特性来检查一遍。只要有一条不满足，我们都需要调整。我们重新对照之后会发现每一条都符合。此时不需要调整。
第三种情况：新节点的父亲节点为红色
我们还是举个例子，比如我们在最开始的红黑树基础之上插入节点21，此时会发生什么情况呢？

文章插图

此时还是老规矩，对照着红黑树的5个特征一个一个来看，只要是违反了一条就需要做出调整。我们来看一下：
（1）每个节点只有两种颜色：红色和黑色。这一条满足。
（2）根节点是黑色的。这一条也满足。
（3）每个叶子节点（NIL）都是黑色的空节点。这一条满足。
（4）从根节点到叶子节点，不会出现两个连续的红色节点。这一条发现不满足。
就是上面这一条规则没有满足，所以我们此时需要调整？问题来了如何调整呢？因为直接看父节点没办法实现，所以还需要观察另外的节点，也就是新节点的叔叔节点。根据叔叔节点的颜色来调整。调整的方式有两种：变色和旋转。
（1）叔叔节点是红色：
此时插入的节点是21，但是叔叔节点是27，更好是红色。我们直接来看调整的步骤：
第一步：把新节点21的父节点22变成黑色。

文章插图

此时重新看一下是否满足红黑树的五条特征了没，一条一条发现，第五条没有满足，也就是从任何一个节点出发，到叶子节点，这条路径上没有相同数目的黑色节点。比如从25出发。这时候怎么办呢？那就继续调整。
第二步：把22的父节点25变成红色

文章插图

这时候还是老规矩，不要嫌弃麻烦，因为只有经历了一步又一步的麻烦之后，你才能牢记那5条规则特征。我们对照之后会发现节点25和节点27是两个连续的红色节点，这时候又破坏了规则4 。怎么办呢？那就继续调整就OK了。
难道这时候还要继续往上调整吗？如果你这样做就错了，因为不断地往上调整最后就会把根节点变成了红色，会走进死胡同。我们往下走。
第三步：把节点27变成黑色