当在 10 亿数据中只需要进行十几次比较就能查找到目标时，不禁感叹编程之魅力!人类之伟大呀!
—学红黑树有感
终于，在学习了几天的红黑树相关的知识后，我想把我所学所想和所感分享给大家。
红黑树是一种比较难的数据结构，要完全搞懂非常耗时耗力，红黑树怎么自平衡?什么时候需要左旋或右旋?插入和删除破坏了树的平衡后怎么处理?等等一连串的问题在学习前困扰着我。
如果你在学习过程中也会存在我的疑问，那么本文对你会有帮助，本文帮助你全面、彻底地理解红黑树!
本文将通过图文的方式讲解红黑树的知识点，并且不会涉及到任何代码，相信我，在懂得红黑树实现原理前，看代码会一头雾水的，当原理懂了，代码也就按部就班写而已，没任何难度。
阅读本文你需具备知识点：
二叉查找树
完美平衡二叉树
红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。
现在在脑海想下怎么实现?是不是太多情景需要考虑了?啧啧，先别急，通过本文的学习后，你会觉得，其实也不过如此而已。好吧，我们先来看下红黑树的定义和一些基本性质。
红黑树定义和性质
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
每个节点要么是黑色，要么是红色。
根节点是黑色。
每个叶子节点(Nil)是黑色。
每个红色结点的两个子结点一定都是黑色。
任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
从性质 5 又可以推出：如果一个结点存在黑子结点，那么该结点肯定有两个子结点。
图 1：一棵简单的红黑树
上图就是一颗简单的红黑树。其中 Nil 为叶子结点，并且它是黑色的。(值得提醒注意的是，在 Java 中，叶子结点是为 null 的结点。)
红黑树并不是一个完美平衡二叉查找树，从图 1 可以看到，根结点 P 的左子树显然比右子树高。
但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质 5)。所以我们叫红黑树这种平衡为黑色完美平衡。
介绍到此，为了后面讲解不至于混淆，我们还需要来约定下红黑树一些结点的叫法，如图 2 所示：
图 2：结点叫法约定
我们把正在处理(遍历)的结点叫做当前结点，如图 2 中的 D，它的父亲叫做父结点，它的父亲的另外一个子结点叫做兄弟结点，父亲的父亲叫做祖父结点。
前面讲到红黑树能自平衡，它靠的是什么?有如下三种操作：
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图 3。
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图 4。
变色：结点的颜色由红变黑或由黑变红。
图 3：左旋
图 4：右旋
上面所说的旋转结点也即旋转的支点，图 4 和图 5 中的 P 结点。我们先忽略颜色，可以看到旋转操作不会影响旋转结点的父结点，父结点以上的结构还是保持不变的。
左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了;右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
所以旋转操作是局部的。另外可以看出旋转能保持红黑树平衡的一些端详了：当一边子树的结点少了，那么向另外一边子树“借”一些结点;当一边子树的结点多了，那么向另外一边子树“租”一些结点。