红黑树：

红黑树是自平衡的二叉查找树。

在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态 。

自动处理达到平衡状态的方式：

1. recolor (重新标记黑色或红色)

2. rotation (旋转，这是树达到平衡的关键)

红黑树的特性：🔔

• 性质1：每个节点要么是黑色，要么是红色。

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

• 性质3：所有的NiL是黑色（NiL是叶子节点）图1

• 性质4：如果一个节点是红色，那么他的父亲，孩子都是黑色（两个红色节点不能相邻）

• 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

图1：一颗简单的红黑树

红黑树查找：

因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：

1. 从根结点开始查找，把根结点设置为当前结点；

2. 若当前结点为空，返回null；

3. 若当前结点不为空，用当前结点的key跟查找key作比较；

4. 若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；

5. 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；

6. 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；

如图2所示：

非常简单，但简单不代表它效率不好。正由于红黑树总保持黑色完美平衡，所以它的查找最坏时间复杂度为O(2lgN)，也即整颗树刚好红黑相隔的时候。能有这么好的查找效率得益于红黑树自平衡的特性，而这背后的付出，红黑树的插入操作功不可没～

红黑树插入：

插入流程

插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。查找插入的父结点很简单，跟查找操作区别不大：

1. 从根结点开始查找；

2. 若根结点为空，那么插入结点作为根结点，结束。

3. 若根结点不为空，那么把根结点作为当前结点；

4. 若当前结点为null，返回当前结点的父结点，结束。

5. 若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点的值，结束。

6. 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；

7. 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；

如图3所示：

ok，插入位置已经找到，把插入结点放到正确的位置就可以啦，但插入结点是应该是什么颜色呢？🙋答案是红色。理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

插入的规则与方式

左旋：被旋转的节点将变成一个左节点。（以旋转节点和其右子节点逆时针转动）

以a作为支点(旋转结点)，其右子结点b变为旋转结点a的父结点，a右子结点的左子结点d变为旋转结点a的右子结点（d之所以从b的左子节点变为a的右子节点，是因为当以a作为旋转节点进行左旋，其右子节点会成为旋转节点a的父节点，a成为一个b的左子节点，这时b的左子节点d与a冲突，由于红黑树是一个二叉树，左边的值小于右边的值，所以d>a，d成为a的右子节点，a原本的右子节点b由d替换），左子结点e保持不变。如图4。

右旋：被旋转的节点将变成一个右节点。（以旋转节点和其左子节点顺时针转动）

以b作为支点(旋转结点)，其左子结点a变为旋转结点b的父结点，a左子结点的右子结点d变为旋转结点b的左子结点（与左旋类似），右子结点c保持不变。如图5。

变色：结点的颜色由红变黑或由黑变红。重要特征： 是否违反了特性4，特性5。

所以旋转操作是局部的。另外可以看出旋转能保持红黑树平衡的一些端详了：当一边子树的结点少了，那么向另外一边子树“借”一些结点；当一边子树的结点多了，那么向另外一边子树“租”一些结点。

图4：左旋示意图

图5：右旋示意图

插入示例

假设我们插入的新节点为X

1. 将新插入的节点标记为红色

2. 如果X是根结点(root)，则标记为黑色

3. 如果X的 parent 不是黑色，同时 X 也不是 root

• 3.1 如果 X 的 uncle (叔叔) 是红色

• 
  

• 3.1.1 将 parent 和 uncle 标记为黑色

• 3.1.2 将 grand parent (祖父) 标记为红色

• 3.1.3 让 X 节点的颜色与 X 祖父的颜色相同，然后重复步骤 2、3

话不多说，看下图6

跟着上面的公式走:

1. 将新插入的 X节点标记为红色

2. 发现 X的 parent (P) 同样为红色，这违反了红黑树的第三条规则「不能有两个连续相邻的红色节点」

3. 发现X 的 uncle (U)同样为红色

4. 将 P和 U标记为黑色

5. 将X和X 的grand parent (G)标记为相同的颜色，即红色，继续重复公式 2、3

6. 发现 G是根结点，标记为黑色

7. 结束

刚刚说了 X 的 uncle 是红色的情况，接下来要说是黑色的情况

1. 如果 X 的 parent 不是黑色，同时 X 也不是 root

• 3.2 如果 X 的 uncle (叔叔) 是黑色，我们要分四种情况处理

• 3.2.1 左左 (P 是 G 的左孩子，并且 X 是 P 的左孩子)

• 3.2.2 左右 (P 是 G 的左孩子，并且 X 是 P 的右孩子)

• 3.2.3 右右 (和 3.2.1 镜像过来，恰好相反)

• 3.2.4 右左 (和 3.2.2 镜像过来，恰好相反)

当出现 uncle 是黑色的时候我们第一步要考虑的是 旋转 ，这里先请小伙伴不要关注红黑树的第 4 条规则，主要是为了演示如何旋转的，来一点点看，不要看图就慌，有解释的 :

左左情况

这种情况很简单，想象这是一根绳子，手提起 P 节点，然后变色即可(变色原则依据特性5)

左右情况

左旋: 使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的左孩子，然后再应用 左左情况

右右情况

与左左情况一样，想象成一根绳子

右左情况

右旋: 使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的右孩子，然后再应用 右右情况

归纳总结

从插入的情况来看，新插入的节点约定为红色，当插入节点与其父亲都是红色时，要么变色，要么旋转。

那么变色和旋转的依据是什么呢？？红黑树的5个特性。现在以我的理解（看大佬博客后自己的理解）来解释下5个特性，首先约定下概念如下图7（大佬的图，连接②）

上图描述：一方面是插入节点与其相关的主要节点，另一个方面以插入节点的祖父往下形成一个局部的一个平衡树（插入节点还没有插入之前或没变色之前，这个局部的树是平衡的）。

现在当插入了新节点I（红色）发现父亲也是红色，（I是P的左子节点）违反特性4，把父亲p变为黑色祖父pp变为红色，如果叔叔s是红色（1️⃣黑色情况下面讨论），那么变为黑色，改变颜色之后，红（I,PP），黑（P,S），特性4满足了。

看特性5，没插入新节点前，祖父PP往下，左树经过黑节点路径为（PP--->P），右树经过的黑节点路径为（PP--->S），左右路径的黑色节点数均为一个，平衡。插入新节点变色后，左树路径（PP--->P--->I），右树路径（PP--->S），左右路径的黑色节点数均为一个，平衡。所以只用图色不用旋转，如下图8。

在这个局部的子树中，当插入节点I的父亲和叔叔S为红色时，变色方案固定为（父亲，叔叔变黑，祖父（爷爷）变红）（每次变色特性4，特性5都会校验，在这里简化）。

上面局部树校验完之后，需要校验局部外面的树（为什么需要校验局部之外的树，因为PP节点的颜色变了，这个节点关联到局部树之外的树平衡），这时需要把PP设置为新的关键节点，以便PP与它的父亲，叔叔，爷爷形成一个新的局部子树，继续进行特性4，特性5的校验，当且仅当关键节点为root节点时，符合性质2，变为黑色。否则自底向上继续。

1️⃣的情况：可以看前面讲的左左情况，首先根据特性4，变色，p变为黑色，g变为红色，在这个局部树中黑色节点路径为：左g--->p--->x一个黑色节点，右g--->u一个黑色节点，这种情况不符合特性5，所以现在局部子树中需要旋转，这时特性4变色后的颜色为：红（x，g），黑（p，u）,这时关键节点为g爷爷这个节点，那么以这个节点右旋（如果左旋可以使用特性5校验下），旋转之后，局部树黑色节点路径为：左p--->x一个黑色节点，右p--->g--->u二个黑色节点，符合特性5，局部树平衡，因为局部节点的顶点还是黑色，所以没有破坏局部树之外的平衡，所以不用校验局部树之外的树。

关键节点的定位：（我的理解）当关键节点为红色且父亲也是红色，在没变色之前关键节点移动到父亲节点，当变色之后移动到爷爷节点，新插入的节点为关键节点。

左右情况：x是p的右子节点，变色之后，红（x，g），黑（p，u），符合特性4，g的左子树黑色节点路径为g--->p--->x共一个，右子树黑色节点路径为g--->u共一个，不符合特性5，

所以尝试旋转，左旋不符合特性5，尝试右旋g与p的右节点x冲突，旋转之后形成的图如下，再次变色，红（x，p），黑（g，u）

由p向下的左子树黑色节点路径p--->t10个，与插入之前少了一个，右子树黑色节点路径为p--->g--->u共两个，所以不符合特性5。那么回到最初的情况，x是p的右子节点，先旋转，关键节点p进行左旋，旋转之后发现局部树变成了左左情况，以左左情况继续平衡局部树，

那么右旋呢，p的左子节点因为p是红色根据特性4，那么该节点要么是黑色要么是NiL，旋转之后p的右子树多了一个黑色节点。

如果局部子树怎么变都不能平衡或者平衡也是以改变局部树与外部树的连接点为前提，那么这时以连接点为新的关键节点，使连接节点与它的主要相关节点组成一个局部树，再次的平衡。

前面讲解的方法，可以在插入的时候分为以下几种情况

情景4.2,4.3的情况分别是，左左，左右，右右，右左。

练习题与练习网站：

【10 70 32 34 13 56 32 56 21 3 62 4】

练习链接

[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html]

红黑树删除：

红黑树的删除操作也包括两部分工作：一查找目标结点；而删除后自平衡。查找目标结点显然可以复用查找操作，当不存在目标结点时，忽略本次操作；当存在目标结点时，删除后就得做自平衡处理了。删除了结点后我们还需要找结点来替代删除结点的位置，不然子树跟父辈结点断开了，除非删除结点刚好没子结点，那么就不需要替代。

普通二叉树删除结点找替代结点有3种情情景：

• 情景1：若删除结点无子结点，直接删除

• 情景2：若删除结点只有一个子结点，用子结点替换删除结点

• 情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点

前继节点，后继节点：

把二叉树所有结点投射在X轴上，所有结点都是从左到右排好序的，所有目标结点的前后结点就是对应前继和后继结点。如图所示。

二叉树投射在x轴上有序

接下来，讲一个重要的思路：删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点！话很苍白，我们看图。在不看键值对的情况下，下图的红黑树最终结果是删除了Q所在位置的结点！这种思路非常重要，大大简化了后文讲解红黑树删除的情景！

基于此，上面所说的3种二叉树的删除情景可以相互转换并且最终都是转换为情景1！

• 情景2：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为情景3，一直自顶向下转换，总是能转换为情景1。（对于红黑树来说，根据性质5.1，只存在一个子结点的结点肯定在树末了）

• 情景3：删除结点用后继结点（肯定不存在左结点），如果后继结点有右子结点，那么相当于转换为情景2，否则转为为情景1。

二叉树删除结点情景关系图如图所示。

综上所述，删除操作删除的结点可以看作删除替代结点，而替代结点最后总是在树末。

前提条件：先删除（替换），后调整平衡（变色，旋转）。替换节点是父节点的左子节点的情况下。根据替换后继节点的情况，分为两种。

删除时约定节点名称如图：

替换的节点有一个节点：

替换节点没有子节点：

X是要替换的节点，需要先替换删除节点之后，才做平衡操作，这也就导致P的左子树出现两种情况，有节点，无节点。

删除节点情况下，当替换节点为黑色的时候，影响比较大，所以这里说下，一个小技巧：

要么在左边增加一个黑色节点，要么在右边减少一个黑色节点（变色，旋转）。

下面讨论下删除的情况：

情况1：

X的节点只有一个，X的节点是红色，那么直接替换X节点即可（有子节点的话，子节点直接移动到X位置）。X删除之后，通过P的左子树并没有减少黑色节点。

当X为黑色的情况，下面会讨论

情况2：

当X有两个节点，X是黑色，X的右子节点是红色，需要把X删除后R移动到X位置并且变色，这样经过R节点的黑色节点就和原来的保持一致，符合特性5，如图：

情况3：

当X为黑色，删除之后的情况如下图：

这种情况下，P的左子树就少了一个黑色节点，那么这个局部树要么在左边增加一个黑色节点，要么在右边减少一个黑色节点。

继续讨论局部树，当S为红色节点时，因为特性4，并且在删除节点前，这是一个平衡树，所以，P，sl，sr都是黑色节点，进行变换之后，经过R的黑色节点还是少了一个，不满足特性5， 不过此时可以按照情况五、六、七进行调整。

情况4：

当R为黑色，p  s   sl   sr都为黑色时，这时考虑下，把右边的增加一个红色节点（左边减少了一个黑色），局部树可以恢复平衡，局部树平衡了，通过外部通过p节点少了一个黑色节点，那么这时把p当做关键节点，往上走，根据特性5变色。

情况5：

当R为黑色，s sl sr为黑色，p为红色，只需把p<->s换色即可，局部树保持平衡。

情况6：

当R为黑色，s  sr 为黑色，sl为红色，p任意，sl右旋，s<->sl换色，如图，此时所有路径上的黑色节点，与左边的删除节点之后的相同，p的左边还是少了一个黑色节点，不过此时可以进入情况7进行讨论。

情况7：

S 为黑色，S 的右孩子为红色。R的父节点颜色可红可黑，且 R 是其父节点左孩子。这种情况下，我们对 P 进行左旋操作，并互换 P 和 S 的颜色，并将 SR 变为黑色。因为 P 变为黑色，所以经过 R 的路径多了一个黑色节点，经过 R 的路径上的黑色节点与删除前的数量一致。对于不经过 N 的路径，则有以下两种情况：

1. 该路径经过 R 新的兄弟节点 SL ，那它之前必然经过 S 和 P。而 S 和 P 现在只是交换颜色，对于经过 SL 的路径不影响。

2. 该路径经过 R 新的叔叔节点 SR，那它之前必然经过 P、 S 和 SR，而现在它只经过 S 和 SR。在对 P 进行左旋，并与 S 换色后，经过 SR 的路径少了一个黑色节点，性质5被打破。另外，由于 S 的颜色可红可黑，如果 S 是红色的话，会与 SR 形成连续的红色节点，打破性质4（每个红色节点必须有两个黑色的子节点）。此时仅需将 SR 由红色变为黑色即可同时恢复性质4和性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。）

删除总结：

删除情况比较复杂，建议直接推导之后，直接记住这几种情况，当遇到删除时，直接对号入座。在看删除和插入的时候我也是懵逼的，幸好在网上看了几篇好的文章，这才总结出我的理解，当然这其中引用了大佬文章中的内容，

联系方式：

邮箱：[email protected]

参考引用（大佬博客链接）：

https://zhuanlan.zhihu.com/p/79980618https://zhuanlan.zhihu.com/p/79980618https://segmentfault.com/a/1190000012728513