红黑树是一种稍微弱一点的平衡二叉树，它的定义如下：1. 每个节点或者是黑色，或者是红色。2. 根节点是黑色。3. 每个叶子节点（Null节点）是黑色。4. 如果一个节点是红色的，则它的子节点必须是黑色的。5. 从任意一个节点到叶子节点，经过的黑色节点是一样的。可以发现在满足红黑树定义的情况下，即使在最差的场景，红黑树的最大深度相较于完全平衡二叉树也只差常数倍（2倍）。
红黑树的核心在于两点：1. recolor（重新标记黑色或红色） 2. rotation（旋转）。
我们会先尝试 recolor，如果 recolor 不能达到红黑树的 4 点要求，然后我们尝试 rotation，其实红黑树的关键玩法就是弄清楚 recolor 和 rotation 的规则，接下来以插入节点为例：
- 将新插入的节点X标记为红色
- 如果X是根节点，则标记为黑色
- 如果X的parent不是黑色，且X也不是root则需要分类讨论：
- 如果X的Uncle节点（Parent节点的邻接节点）是红色，此时就执行recolor操作：
- 将父节点和Uncle节点标记为黑色
- 将祖父节点标记为红色
- 将祖父节点视为X节点，然后重复之前的过程
- 如果X的Uncle节点是黑色，此时分类执行rotation操作，另外这里需要注意，因为插入节点肯定是在叶子节点处进行，而在此之前树本身是符合红黑树性质的，因此Uncle节点只会是Null节点：
- 父节点在祖先节点的左边，且X节点在Parent节点的左边：在父节点进行右旋操作，也即想象有一根绳子，手提起父节点，然后变色即可!
- 父节点在祖先节点的左边，且X节点在Parent节点的左边：在父节点进行左旋操作，将X节点转到原来父节点所在的位置，此时回到3.2.1的情况，然后继续3.2.1的操作即可!
- 父节点在祖先节点的右边，且X节点在Parent节点的右边：在父节点进行左旋操作，也即想象有一根绳子，手提起父节点，然后变色即可!
- 父节点在祖先节点的右边，且X节点在Parent节点的左边：在父节点进行右旋操作，将X节点转到原来父节点所在的位置，此时回到3.2.3的情况，然后继续3.2.3的操作即可!
- 父节点在祖先节点的左边，且X节点在Parent节点的左边：在父节点进行右旋操作，也即想象有一根绳子，手提起父节点，然后变色即可!
- 如果X的Uncle节点（Parent节点的邻接节点）是红色，此时就执行recolor操作：
红黑树的删除相较于其插入而言更加复杂，删除的本质其实就是找一个替代节点（左子树的最小值，或者右子树的最大值），然后将删除节点的值替换为替代节点对应的值，最后删除替代节点，这里需要注意的是，替代节点一定是叶子节点。
在删除时一共会有多种情况：
- 替代节点是红色节点，此时直接删除即可
- 替代节点是黑色节点，此时会有以下情况：
- 兄弟节点是黑色的，且有一个右子节点（一定是红色的）
- 兄弟节点是黑色的，且有一个左子节点（一定是红色的）：将兄弟节点染成红色，子节点染成黑色，然后对于子节点进行右旋，从而变成1的情况即可
- 兄弟节点是黑色的，且有两个子节点（一定是红色的）
- 兄弟节点是黑色的，且没有子节点
- 兄弟节点是红色的，且有两个子节点（都是黑色的）
- 兄弟节点是黑色的，且有一个右子节点（一定是红色的）
