【计算机基础——数据结构——红黑树】

1. 红黑树（RBTree）

为什么HashMap不直接使用AVL树，而是选择了红黑树呢？

由于AVL树必须保证左右子树平衡，Max(最大树高-最小树高) <= 1，所以在插入的时候很容易出现不平衡的情况，一旦这样，就需要进行旋转以求达到平衡。正是由于这种严格的平衡条件，导致AVL需要花大量时间在调整上，故AVL树一般使用场景在于查询场景， 而不是 增加删除 频繁的场景。

红黑树(rbt)做了什么优化呢？

红黑树(rbt)继承了AVL可自平衡的优点，同时, 红黑树(rbt)在查询速率和平衡调整中寻找平衡，放宽了树的平衡条件，从而可以用于增加删除 频繁的场景。在实际应用中，红黑树的使用要多得多。

与AVL树相比，红黑树牺牲了部分平衡性，以换取插入/删除操作时较少的旋转操作，整体来说性能要优于AVL树。虽然RBTree是复杂的, 但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的：

1.1 红黑树的特性（5条原则）

口诀：根黑叶黑，非红即黑，红黑相连，黑数相等

• 节点非黑即红
• 根节点一定是黑色
• 叶子节点（nil）一定是黑色
• 每个红色节点的两个子节点都为黑色。(等价于每个叶子到根的所有路径上不能有两个连续的红色节点)
• 从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。

RBT有点属于一种空间换时间类型的优化，
在avl的节点上，增加了 颜色属性的 数据，相当于 增加了空间的消耗。 通过颜色属性的增加， 换取，后面平衡操作的次数 减少。

• 红色属性 说明，红色节点的孩子，一定是黑色。 但是，RBTree 黑色节点的孩子，可以是红色，也可以是黑色。
• 叶子属性 说明， 叶子节点可以是空nil ，AVL的叶子节点不是空的，具体如下图。
  

基于上面的原则，我们一般在插入红黑树节点的时候，会将这个节点设置为红色，

原因参照最后一条原则： 红色破坏原则的可能性最小，如果是黑色, 很可能导致这条支路的黑色节点比其它支路的要多1，破坏了平衡。

1.2 黑色完美平衡

红黑树并不是一颗AVL平衡二叉搜索树，从图上可以看到，根节点P的左子树显然比右子树高

根据 红黑树的特性5，从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点， 说明：

rbt 的 左子树和右子树的黑节点的层数是相等的
红黑树的平衡条件，不是以整体的高度来约束的，而是以黑色节点的高度，来约束的。

去掉 rbt中的红色节点，会得到 一个四叉树， 从根节点到每一个叶子，高度相同，就是rbt的root到叶子的黑色路径长度。

1.3 红黑树的恢复平衡过程的三个操作

一旦红黑树5个原则有不满足的情况，我们视为平衡被打破，如何恢复平衡？

1.3.1 变色

节点的颜色由红变黑或由黑变红。（这个操作很好了解）

1.3.2 左旋

以某个结点作为支点(pivot)，其父节点（子树的root）旋转为自己的左子树（左旋），pivot的原左子树变成 原root节点的 右子树，pivot的原右子树保持不变。

1.3.3 右旋

以某个结点作为支点(pivot)，其父节点（子树的root）旋转为自己的右子树（右旋），pivot的原右子树变成 原root节点的 左子树，pivot的原左子树保持不变。

2. 红黑树插入节点情况分析

默认新插入的节点为红色，因为父节点为黑色的概率较大，插入新节点为红色，可以避免颜色冲突。

2.1 红黑树为空树

直接把插入结点作为根节点就可以了。
另外：根据红黑树性质 2根节点是黑色的。还需要把插入节点设置为黑色。

2.2 插入节点的Key已经存在

更新当前节点的值，为插入节点的值。

2.3 插入节点的父节点为黑色

由于插入的节点是红色的，当插入节点的父节点是黑色时，不会影响红黑树的平衡，所以： 直接插入无需做自平衡（因为每个节点自带两个Nil黑色节点）。

2.4 插入节点的父节点为红色

根据性质2：根节点是黑色。

如果插入节点的父节点为红色节点，那么该父节点不可能为根节点，所以插入节点总是存在祖父节点(三代关系)。

根据性质4：每个红色节点的两个子节点一定是黑色的。不能有两个红色节点相连。
此时会出现两种状态：

• 父亲和叔叔为红色
• 父亲为红色，叔叔为黑色

2.4.1 父亲和叔叔为红色节点

根据性质4：红色节点不能相连 ==》祖父节点肯定为黑色节点：
父亲为红色，那么此时该插入子树的红黑树层数的情况是：黑红红。
因为不可能同时存在两个相连的红色节点，需要进行 变色， 显然处理方式是把其改为：红黑红

变色处理：黑红红 ==> 红黑红

1. 将F和V节点改为黑色
2. 将P改为红色
3. 将P设置为当前节点，进行后续处理

可以看到，将P设置为红色了，如果P的父节点是黑色，那么无需做处理；
但如果P的父节点是红色，则违反红黑树性质了，所以需要将P设置为当前节点，继续插入操作, 做自平衡处理，直到整体平衡为止。

2.4.2 叔叔为黑色，父亲为红色，并且父亲节点是祖父节点的左子节点

2.4.2.1 插在父亲的左节点（LL型失衡）

细分场景 1： 新插入节点，为其父节点的左子节点(LL红色情况)， 插入后 就是LL 型失衡

1. 变颜色：将F设置为黑色，将P设置为红色
2. 对F节点进行右旋
   

2.4.2.2 插在父亲的右节点（LR型失衡）

细分场景 2： 新插入节点，为其父节点的右子节点(LR红色情况)， 插入后 就是LR 型失衡

1. 对F进行左旋
2. 将F设置为当前节点，得到LL红色情况
3. 按照LL红色情况处理(1.变色 2.右旋P节点)

2.4.3 叔叔为黑节点，父亲为红色，并且父亲节点是祖父节点的右子节点

2.4.3.1 RR型失衡

新插入节点，为其父节点的右子节点(RR红色情况)

自平衡处理：
1.变色：将F设置为黑色，将P设置为红色
2.对P节点进行左旋

2.4.3.2 RL型失衡

新插入节点，为其父节点的左子节点(RL红色情况)

自平衡处理：

1. 对F进行右旋
2. 将F设置为当前节点，得到RR红色情况
3. 按照RR红色情况处理(1.变色 2.左旋 P节点)