红黑树:
红黑树是一棵二叉查找树(BST)，BST的查找效率为O(lgN), 但对于插入，某些情况下，偏向性严重的情况下会退化成类似于具有N个节点的线性链表，此时时间的复杂度可能会达到O(N)。红黑树在BST基础上，增加了着色和相关的性质，使得红黑树相对平衡，从而保证了红黑树的查找，插入和删除的时间复杂度为O(lgN)。
红黑树的性质
- 节点为红色或者黑色的
- 根节点为黑色的
- 所有叶子都是黑色的（NIL）
- 每个红色节点必须有两个黑色子节点(不可能出现两个连续的红色节点）
- 从任意一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点(这也要算上NIL)
红黑树的插入
红黑树的插入数据之前会进行数值比较，决定数据应该插入什么位置，且一定会在底部；插入的数据着色为红色，因为我们不能破坏性质5；插入完数据之后，根据红黑树的性质进行旋转，着色操作。
左旋
左旋：通用规则：变为其右孩子的左子节点
右旋
右旋：变为其左孩子的右子节点
插入
- 情况一：该树没有任何节点，插入的节点直接成为根节点，不用做任何改变
- 情况二：插入节点的父节点为黑色，则直接将该节点插入即可
-
情况三：插入节点的父节点为红色，如果想在原图中插入新节点(Insert)(红色),则会打破性质4，此时选择直接把父节点和叔节点变为黑色，然后爷爷节点变为红色，且要继续迭代，因为这样可能会出现爷爷和太爷爷的都是红色的情况，那么就要继续判断是哪种情况。
如图：
情况三.png -
情况三之后继续往上迭代或者停止，让(Insert == parent(parent(Insert)) == G),可能会出现当前Insert节点的父节点为红色，且叔叔节点为黑色，情况较为复杂，具体分为以下几种情况：
如图：
情况四.png -
对于符合图中(a)的情况，会选择先令Z = F节点， 然后对Z进行左旋，右旋之后F与Insert会倒换位置，此时G->F->Insert三点共线，为(b)的情况，即这一阶段分为两个阶段，一个从(a)->(b), 然后从(b)->最终；之后令Z节点的父节点即Insert变为黑色，选择Z = G节点，变为红色，然后对Z节点进行右旋。即如图：
情况(a).png -
对于符合图中(c)的情况，与上面的阶段相反：如图：
情况4(C).png
情况三，四伪代码：
RB_INSERT_NODE {
//将插入的新节点，颜色设置为红色
color(Insert) = RED;
/**
* 当插入的节点x不为空，不是根节点，并且父节点是红色的
* 因为如果父节点是黑色的，直接插入红色的新节点是不会影响红黑树的性质的，不用做任何操作
* 所以到这里已经把情况1和情况2都过滤掉了，下面就是对情况3和情况4的处理
* 并不是处理一次就能得到最后的结果，大家还需要注意x的重新赋值，进入下一次循环
*/
Z = Insert；
while (Z != null && Z != root && color(parent(Insert)) == RED) {
//如果Insert节点的父节点，为爷爷节点G的左孩子
if (parent(Insert) == left(parent(parent(Insert))) {
//那设置Insert的叔叔节点为Uncle
Uncle = right(parent(parent(Insert)));
//如果叔叔节点颜色是红色，那就是情况3
if (color(Insert) == RED) {
//设置父节点为黑色
setColor(parent(Insert), BLACK);
//叔叔节点也设置为黑色
setColor(Uncle, BLACK);
//设置祖父节点为红色
setColor(parent(parent(Insert)), RED);
//把Z设置为祖父节点，继续往上游循环
Z = parent(parent(Insert));
//否则叔叔节点的颜色是黑色，情况4
} else { //叔叔节点为黑色
//如果Insert是父节点的右节点，三点不一线，即情况(a)
if (Z== right(parent(Insert))) {
//基于刚刚新设置的Z节点进行左旋
rotateLeft(parent(Z));
}
//情况4的阶段2，此时三点一线了，为情况(b)
//设置Z节点的父节点为黑色
setColor(parent(Z), BLACK);
//祖父节点为红色
setColor(parent(parent(Z)), RED);
//基于祖父节点进行右旋
rotateRight(parent(parent(Z)));
}
//否则就是情况4的另外两种，父节点是爷爷节点的右子节点
} else {
Uncle = leftOf(parentOf(parentOf(x)));
//如果叔叔Uncle是红色，那就是情况3
if (colorOf(Uncle) == RED) {
setColor(parent(Insert), BLACK);
setColor(Uncle, BLACK);
setColor(parent(parent(Uncle)), RED);
//把Z设置为祖父节点，继续往上游循环
Z = parent(parent(Insert));
} else {
//否则叔叔Uncle是黑色，就是情况4，先判断是不是情况4的阶段1,
if (Z == left(parent(Z))) { //此时为情况4的图(c)
//阶段1会把插入的节点转到上面去，所以我需要重新设置插入的节点为原来的父节点
rotateRight(parent(Z));
}
//执行情况4的阶段2
setColor(parent(Z), BLACK);
setColor(parent(parent(Z)), RED);
rotateLeft(parent(parent(Z)));
}
}
}
root.color = BLACK;
}
删除数据节点
删除树中节点时分为两步：
1.为了保持二叉搜索树的性质，需要寻找要删除节点的替代者，即寻找继承节点，然后删除
首先删除节点的情况根据子节点的数目分为以下三种情况：
- 要删除的节点没有子节点，则直接删除
- 要删除的节点含有一个子节点，则直接用该子节点替代该节点，然后删除；如果该删除节点为单支黑节点，那么像BST那样将其子树接上，就相当于是删除了该节点。而这样一来，因为删除了一个黑节点，对于红黑树的第五个性质造成了破坏，这里就需要对红黑树进行调整。
- 要删除的节点含有两个子节点，则首先寻找继承节点；然后用后继节点的值来替换待删除节点的值，被删除节点的其余成员值保持不变，就相当于删除了该节点，同时继续对后继节点进行删除操作
选中继承节点的原理就和依据中序遍历寻找后继节点是一样的原理： - 该节点含有两个子节点，则继承节点为右子树的最左节点
2.删除节点之后，平衡此时的二叉树
平衡二叉树的情况：
1.当删除的节点为红色节点或者为根节点时不需要进行平衡
2.当删除的节点为黑色节点时，由于支路少了一个黑色节点，此时必须要进行平衡
情况一：删除的节点为黑色，且兄弟节点为红色；
删除过程如下：
这样删除且平衡后删除后，明显是不平衡的（S-P-NIL，只有2个黑，其他线都是3个黑），需要进入情况2继续判断（这时候设置新的兄弟节点为SL），进行下一步处理，需要进入情况二继续处理：
情况2-1：被删除节点的兄弟节点子节点全部为黑色
当删除节点的兄弟节点为黑色，可以直接把兄弟节点SL变为红色，P节点变为黑色即可。如图：
兄弟节点为黑色，且自己也是黑色，被删除了，左边少了黑色，就把同级的兄弟节点变成红色，因为兄弟节点的子节点又全部都是黑色，所以不会有影响后面。
情况2-2：被删除节点的兄弟节点子节点并不是全黑色，左孩子为红色，右孩子为黑色（在该种情况下，节点P的颜色不用做设定，无论黑红都是可以的）；
如下图所示：
此步骤的目的就是让SL的红色左子节点，变换到兄弟节点的右子树节点为红色，变换到右侧，此时被删除的节点的兄弟节点变为SL_L节点。之后交由情况2-3处理。
情况2-3：被删除节点的兄弟节点子节点并不是全黑色，右孩子为红色，左孩子为黑色；
如下图所示：
SL设置为P的颜色，SL的右子节点变为黑色，让P节点变为黑色，然后左旋，补充左子树被删除的黑色节点数量。情况2-2之所以要把左子树的红色节点变到右子树，就是为情况2-3做准备，然后让P节点来补充黑色节点数量。
//传入的是替换节点
fixAfterDeletion(D) {
while (D != root && color(D) == BLACK) {
//这里判断传入的节点是左孩子还是右孩子，
//是因为在左在右他的处理方式刚好是镜面对称
//所以得分开处理
//如果是左孩子
if (D == left(parent(D))) {
//拿到兄弟节点
Bro = right(parent(x));
//情况1：兄弟节点为红
if (color(Bro) == RED) {
setColor(Bro, BLACK);
setColor(parent(D), RED);
rotateLeft(parent(D));
Bro = right(parent(D));
}
//情况2-1：由于经过上面的处理，兄弟节点肯定为黑色
//这时，如果兄弟节点两个子节点都为黑
if (color(left(Bro)) == BLACK &&
color(right(Bro)) == BLACK) {
setColor(Bro, RED);
D = parent(D);
} else {
//情况2-2：兄弟节点右孩子是黑，左孩子是红，那就需要先把红色孩子转到右边
if (color(right(Bro)) == BLACK) {
setColor(left(Bro), BLACK);
setColor(Bro, RED);
rotateRight(Bro);
Bro = right(parent(D));
}
//情况2-3：如果红色孩子本身就在右边，那就执行最后一步旋转
setColor(Bro, color(parent(D)));
setColor(parent(Bro), BLACK);
rotateLeft(parent(D));
D = root;
}
} else { // symmetric，这里就是完全镜像处理，就不做详细注释了
Bro = left(parent(x));
if (color(Bro) == RED) {
setColor(Bro, BLACK);
setColor(parent(D), RED);
rotateRight(parent(D));
Bro = left(parent(D));
}
if (color(right(Bro)) == BLACK &&
color(left(Bro)) == BLACK) {
setColor(Bro, RED);
D = parent(D);
} else {
if (color(left(Bro)) == BLACK) {
setColor(right(Bro), BLACK);
setColor(Bro, RED);
rotateLeft(Bro);
Bro = left(parent(D));
}
setColor(Bro, color(parent(D)));
setColor(parent(D), BLACK);
setColor(leftOf(Bro), BLACK);
rotateRight(parent(D));
D = root;
}
}
}
setColor(D, BLACK);
}
