一. 面试题及剖析
1. 今日面试题
你了解红黑树吗？
说说它的底层结构吧？
HashMap中，链表变成红黑树的阈值是多少？
HashMap中，红黑树变成链表的阈值是多少？
2. 题目剖析
你了解红黑树吗？
说说它的底层结构吧？
HashMap中，链表变成红黑树的阈值是多少？
HashMap中，红黑树变成链表的阈值是多少？
2. 题目剖析
在之前的两篇文章中，壹哥 给大家介绍了二叉树、B树、B+树等内容。我们对其概念、特点、分类、使用场景、存储结构、遍历方式等进行了必要的了解和掌握。但在树的子类中，还有一个很重要的子类--红黑树，该树也需要我们学习掌握，所以今天 壹哥 再给大家写一篇文章，介绍一下什么是红黑树。
我们之前学习HashMap与ConcurrentHashMap的时候，我给大家讲过，这两种集合的底层数据结构都用到了红黑树。当HashMap中出现了哈希冲突，为了解决这个冲突问题，会把同一个位桶上的数据拉成一个链表，当链表过长时又会转为红黑树来进行数据的存储。那么这棵红黑树到底是棵什么样的树？它有什么特点，它有什么能力，可以使得HashMap选择它来作为底层的存储结构呢？为什么不选用B树等其他树呢？
那么接下来请跟着 壹哥，来了解一下红黑树吧！
二. 红黑树详解
1. 概念
红黑树(Red Black Tree)，可以简称为R-B树，是一种自平衡的二叉查找树，所以它是一种特殊的二叉树。红黑树的每个结点上都有存储位来表示结点的颜色，可以是红色(Red)或者黑色(Black)。它是在1972年，由Rudolf Bayer这个大牛发明的，当时被称为平衡二叉B树(Symmetric Binary B-trees)。后来在1978年，被 Leo J. Guibas 和 Robert Sedgewick 这两个人进行了修改，成了现在的“红黑树”。
有些小伙伴可能会有疑惑，为啥非要叫“红黑树”呢？为啥不叫“黑白树”、“蓝绿树”？其实这里的“红”与“黑”，只是为了标记出二叉树中不同结点的状态、特征。作者一开始可能是觉得黑色最亮，红色最艳，比较好区分二叉树中的各个结点的高度，所以就叫“红黑树”了呗。如果当时作者喜欢别的颜色，可能就叫别的名字了。
红黑树可以在插入和删除操作时，通过特定的操作保持二叉查找树的平衡，从而获得较高的查找性能。一棵典型的红黑树如下图所示：
但红黑树并不是一棵完美的平衡二叉查找树。从上图可以看到，根结点的右子树显然比左子树高。但左子树和右子树中黑色结点的层数是相等的，即任意一个结点到到每个叶子结点的路径上都包含数量相同的黑色结点，所以我们把红黑树的这种平衡称为黑色完美平衡。
2. 作用
红黑树主要是用来存储有序的数据，它查询的时间复杂度是O(log n)，效率比较高，所以红黑树的应用是比较广泛的。比如在Java集合中的HashMap、ConcurrentHashMap、TreeSet和TreeMap，C++ STL中的Set、Map，以及Linux虚拟内存的管理，都是利用红黑树来实现的。
3. 特点(重点)
红黑树作为一种特殊的二叉树，有其自有的一些特征，如下：
红黑树的每个结点要么是黑色的，要么是红色的； 根结点必须是黑色的；每个叶子结点都是黑色的，值为NIL(为了确保删除结点时红黑树的平衡)；如果某个结点是红色的，则它的子结点必须是黑色的，即在一条路径上不能出现连续的两个红色结点； 从任何一个结点出发，到其自身所有的叶子结点为止，中间的所有路径上都有相同数目的黑色结点，这主要是确保没有任何一条路径会比其他路径长出两倍，这也是红黑树的关键特性； 如果一个结点存在黑色子结点，那么该结点肯定有两个子结点； 左子树上所有结点的值均小于或等于根结点的值； 右子树上所有结点的值均大于或等于根结点的值；一棵含有n个结点的红黑树，其高度最多为2log(n+1)。
4. 红黑树与二叉树的关系
红黑树算是一种特殊的二叉树，具体来说是平衡二叉查找树的一个变种。它左右子树的高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树(AVL)，它追求的是一种局部平衡，但对其进行平衡的代价较低，其平均性能要强于 AVL树。
每一棵红黑树都是一颗二叉排序树，因此在对红黑树进行查找时，都可以采用针对普通二叉排序树的查找算法，在查找过程中不需要额外的颜色信息。
5. 添加
红黑树的插入操作是一个比较复杂的操作，整体上来看，可以分为两部分：一是查找新结点要插入的位置；二是新结点插入后要确保红黑树的自平衡。整个插入的大致过程如下：
首先，将红黑树当作一颗二叉查找树，将某个新结点插入；
然后，将结点变色为红色；
最后，通过旋转和重新变色等方法来修正该树，使之重新成为一颗红黑树。
这里我们要根据被插入结点的父结点的情况，将"当前结点变色为红色结点，并插入二叉树"划分为3种情况来处理。
①.第1种情况：如果被插入的结点是根结点，则直接把此结点作为根结点，涂为黑色即可；
②.第2种情况：如果被插入结点的父结点是黑色的，则什么也不需要做。该结点被插入后，仍然是红黑树；
③.第3种情况：被插入结点的父结点是红色，此时要考虑的情况就比较多了。在这种情况下，被插入的结点是一定存在非空祖父结点的，而且被插入结点也一定存在“叔叔”结点(即使叔叔结点为空，我们也视之为存在，空结点本身就是黑色结点)。对于该情况，我们可以再细分为如下3种情况：case1: 当前结点的父结点是红色，且当前结点的祖父结点的另一个子结点(叔叔结点)也是红色； case2: 当前结点的父结点是红色，叔叔结点是黑色，且当前结点是其父结点的右孩子； case3: 当前结点的父结点是红色，叔叔结点是黑色，且当前结点是其父结点的左孩子。
这3种情况我们再分别考虑如下：
| 现象说明 | 处理策略 | |
| Case 1 | 当前结点的父结点是红色，且当前结点的祖父结点的另一个子结点(叔叔结点)也是红色。 | (01) 将“父结点”设为黑色。 |
| Case 2 | 当前结点的父结点是红色，叔叔结点是黑色，且当前结点是其父结点的右孩子 | (01) 将“父结点”作为“新的当前结点”。 |
| Case 3 | 当前结点的父结点是红色，叔叔结点是黑色，且当前结点是其父结点的左孩子 | (01) 将“父结点”设为“黑色”。 |
case1时示意图：
case2时示意图：
case3时示意图：
各位请注意，我这里不是红黑树的专门教程，本文只是针对红黑树的面试进行相关知识点的回顾复习，所以插入、删除、左旋、右旋等操作，讲的不会那么细！如果真要讲的很细，那么内容就会有很多了。
6. 删除
红黑树的删除操作也是非常复杂的，整体来看，删除操作可以包括两个部分：一是查找要删除的目标结点，二是要进行删除后的自平衡。
查找要删除的目标结点，显然可以复用查找操作，当不存在目标结点时，则忽略本次操作；当存在目标结点时，删除后需要进行自平衡处理。删除了结点后，我们还需要找结点来替代删除结点的位置，不然子树跟父辈结点就断开了，除非删除的结点刚好没有子结点，那么就不需要替代操作。
红黑树删除结点，查找删除结点时大致过程如下：
1. 若被删除结点没有子结点，直接删除该结点即可； 2. 若被删除的结点只有一个子结点，则直接删除该结点，并用其子结点替换被删除结点；3. 若被删除的结点有两个子结点，则用后继结点(大于删除结点的最小结点)替换删除该结点；4. 最后再通过"旋转和重新变色"等一系列操作来修正该树，使之重新成为一棵红黑树。
7. 红黑树的自平衡
红黑树在添加、删除结点后，因为结点数量发生了变化，此时现存的结点有可能不再满足红黑树的特征，所以就需要通过左旋、右旋、变色这3种操作来进行平衡，以此来满足红黑树的特点。
7.1 左旋以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
7.2 右旋以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
7.3 变色结点的颜色由红变黑或由黑变红。
三. 结语
至此，壹哥 就带大家复习了红黑树的相关内容，现在你学会了吗？但本文不是专门的红黑树教程文章，只是带大家复习红黑树相关内容，所以内容多有遗漏之处。如果你对红黑树完全不了解，还是建议再阅读其他红黑树教程。
码字创作不易，不知 壹哥 今天编写的内容有没有打动你呢？给来个点赞评论收藏三连击呗。
