红黑树---简单易懂
这样说呢，可能大家也猜到了是【二分查找法】，通过这个例子呢，主要想引出的是树，看下面的图片：
程序中的树呢，其实是我们日常看到的树的倒影，或者发挥一下想象，倒影也可以是树根
二叉查找树，Binary Search Tree 「BST」，要想了解二叉查找树呢，首先我们需要了解一下二叉查找树知耐斗都有哪些特性呢？
看个图就轻松理解上面三句话的意思了:
上图，结合二叉查找树的三条约束来看，非常好，没有什么问题。再来看一个图，依旧符合上面三条约束，感觉有问题吗？
这是一个走路一米六，一米八的树
这是一个畸形的树，大风一挂很可能被折断的树
从程序的角度来说这个树不够平衡，查找次数或时间复杂度 O(h)可能会随着一条腿长无限增长
理科生在高中学习生物时学过一个关键字「去除顶端优势」，通过去除植物顶端优势，侧芽会迅速生长，慢慢变得强壮和平衡， 红黑树其实就是去除二叉查找树顶端优势的解决方案，从而达到树的平衡
红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:
可能大家还是很懵逼，不过没事，多练习几次就熟悉亩宏了。
红黑树有两大操作：
我们会先尝试recolor，如果recolor不能达到红黑树的四个要求，然后我们尝试rotation，其实红黑树的关键玩法就是弄清楚recolor和rotation的规则，接下来我们看一下详细的算法公式吧。
假设我们插入的新节点为X
接下来看下图：
跟着上面的公式走：
上面说的是X的uncle为红色的情况，接下来我们看一下X的uncle为黑色的情况
当uncle节点为黑色的时候，我们第一步考虑的是旋转，这里呢我们可以先不关注红黑树的4个规则，主要是演示如何旋转的。
这种情况很简单，想象这是一根绳子，手提起P节点，然后变色即可，如下图：
变色：X是当前节点，P是X的parent节点，U是X的uncle节点，G是grand parent节点。P节点是根节点变黑色，G变成和X一样的颜色，也就是红色。完成
先进行左旋：使X的父节点P被X取代，同时父节点P成为X的左孩子，然后在应用 左左情况 ，如下图：
像左左一样，看成一根绳子。手提起P节点，然后变色即可，如下搭磨图：
先右旋：使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的右孩子，然后再应用 右右情况 ，如下图：
通过上述过程，想必大家对红黑树有了一定的了解。以后在提到红黑树的时候，就不会那么头大了。本文参照 日拱一兵 公众号中的文章"红黑树，超强动静图详解，简单易懂".
参考文章
