本篇红黑树文章，近120多幅图构成，让你了解红黑树不再难。
发表是最好的记忆 --候捷
目录：
红黑树介绍
旋转分析
插入分析
删除分析
完整实例宏微观图解过程
5.1 插入宏微观图解过程
5.2 删除宏微观图解过程
代码实现分析
分析过程附件
先看下《算法导论》对RBTree的介绍：
红黑树，一种二叉查找树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有1条路径会比其它路径长出2倍，因而是接近平衡的。
下面，在具体介绍红黑树之前，我们先来简单了解下，二叉查找树的一般性质：
（1）在一棵二叉查找树上，执行查找、插入、删除等操作的时间复杂度为O(logN); 因为，一棵由n个节点，随机构造的二叉查找树的高度为logN, 所以顺理成章，一般操作的执行时间O(logN);
至于n个节点的二叉树高度为logN的证明，可参考《算法导论》
（2）但若是一棵具有n个节点的线性链，则这些操作最坏情况运行时间为O(n);
而红黑树，能保证在最坏情况下，基本的动态操作的时间均O(logN);
我们知道，红黑树上每个节点内含有5个域，color, key, left, right, p。 如果相应的指针域没有，则设为NIL。
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
-
每个节点要么是红，要么是黑色；
-
根节点是黑色；
-
每个叶节点，即空节点（NIL）是黑色；
-
如果一个节点是红色，那么它的2个孩子节点必为黑色；
-
对于每个节点，从该节点到其子孙的叶子节点的路径上包含相同数目的黑色节点；
下图所示，即是一颗红黑树：
左旋与右旋
为什么要左旋右旋？
因为红黑树插入或删除节点后，树的结构发生了 变化，从而可能破坏红黑树的性质。为了维持插入或删除节点后的树，仍然是一棵红黑树，所以有必要对树的结构做部分调整，从而恢复红黑树的原本性质。而为了恢复红黑树性质而作的动作包括节点颜色的改变（重新着色），和节点的调整。
这部分节点调整工作，改变指针结构，即是通过左旋或右旋而达到目的。
从而使插入或删除节点的树重新成为一棵新的红黑树。
请看下图：
左旋代码实现，分三步：
右旋代码类似，可自行对比类比分析。