本文将通过图文的方式讲解红黑树的知识点，并且不会涉及到任何代码，相信我，在懂得红黑树实现原理前，看代码会一头雾水的，当原理懂了，代码也就按部就班写而已，没任何难度 。
阅读本文你需具备知识点：
二叉查找树
完美平衡二叉树
事不宜迟，让我们进入正题吧 。
红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态 。现在在脑海想下怎么实现？是不是太多情景需要考虑了？啧啧，先别急，通过本文的学习后，你会觉得，其实也不过如此而已 。好吧，我们先来看下红黑树的定义和一些基本性质 。
一、红黑树定义和性质
红黑树是一种含有红黑结点并能自平衡的二叉查找树 。它必须满足下面性质：
- 性质1：每个节点要么是黑色，要么是红色 。
- 性质2：根节点是黑色 。
- 性质3：每个叶子节点（NIL）是黑色 。
- 性质4：每个红色结点的两个子结点一定都是黑色 。
- 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点 。
- 性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点
文章插图
图1 一颗简单的红黑树
红黑树并不是一个完美平衡二叉查找树，从图1可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5) 。所以我们叫红黑树这种平衡为黑色完美平衡 。
介绍到此，为了后面讲解不至于混淆，我们还需要来约定下红黑树一些结点的叫法，如图2所示 。
文章插图
图2 结点叫法约定
我们把正在处理(遍历)的结点叫做当前结点，如图2中的D，它的父亲叫做父结点，它的父亲的另外一个子结点叫做兄弟结点，父亲的父亲叫做祖父结点 。
前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色 。
- 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变 。如图3 。
- 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变 。如图4 。
- 变色：结点的颜色由红变黑或由黑变红 。
文章插图
图3 左旋
文章插图
图4 右旋
上面所说的旋转结点也即旋转的支点，图4和图5中的P结点 。
我们先忽略颜色，可以看到旋转操作不会影响旋转结点的父结点，父结点以上的结构还是保持不变的 。
左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了 。
右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了 。
所以旋转操作是局部的 。另外可以看出旋转能保持红黑树平衡的一些端详了：当一边子树的结点少了，那么向另外一边子树“借”一些结点；当一边子树的结点多了，那么向另外一边子树“租”一些结点 。
但要保持红黑树的性质，结点不能乱挪，还得靠变色了 。怎么变？具体情景又不同变法，后面会具体讲到，现在只需要记住红黑树总是通过旋转和变色达到自平衡 。
balabala了这么多，相信你对红黑树有一定印象了，那么现在来考考你：
思考题1：黑结点可以同时包含一个红子结点和一个黑子结点吗？ (答案见文末)
接下来先讲解红黑树的查找热热身 。
二、红黑树查找
因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：
