对于红黑树，任何不平衡都会在三次旋转内解决？
可能很多同学看面经，会看到关于红黑树的这样一条性质：对于红黑树，任何不平衡都会在三次旋转内解决。但是，看过这一章所介绍的红黑树，肯定很多同学发现了，我们这个课程所实现的红黑树是没有这个性质的。但是，更优化的红黑树实现可以有这个性质！

任务

在这里，关键在于，这个课程中所介绍的红黑树（包括《算法4》所介绍的红黑树），是一种特殊的红黑树——左倾红黑树。但是红黑树本身并不需要“左倾”性质。也就是说，我们在这一章实现的左倾红黑树一定是红黑树；但是红黑树不一定全是左倾红黑树。换句话说，我们的代码为了维护“左倾”这个性质，做了额外的事情，消耗了性能，使得我们在这个课程中的实现，没有“任何不平衡都可以在三次旋转内解决”这么好的性能优势。

在这个课程中，我们也提及了红黑树的五个性质。只要满足着五个性质，就是红黑树！这五个性质是红黑树的标准定义。

这五个性质再罗列一下，是：

所有节点非红即黑；

根节点为黑；

最后的NULL节点为黑；

红节点的孩子一定为黑；

黑平衡
仔细观察这五个性质，大家就会发现，红黑树的标准定义中没有规定红节点一定左倾：）

换句话说，以下的两种形状，是满足红黑树的性质的！（其中B代表黑节点；R代表红节点）：

   B            
 /   \          
B     R

   B
 /   \
R     R
但是，由于在我们这个课程的实现中，以上两种情况并不满足“左倾”的性质，我们就需要额外的操作，将这两种情况转换成“左倾”的样子。这也就是我在课程中说的，红黑树有更优的实现。当我们放宽限制，让红黑树也可以包含上面两种样子的时候，我们需要的旋转调整将减少，并且有对于任何不平衡，三次旋转即可解决！

印象里，更多资源联系qq2503961206《算法导论》中红黑树的实现，是满足这个性质的。有兴趣的同学，不妨找来《算法导论》，好好研究一下：）

那么如果以上的两个样子也符合红黑树的定义，意味着什么呢？

我们可以仔细观察一下其中的第二种样子：

   B
 /   \
R     R
根据我们课程中介绍的红黑树和2-3树的关系，这其实意味着红黑树不仅仅是和2-3树等价的，还和2-4树等价（包含2-node，3-node，4-node）。但是，对于其中的4-node，我们只能用以上的样子表示，而不能使用以下两种形状：

    B    B   
   /      \
  R        R
 /          \
R            R
这是因为以上两种形状，他们破坏了红黑树的性质4！

在这里，请大家再回顾一下红黑树的五个性质！

所有节点非红即黑；

根节点为黑；

最后的NULL节点为黑；更多资源联系qq2503961206

红节点的孩子一定为黑；

黑平衡
有时候，其中前三个性质，都是非常记忆的很朴素的定义。对于性质3，我们又称又称为“红色性质”，因为它是和红色节点相关的；相应的，性质5，我们有时候又称为“黑色性质”，因为它是和黑色节点相关的。

怎么样，现在是不是觉得红黑树的5个性质很好记？：）

同时，通过这个角度，用2-4树去理解《算法导论》中红黑树的实现，或许更容易。（但是不知道为什么，印象里《算法导论》中完全没有提及红黑树和2-3树，2-4树的关系！这就是《算法导论》这部著作，让大家又爱又恨的原因吧！）

大家加油！：）