原理

reference：原文参考

红黑树介绍

红黑树是一棵二叉搜索树。普通的二叉搜索树最大节点深度是 (O(n))，但是红黑树最大深度为 (O(2log_2(n))) 。为了实现这一点红黑树为每个节点添加了颜色，

1. 每个节点非黑即红；
2. 根节点为黑色；
3. 同时保证每个根节点到每个叶子节点所经过的黑色节点数量相等（可以看作是对有效路径深度的一种度量）；
4. 同时保证父子节点不可能同时为红色节点;

上述几点也就是红黑树的基本性质，可以看到从根节点到叶子节点的最大深度的路径就是红黑节点交替的路径，该路径深度是最小路径深度（全为黑色节点的路径）的2倍。这就确保红黑树不会长的太偏。
红黑树例子：

节点插入

设新插入的节点为 x ，新插入节点的颜色总是红色（如果是黑色的话，意味这有效深度被改变了，一定需要调整，红色的话如果父节点是黑色的话就不用调整了）。x 的父节点记作 p，祖父节点记作 g , 叔叔节点记作 u。

1. 首先按照二叉搜索树找到 x 的插入位置，并设为红色；
2. 接下分情况(INSERT)
   1. x 为根节点，设置颜色为黑色；
   2. x 的父节点为黑色，已经满足要求，啥都不做。
   3. x 的父节点为红色，且存在叔叔节点并且其为红色。（因为父节点为红色，所以祖父节点一定为黑色）。
      1). 反转 x p u g 的颜色；
      2). 设 g 为 x，跳转到INSERT；
   4. x 的父节点为红色，且存在叔叔节点并且其为黑色或者不存在叔叔节点。
      1). 看 **x p g ** 是否在一条线上，不在的话通过左旋/右旋调整到一条线上。
      2). 进行左旋/右旋，将 g 下移。并交换 g 和 新的 g 的颜色。
      3). 设新的 g 为 x，跳转到INSERT；

情况2.3（黑-红-红布局）

情况2.4.a（已有一条左线，右旋）

情况2.4.b（旋转得到一条左线，右旋）

情况2.4.c（已有一条右线，左旋）

情况2.4.d（旋转得到一条右线，左旋）

节点删除

红黑树的删除首先按照传统二叉搜索书的方式搜索删除节点找到删除节点后，删除节点有如下情况：

1. 删除节点是叶子节点，且为红色； -> 直接删除即可
2. 删除节点是叶子节点，且为黑色； -> 进行删除后，平衡被打破，所以需要调整后才能删除该节点。
3. 删除节点是非叶子节点，且只有一个叶子节点；根据红黑树性质，我们知道这时待删除节点一定是黑色，子节点一定是红色，并且该子节点已经没有后继了。这时我们我们用子节点替换父节点，并将替换后的位置的节点颜色依旧设为黑色，然后进行调整。（和第二步的调整一样，不同的是，调整后不用再删除了，因为替换的时候已经删除掉了）
4. 删除的节点是非叶子检点，且有两个后继节点，这时我们找到该删除节点的后继节点，用后继节点的值替换删除节点的值，并设置后继节点为删除节点。需要注意的是该后继节点只有两种情况，要么是叶子节点，要么是第三种情况下的节点。所以进入1，2，3情况即可。

分析上述步骤发现，我们需要调整树平衡的地方只有 目标节点是黑色子节点的情况。
下面讨论如何进行平衡调整（镜像情况略去，无兄弟节点无需调整）。X 是待删除节点，S 为兄弟节点，P 父节点，L 和 R 分别为兄弟节点的左右子节点。

情况1：兄弟节点为红色，此时由红黑树性质决定了，兄弟节点一定由两个黑色子节点，调整方式为 Rotate + Recolor。

情况2：兄弟节点为黑色，且有一个右子节点，可以判定该右子节点为红色并且是叶节点，调整方式为 Rotate + Recolor。

情况3：兄弟节点为黑色，且有一个左子节点，同样可以判定该左子节点为红色并且是叶节点，调整方式为 Rotate + Rotate + Recolor。（经过一次 rotate 变为情况2）

情况4：兄弟节点为黑色，且有两个子节点，可以判定两个子节点均为红色，且均为叶子节点，调整方式为 Rotate + Recolor。

情况5：兄弟节点为黑色，且没有子节点。删除节点，将兄弟节点变红色，设父节点为递归节点，递归调整(不再删除)

c++ 代码

待续。