红黑是一棵特殊的平衡二叉树，其没有AVL树那么严格，其查找时间复杂的为2log2N，在实际开发中更加常用。
红黑树的特性
- 根节点为黑色；
- 不存在两个连续的红色节点；
- 叶子节点为NULL的黑色节点；
- 根节点到每个叶子节点所经过的黑色节点个数一致；
红黑树的插入
当插入的节点为根节点时，直接将根节点颜色置为黑色。
为了减少调整的次数，插入的子节点默认置为红色，当插入的节点的父节点为黑色时候，此时没有破坏红黑树的特征，不需要调整树。
当插入的节点的父节点为红色时，此时需要对树进行调整，主要有以下两种大的情况：叔叔节点为红色，叔叔节点为黑色。
叔叔节点为红色
叔叔节点为黑色
插入对应的代码：
//插入后检查并调整树
_proto._insertBalance = function(node) {
if (node.rChild && node.rChild.color == 1 && (node.rChild.lChild && node.rChild.lChild.color == 1 || node.rChild.rChild && node.rChild.rChild.color == 1)) { //右子树不平衡，需要调整
if (node.lChild && node.lChild.color == 1) { //如果左节点为红节点，不需要旋转，只需要改变颜色
node.lChild.color = 0;
node.rChild.color = 0;
if (node != this.root) { //如果是根节点，不需要变色
node.color = 1;
}
} else {
if (node.rChild.rChild && node.rChild.rChild.color == 1) { //左旋转
this._lRotate(node, true);
} else { //先右旋转，再左旋转
this._rlRotate(node);
}
}
} else if (node.lChild && node.lChild.color == 1 && (node.lChild.lChild && node.lChild.lChild.color == 1 || node.lChild.rChild && node.lChild.rChild.color == 1)) { //左子树不平衡，需要调整
if (node.rChild && node.rChild.color == 1) { //如果右节点为红节点，不需要旋转，只需要改变颜色
node.lChild.color = 0;
node.rChild.color = 0;
if (node != this.root) { //如果是根节点，不需要变色
node.color = 1;
}
} else {
if (node.lChild.lChild && node.lChild.lChild.color == 1) { //左旋转
this._rRotate(node, true);
} else { //先左旋转，再右旋转
this._lrRotate(node);
}
}
} else {
this._setHeight(node);
}
};
红黑树的删除
平衡二叉树的删除和二叉排序树的删除原则一样，如果待删除的既有左子树又有右子树，则将其与对应的叶子节点（没有左子树或者没有右子树）替换位置，再删除该叶子节点。
如果删除的节点为红色，不用调整树，直接删除即可。如果删除的节点为黑色（根据红黑树性质，其必然没有左右子树），则需要重新调整树。下面主要讨论删除黑色子节点的情况。
左子树缺少一个黑色节点
调整左子树对应的代码：
if (pNode.rChild && pNode.rChild.color == 1) { //兄弟节点为红色
pNode.color = 1;
pNode.rChild.color = 0;
this._lRotate(pNode);
//将兄弟节点变成黑色节点后，再平衡
this._deleteBalance(pNode, true);
} else if (pNode.rChild && (pNode.rChild.lChild && pNode.rChild.lChild.color == 1 ||
pNode.rChild.rChild && pNode.rChild.rChild.color == 1)) { //兄弟节点的子节点为红色
if (!pNode.rChild.rChild || pNode.rChild.rChild.color != 1) { //兄弟节点的右子节点不为红色
pNode.rChild.lChild.color = 0;
pNode.rChild.color = 1;
//先右旋转
this._rRotate(pNode.rChild);
}
var tmp = pNode.color;
pNode.color = pNode.rChild.color;
pNode.rChild.color = tmp;
pNode.rChild.rChild.color = 0;
this._lRotate(pNode);
} else if (pNode.color == 1) { //父节点为红色
pNode.color = 0;
pNode.rChild.color = 1;
} else {
pNode.rChild && (pNode.rChild.color = 1);
if (pNode != this.root) {
if (pNode.pNode.lChild == pNode) {
this._deleteBalance(pNode.pNode, true);
} else {
this._deleteBalance(pNode.pNode, false);
}
}
}
右子树缺少一个黑色节点
调整过程和（左子树缺少一个黑色节点）类似。
调整右子树对应的代码：
if (pNode.lChild && pNode.lChild.color == 1) { //兄弟节点为红色
pNode.color = 1;
pNode.lChild.color = 0;
this._rRotate(pNode);
//将兄弟节点变成黑色节点后，再平衡
this._deleteBalance(pNode, false);
} else if (pNode.lChild && (pNode.lChild.lChild && pNode.lChild.lChild.color == 1 ||
pNode.lChild.rChild && pNode.lChild.rChild.color == 1)) { //兄弟节点的子节点为红色
if (!pNode.lChild.lChild || pNode.lChild.lChild.color != 1) { //兄弟节点左子节点不为红色
pNode.lChild.rChild.color = 0;
pNode.lChild.color = 1;
//先左旋转
this._lRotate(pNode.lChild);
}
var tmp = pNode.color;
pNode.color = pNode.lChild.color;
pNode.lChild.color = tmp;
pNode.lChild.lChild.color = 0;
this._rRotate(pNode);
} else if (pNode.color == 1) { //父节点为红色
pNode.color = 0;
pNode.lChild.color = 1;
} else {
pNode.lChild && (pNode.lChild.color = 1);
if (pNode != this.root) {
if (pNode.pNode.lChild == pNode) {
this._deleteBalance(pNode.pNode, true);
} else {
this._deleteBalance(pNode.pNode, false);
}
}
}