树结构是数据结构中最经典最常用的结构之一，也是面试中常问的面试题，最近学习了一下红黑树的知识，记录整理一下

文章目录

前言

面试中我们经常会被问到 HashMap 在 1.7和 1.8 的区别，在 jdk 1.8 中，当链表的长度超过8数组长度大于64时数据结构改为了红黑树 ，当新插入一个值的时候，红黑树可能会进行变色 左旋 右旋的操作,这里对红黑树在什么情况下进行 变色 左旋 右旋的操作做一下整理

一、红黑树的特征

（1）每个节点或者是黑色，或者是红色

（2）根节点是黑色

（3）每个红色节点的两个子节点都是黑色。( 即： 不能有两个连续的红色节点)

（4）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

二、变色左旋和右旋

1. 变色规则

当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色（叔叔结点）：

（1）把父节点设为黑色

（2）把叔叔也设为黑色

（3）把祖父也就是父亲的父亲设为红色（爷爷）

（4）把指针定义到祖父结点设为当前要操作的（爷爷）分析的点变换的规则

这里我们新插入一个值 6 ( 插入的节点都是红色的 所以 6 是红色的节点) ，变色后的图形

2.左旋

当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树。左旋

左旋动态图 ( 爷爷从上面回来 爸爸从下面上去 以前挂靠着爸爸 现在挂靠着爷爷)

当前结构不满足红黑色，这里做一下左旋

3.右旋

当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树。右旋

（1）把父节点变为黑色

（2）把祖父结点变为红色（爷爷）

（3）把祖父结点旋转（爷爷）

右旋动态图

当前结构不满足红黑色，这里进行一下右旋

总结

以上是关于红黑树变色 左旋 右旋的一些规则，也是面试中常见的问题之一，这里对学习红黑树后做一下整理记录

如果觉得《HashMap 数据结构之红黑树 红黑树在什么时候左旋 右旋 如何旋转》对你有帮助，请点赞、收藏，并留下你的观点哦！