共计 2376 个字符，预计需要花费 6 分钟才能阅读完成。
在亿级数据中只需要进行几十次的比较就能查找到目标，这就是红黑树的魅力。
在学习红黑树之前，要先理解一下二叉查找树（Binary Search Tree）。
二叉树
二叉查找树的特性：
- 左子树上所有节点的值均 <= 它的父节点的值
- 右子树上所有节点的值均 >= 它的父节点的值
- 左右子树也分别称为二叉排序树
二叉树的查找
我们从上面这颗二叉树中来查找值为12的节点。
- 首先，查看根节点值为9，小于12，所以查看右孩子值为13的节点
- 其次，因为12<13，所以查找它的左孩子值为11的节点
- 接着，12>11，所以查看它的右孩子，发现正是要查找的值为12的节点
这种正是二叉树的查找的思想，最大查找次数为二叉树的高度。
二叉树的插入
插入也是类似查找的方法，一层一层的比较，找到合适的位置进行插入
二叉树的缺点
假设初始的二叉树如下
接下来依次插入7，6，5，4，3，依照二叉树的特性，就会变成如下图
这样的话，在查找很多节点就变成线性的了，性能就大打折扣了。
红黑树
如何解决二叉树多次插入新节点导致的不平衡呢？红黑树就应运而生了。
红黑树特性
红黑树是一种自平衡的二叉树，除了有二叉树的特性外，还有一些特有的属性
- 节点是黑色或者红色
- 根节点是黑色
- 每个叶子节点（NIL）都是黑色
- 每个红色节点的两个叶子一定是黑色
- 任意一节点到每个叶子节点的路径都包含相同数量的黑色节点
根据性质5可以推断出，如果一个节点存在黑子节点，那么该节点肯定有两个子节点
红黑树并不是一个完美平衡二叉查找树，从上图可以看到，根节点P的左子树显然比右子树高，但是左子树和右子树的黑节点的层树是相等的，也即任意一个节点到每个叶子节点的路径都包含数量相同的黑节点（性质5）。所以我们叫红黑树这种平衡为黑色完美平衡。
我们先约定一下红黑树个节点的叫法，选取当前节点为D节点，它的相关节点叫法如下图
红黑树如何实现自平衡？
红黑树实现自平衡靠的三个基本操作：左旋，右旋，变色
- 左旋：以某个节点作为旋转支点（P点），其右子节点（V点）变成旋转节点的父节点，右子节点的左子节点（R点）变成旋转节点的右子节点，左子节点（F点）保持不变。
- 右旋：以某个节点作为旋转支点（P点），其左子节点（F点）变成旋转节点的父节点，左子节点的右子节点（K点）变成旋转节点的左子节点，右子节点（V点）保持不变。
- 变色：节点的颜色由红变黑或由黑变红。
左旋只影响旋转接点和其右子节点的结构，右旋影响旋转接点和其左子节点的结构。但是旋转过后，红黑树的颜色就不平衡了，需要配合变色来达到新的平衡。
红黑树的查找
因为红黑树是一颗二叉平衡树，所以查找和二叉树的查找无异，上面已经介绍过了，就不再说明了。
由于红黑树总保持黑色完美平衡，所以她的查找最坏时间复杂度为O(2logN)，也即整颗树刚好红黑相隔的时候。
红黑树插入
插入操作分为两步：
- 查找插入的位置（这个和查找的操作一致）
- 插入后自平衡
红黑树有红黑二色，那么插入的节点是什么颜色呢？
红色。理由很简单，红色在父节点存在未黑色节点时，红黑树的黑色平衡没有被破坏，不需要做自平衡操作。但是如果插入节点时黑色，那么插入位置所在的子树黑色节点总是多1，必须做自平衡。
这里做了做了所有插入情景的总结（看不清请点击放大看）
插入情景1，2，3
情景1，2，3比较简单，看图不再做说明。
插入情景4：插入节点的父节点为红色
插入节点的父节点为红色，那么父节点不可能为根节点，因为根节点是黑色的。下面的各种情景都是在这个前提下展开的
插入情景4.1：叔叔节点存在并且为红色
如下两图，插入I，因为不能同时存在两个相连的红节点，所以需要自平衡，最简单的方式就是将黑红红变色为红黑红。
变色后，PP节点变成红色，如果父节点是黑色，那么不需再做其他处理；如果父节点是红色，还需将PP当做新的插入节点，继续做自平衡处理，直到平衡位置。
这里有一种特殊情况，如果PP为根节点，那么必须把PP设置为黑色，那么结构变为黑黑红。从根节点到叶子节点的路径中，黑色节点增加了，这也是唯一一种会增加黑色节点层数的插入情景。
这里可以总结出另外一个特点，红黑树的生长是自底向上的。而普通的二叉树的生长是自顶向下的。
插入情景4.2：叔叔节点不存在或为黑节点，并且插入节点的父节点是祖父节点的左子节点
因为父节点为红色的前提下，叔叔节点非红，那么肯定就是叶子节点（NIL），因为如果为黑色节点，那么叔叔节点所在的子树的黑色节点就比父节点所在的子树多了，不满足性质5。
插入情景4.2.1：插入节点为其父节点的左子节点
- 将P啥位置为黑色
- 将PP设置为红色
- 对PP进行右旋
插入情景4.2.2：插入节点为其父节点的右子节点
插入情景4.3：叔叔节点不存在或为黑节点，并插入节点的父节点是祖父节点的右子节点
这个情景跟4.2类似，就是方向反过来而已。
插入情景4.3.1：插入节点是其父节点的右子节点
插入情景4.3.2：插入节点是其父节点的左子节点
红黑树删除
删除操作也是相当复杂，是红黑树里最复杂的操作了。跟插入类似，也分为两部分工作：1.查找删除节点；2.删除后自平衡
总结如下，就不再详细讲解了
练习题
1. 黑节点可以同时包含一个红子节点和一个黑子节点吗？
答案：可以，参考下图的F节点（满足性质5，从L到A或者L到G都是3个黑色节点）
2.请画出下图的插入自平衡过程
答案：DM变色 -> K变色 -> 对P进行右旋 -> P变色 -> U变色
参考文章：
https://www.jianshu.com/p/e136ec79235c
https://mp.weixin.qq.com/s/-8JFh5iLr88XA4AJ9mMf6g
