真正理解红黑树，真正的(Linux内核里大量用到的数据结构，且常被二货问到)

作为一种数据结构，红黑树可谓不算朴素，因为各种宣传让它过于神秘，网上搜罗了一大堆的关于红黑树的文章，不外乎千篇一律，介绍概念，分析性能，贴上代码，然后给上罪恶的一句话，它最坏情况怎么怎么地...

1.查找-在高度不在宽度

对于查找而言，如果一棵二叉树的高度是N，那么最多可以在N步内完成查找，这个不用解释，解释这个有点喧宾夺主了。这就是说，树的高度要尽可能矮。考虑到查找的平均情况，叶子节点到根节点的距离不能差别太大。

2.二叉树的不平衡根源

一棵树在查找看来变得不平衡是因为子树的高度相差很大。

3.多叉树-宽度换高度

在第1节以及第2节，我们已经知道，树的宽度越大，高度越小，这样查询起来越快，Cisco路由器里不是有256叉乃至1024叉树吗？但是这样真的很好吗？对于稀疏节点，这样会严重消耗内存。

4.权衡-2，3树

我们发现，道生一，一生二，二叉树是一个完美的开始，但是我们发现它特别容易倾斜，倾斜的时候别触摸。我们也不能一下子就上256叉树，即使那样在海量节点情况下也抗不住，因此这种盲目宽度换高度的方案没有可扩展性。我们需要找出一种动态的机制，让一棵树动态调整保持平衡。

5.2-3树的平衡变换

如果是二叉树，那么你插入一个节点，你只有最多1次机会保持子树的高度不变，如果是一个三叉树，那么就有2次机会。现在开始，我们为二叉树添了一叉，变成了三叉树。

1).插入的新叶子节点的父节点是一个二叉节点

这种情况最简单，二叉节点变三叉节点即可，如下图所示：

2).插入的新叶子节点的父节点是一个三叉节点

这种情况比较复杂。树总是要长高的，保持平衡的方式就是同时长高，而这是不可能的，插入一个节点只能让该节点所在的子树长高。然而，如果能将这个信息上升到根部，在根部长高，就实现了“同时长高”！

很遗憾，没有完成任务，但是最终我们提出了两个问题，只要解决了这两个问题，所有问题就解决了。

解决这两个问题，无疑都要牵扯到节点P的父节点以及再往上的节点，有两种可能：
可能性1：P的父节点PP是一个二叉节点

问题2解决。

可能性2：P的父节点PP是一个三叉节点

最后，我们发现，在递归的过程中，要么碰到了P..P是个二叉节点，此时按照问题2的解决方式将当前节点的值直接提到P...P中，其子树降低一个高度，抵消增加的高度，平衡保持，递归结束，要么递归到了根节点，此时只需要一个分裂操作即可完美结束！

6.演进到红黑树

很显然，通过上面的描述，我们似乎找到了一个使树保持平衡的方案，而且是相当完美的平衡！核心就是宽度和高度之间的博弈。我们总是可以用一个宽度抵消一层高度，整个过程就是一次或者多次的一加一减，最终的结果还是0！

看到了吧，红色节点就是从2-3树中分出来的，为了维持一棵二叉树而不是2-3树，必须将三叉节点变成二叉节点，这是一个宽度换高度得回退，即高度换宽度，当然代价就是不再完美平衡。

按照以上的这个变换，你自己试试看，可以变出两个连续的红节点吗？NO！还在纠结红黑树的性质概念吗？看了它的演进，你会发现，很多红黑树的复杂概念和让人没有头绪的性能都是自然而然的。下面我们来看一下它的最坏情况是什么。