每次找工作面试八股文肯定少不了，集合就是其中一个，map集合中问的最多的就是hashMap和ConcurrentHashMap两个了。这两个集合在1.8之后就使用到了红黑树，所以这篇文章主要介绍的是红黑树，把红黑树搞懂再去看hashmap和concurrentHashMap就会发现很简单，根本不用每次面试都要去死记硬背，过不了几天就忘了。
首先关于树的概念就不介绍了，二叉查找树我们都知道左子节点<根节点<右节点，使用这种结构来查找一个数就很快；但如果出现了一些极端情况就不那么快了，比如下面的情况：
极端二叉查找树
如果出现了上图的这种数，那么时间复杂度就变成了O(n)。为了解决这种情况可以使用平衡二叉树；平衡二叉树也是二叉查找树，只不过平衡二叉树多了一个条件：左子树和右子树差的绝对值不大于1。平衡二叉树的实现方式有很多，红黑树就是其中一种
红黑树的特性
根据一张图来说红黑树的特性：
红黑树结构
- 每个节点不是黑色就是红色
- 根节点是黑色的
- 每个叶子节点(NIL)是黑色的。这里没有画出来，就是2、5、7、9每个节点下面还各有两个NIL的叶子节点，而我们操作的只到2、5、7、9
- 两个红色节点不可相连（即两个红色节点不能是父子节点）
- 任意一个节点到每个叶子节点的路径都包含相同数量的黑色节点（比如4到叶子节点的黑色数量是2，8也是）
红黑树并不是一个完美的平衡二叉树，红黑树可以做到自平衡靠的是变色、左旋、右旋三种方式
变色：理解很简单，就是红色变黑色，黑色变红色
左旋&右旋：对于左旋和右旋大多解释得很拗口，反正我是听不懂，我放一张图来解释
红黑树左旋&右旋
上面一张动态图就表示了红黑树的左旋和右旋，看图就可以一目了然。接下来就挨个分析。
左旋
左旋
根据这个图说左旋的步骤：
1）将y的左子树（如果不为空）的父节点指向x，x的右子树指向y的左子树
2）如果x的父节点不为空，将y的父节点指向x的父节点，并将x的父节点指向y
3）将x的父节点指向y，将y的左子树指向x
备注：上图中的P是一个树结构，在第二点中将x的父节点指向y时，需要判断x在父节点的左子树上还是右子树上：如果是左子树：x.parent.left = y;如果是右子树：x.parent.right = y;
右旋
右旋
根据这个图说右旋的步骤：
1）将y的左子树指向x的右子树，并将x的右子树（如果不为空）的父节点指向y
2）如果y的父节点不为空，将x的父节点指向y的父节点，将y的父节点指向x
3）将x的右子树指向y，将y的父节点指向x
备注：和左子树的旋转是一样的，在第二点“将y的父节点指向x”，需要判断y是P的左子树还是右子树，如果是左子树：y.parent.left = x;如果是右子树：y.parent.right = x;
知道了红黑树的基本操作，那么就会有疑问：这三种操作分别是什么时候进行呢？
在这之前需要知道一个前提：每插入一个数据时，默认的颜色是红色！
红黑树操作场景：
1）如果树结构为空，将插入的节点颜色改为黑色
2）如果插入节点的父节点是黑色，那就说明都不用问，直接挂在父节点的左子树或者右子树上即可
3）如果插入节点的父节点是红色
3.1）如果插入节点存在叔叔节点并且为红色（父节点和叔叔节点都是红色），将父节点和叔叔节点改为黑色，祖父节点改为红色，然后以祖父节点为当前节点进行下一轮处理（即以祖父节点为当前节点再次从第一点开始）
3.2）如果叔叔节点不存在或者叔叔节点为黑色
3.2.1）父节点是祖父节点的左子树
3.2.1.1）插入的节点在父节点的左子树上（LL双红），将父节点改为黑色，祖父节点改为红色，以祖父节点为当前节点进行右旋
3.2.1.2）插入的节点在父节点的右子树上（LR双红），以父节点进行左旋，这样就会得到LL双红的情景（得到3.2.1.1的情景），然后以父节点为当前节点进行下一轮处理（即从第一点开始）
3.2.2）父节点是祖父节点的右子树
3.2.2.1）插入的节点在父节点的右子树上（RR双红），将父节点改为黑色，祖父节点改为红色，以祖父节点进行左旋
3.2.2.2）插入的节点在父节点的左子树上（RL双红），以父节点进行右旋，这样就得到了RR双红的情况，然后以祖父节点进行下一轮处理
说了这么多的文字是不是搞迷糊了，接下来会使用一张图结合上面的文字来说红黑树的自平衡。
红黑树插入
上面的图是一个红黑树，现在需要插入一个19，首先根据BST的规则，19应该放在20的左子树上，对照上面的规则3进行匹配发现是符合3.1的：父节点和叔叔节点都是红色，那么就根据这个规则进行调整：父节点和叔叔节点改为黑色，祖父节点改为红色，以祖父节点为当前节点进行下一轮的处理：
根据3.1规则进行调整
以22为节点再次从第一点开始进行匹配，发现匹配到了3.2.1.2，就以18进行左旋
以18进行左旋
上图是左旋之后的结果，然后再以18位节点从第一点开始验证匹配，发现匹配到了3.2.1.1，根据这个规则，将父节点22改为黑色，祖父节点25改为红色，然后以25为节点进行右旋
以25进行右旋
以25进行右旋的结果，然后再看这颗红黑树是不是就调整完了，至于3.2.2中的情况，可以自己画图尝试下。我觉得学数据结构和算法的东西一定要动手练，动手画，如果只是凭自己看，就很容易出现眼高手低。甩开这些内容自己去想或者过几天再想整个过程的时候能不能想的起来。
红黑树的代码我这就不贴了。后面会介绍在删除的时候是如何保证红黑树的自平衡以及hashmap中使用红黑树的情况
学习Java集合框架是学习数据结构最好的教材，同样设计模式也是。Java源代码把设计模式用到了极致（个人的一些见解）
- 本文分类：知识大全
- 本文标签：无
- 浏览次数：73 次浏览
- 发布日期：2024-01-28 16:32:23
- 本文链接：http://www.liekang.com/286194.html
- 上一篇 > 甲骨文的发现，意义有多大？
- 下一篇 > 吉隆坡是哪个国家——马来西亚吉隆坡
