什么是红黑树
引入
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在 O(log n) 时间内做查找，插入和删除，这里的 n 是树中元素的数目，这代表着它是牺牲编程效率提升性能的数据结构的代表。
在面试时，红黑树相关的问题也屡见不鲜，比如：红黑树的特性和优势，在什么情况需要变色，什么情况需要旋转？下面就对这些问题进行解读，要了解红黑树，我们需要先了解二叉查找树（Binary Search Tree）。
二叉查找树
二叉查找树（BST），又称二叉排序树，亦称二叉搜索树。它是数据结构中的一类，在一般情况下，查询效率比链表结构要高。
定义：
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
不同的教材定义略微有些不同，但不影响使用，下图中的树，就是一颗典型的二叉搜索树：
优点：
数组的搜索比较方便，可以直接用下标，但删除或者插入某些元素就比较麻烦；链表与之相反，删除和插入元素很快，但查找很慢。
而二叉排序树是一种比较有用的折衷方案，它就既有链表的好处，也有数组的好处，在处理大批量的动态的数据是比较有用。
从上面的图，我们可以轻松看出二叉排序树在查找元素时的方式正是二分查找的思想，同理，导致它可以在 O(log n) 时间内做查找，插入和删除操作。
缺点：
但是二叉搜索树仍存在它的缺陷，缺陷在某些情况下插入新节点，会导致它退化成链表，例如下图的情况：
这种形态的二叉树也符合二叉搜索树的特性，但相关操作的性能大打折扣，几乎退化成了线性O(n)，如何解决这种问题呢？红黑树这种数据结构就应运而生。
红黑树
如引入中说到的那样，红黑树是一种自平衡二叉查找树，说“自平衡”是因为它不严格保持平衡二叉树的性质，它的左右子树高差有可能大于 1。红黑树除了符合二叉查找树的基本特性外，它还有以下附加特性：
- 节点分为红色和黑色
- 根节点是黑色
- 每个叶子节点都是黑色的空节点（null）
- 每个红色节点的两个节点都是黑色（也就是从每个叶子到根的所有的根的所有路径上不能有两个连续的红色节点）
- 从任意一个节点到它的每个叶子节点的所有路径都包含相同数目的黑色节点（**最终是为了让任意节点到属于它的任意叶子结点的路径包含相同数目的黑色节点(根节点,叶子结点也算在数目内)**）
上图就是一颗经典的红黑树。
上述的约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
而在插入或者删除节点时，红黑树的规则可能会被打破。这个时候又需要做出一些调整，来继续维持红黑树的规则。争对这些变化，红黑树存在对节点的三种操作：
变色
为了重新符合红黑树的规则，尝试把将红黑树中红色节点变为黑色，或者把黑色节点变为红色。例如在插入一个节点21（如果插入节点是黑色，就一定会违背每条查找线上黑色节点个数一致的规则，插入红色，就可能不需要变色或者旋转，所以待插入节点都是红色）后，我们将节点22变成了黑色，避免了两个红色节点相邻：
但这是这一步操作并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：
此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：
要注意的是，上面的图只是红黑树的一部分，节点25也不是根节点，所以可以是红色，那如果是在一整棵上调整怎么办？那就要用到下面的旋转操作了；
旋转
左旋转
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子，这就称作当前节点的左旋转，例如下图：
在上图中，身为右孩子的节点60取代了节点40的位置，而节点40变成了节点60的左孩子并且节点50按照大小移动到了节点40的右孩子。
右旋转
与左旋转相对应的就是左旋转，顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子，例如下图：
与之前的左旋转操作刚好相反，这里就不再赘述。
举例
我们以刚才插入节点21的情况为例：
在经过上面变色中举例的一系列操作后，红黑树变成了这样：
此时节点17和节点25是连续的两个红色节点，那么把节点17变成黑色节点？恐怕不合适。这样一来不但打破了规则4，而且根据规则2（根节点是黑色），也不可能把节点13变成红色节点。
变色已无法解决问题，我们可以把节点13进行左旋转，像刚才的示意图那样进行左旋转：
左旋转后：
由于根节点必须是黑色节点，所以需要将节点17及左子树各节点进行变色，变色结果如下：
这样就结束了吗？并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5。
这时候我们需要把节点13进行右旋转，像刚才的示意图那样进行右旋转：
最后根据规则来进行变色整理：
在经过上面一系列变色和旋转组合的情况下，我们的红黑树变得重新符合规则，虽然操作看起来很复杂，但是在实际代码中，这样的操作耗费的时间量级并不大，不会影响到元素插入和删除的效率。
总结
红黑树是一种特殊的二叉搜索树，它牺牲了部分插入删除效率来避免了二叉搜索树退化成链表的情况，也避免了平衡二叉树过于追求平衡造成的频繁改动，总体还是比较高效方便的数据结构。它的应用场景比较经典的就是 JDK 集合类中的 TreeSet 和 TreeSet ，在JDK 1.8之后，HashMap 也变成了数组+链表/红黑树的实现方式，感兴趣的可以阅读相关的源码。
上述操作可以用比较通俗的话来说就是：在进行插入时，两个红色节点相邻就需要进行变色，当某一条查找线上黑节点多了就根据旋转规则把黑色节点从树分杈多的往树分杈少的地方转。
