HashMap 数据结构之红黑树, 红黑树在什么时候左旋右旋如何旋转

短命女 2022-12-06 15:48 99阅读 0赞

#  #

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

### 文章目录 ###

*  一、红黑树的特征
 *  二、变色左旋和右旋
    
     *  1.变色规则
     *  2.左旋
     *  3.右旋
 *  总结

--------------------

# 前言 #

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

--------------------

**一、红黑树的特征**

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

（2）根节点是黑色

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

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

# 二、变色左旋和右旋 #

## 1. 变色规则 ##

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

（1）把父节点设为黑色

（2）把叔叔也设为黑色

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

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1cWlhbmt1bmxvbA_size_16_color_FFFFFF_t_70][]

## 2.左旋 ##

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

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

![20200914121928729.gif][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1cWlhbmt1bmxvbA_size_16_color_FFFFFF_t_70 1][]

## 3.右旋 ##

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

（1）把父节点变为黑色

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

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

右旋动态图

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

![20200914121954727.gif][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1cWlhbmt1bmxvbA_size_16_color_FFFFFF_t_70 2][]

--------------------

# 总结 #

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1cWlhbmt1bmxvbA_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1cWlhbmt1bmxvbA_size_16_color_FFFFFF_t_70]: /images/20221123/6b58f7515ab2430d931ece253e952dc7.png
[20200914121928729.gif]: /images/20221123/be5306b452bb4817b3052cd853a27dd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1cWlhbmt1bmxvbA_size_16_color_FFFFFF_t_70 1]: /images/20221123/807e79878ecd49edbef0bc9c721f47ce.png
[20200914121954727.gif]: /images/20221123/ec968296cee747d4b6d73ecf8e9a4ddf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1cWlhbmt1bmxvbA_size_16_color_FFFFFF_t_70 2]: /images/20221123/8f9984832f454c33bc0cca3015cd81dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1cWlhbmt1bmxvbA_size_16_color_FFFFFF_t_70 3]: /images/20221123/e7a1b0cf98a14b3689adb5ad6fac58c6.png