删除|字节算法大神熬了三个通宵整理的数据结构与算法笔记（万字长文）( 七 )

操作示意图如下：

case3
若关注节点是 a ，它的叔叔节点 d 是黑色， a 是其父节点 b 的左子节点。则进行如下操作：
1. 围绕 a 的祖父节点 c 右旋；
2. 将 a 的父节点 b、兄弟节点 c 的颜色互换。
操作示意图如下：

小结：插入后的修复操作是一个向 root 节点回溯的操作过程，一旦涉及的节点都符合了红黑树的定义，则修复操作结束。之所以会向上回溯是由于 case1 操作会将父节点、叔叔节点和祖父节点的颜色进行互换，可能会导致祖父节点不平衡，此时需要对祖父节点进行修复，以此类推。
删除操作
若删除的是叶子节点就直接删除；若不是叶子节点，会用对应的中序遍历的后继节点来顶替要删除的节点的位置。
删除操作的总体思想：从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否平衡，若不平衡则继续向上追溯调整。
删除节点的平衡性调整大概分为四种情况（对称情况下的操作类似）：
case1
待删除节点的兄弟节点是红色。则进行如下操作：
1. 围绕父节点 A 进行左旋；
2. 将父节点 A 和祖父节点 C 颜色互换；
3. 跳转到 case2、case3 或 case4 。
操作示意图如下：

case2
待删除节点的兄弟节点是黑色，且兄弟节点的子节点都是黑色。则进行如下操作：
1. 将兄弟节点 C 的颜色设置为红色；
2. 关注节点上溯为父节点 A 。
操作示意图如下：

case3
待调整节点的兄弟节点是黑色，且左子节点是红色、右子节点是黑色（兄弟节点在右边的情况。若兄弟节点在左边，就是右子节点是红色，左子节点是黑色）。则进行如下操作：
1. 围绕兄弟节点 C 右旋；
2. 将节点 C 和 D 变换颜色；
3. 跳到 case4 。
操作示意图如下：

case4
待调整节点的兄弟节点是黑色，且右子节点是红色、左子节点是黑色（兄弟节点在右边的情况。若兄弟节点在左边，就是左子节点是红色、右子节点是黑色）。则进行如下操作：
1. 围绕父节点 A 进行左旋；
2. 删除 B 节点。
操作示意图如下：

删除修复操作是针对删除黑色节点才有的，需要从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑色节点可以借调的话，就只能向上追溯。
小结
红黑树是一种常见的平衡二叉树，结构稍微复杂了点，主要体现在插入和删除的时候需要进行旋转和变色的平衡性调整操作。
【删除|字节算法大神熬了三个通宵整理的数据结构与算法笔记（万字长文）】在 JDK 1.8 的源码中， TreeMap 和 HashMap 都用到了红黑树