?
【事先声明：N(now)表示当前节点，P(parent)表示N的父节点，U(uncle)表示N的叔叔节点，G(grandfather)表示N的祖父节点，也就是P和U的父节点。】
?
几种需要变色和旋转的可能：
插入节点的父节点是红色的：
?
1.插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色。
应对策略：将当前节点的父亲节点P和叔叔节点M涂黑，祖父节点G涂红，再将祖父节点G设置为当前节点。
?
2.叔叔节点不存在或为黑节点，插入节点的父亲节点是祖父节点的左节点
2.1 插入节点是其父节点的左节点
应对策略：P设置为黑色，PP设为红色，对PP进行右旋
2.2 插入节点是其父节点的右节点
应对策略：把P进行左旋，把P设置为插入节点，进行2.1处理
?
3.叔叔节点不存在或为黑节点，插入节点的父亲节点是祖父节点的右节点
3.1 插入节点是其父节点的右节点
应对策略：P设置为黑色，PP设为红色，对PP进行左旋
2.2 插入节点是其父节点的左节点
应对策略：把P进行右旋，把P设置为插入节点，进行3.1处理
?
代码实现：
private void insertFixUp(RBNode<T> node){
????RBNode<T> parent,gparent;//定义父节点和祖父节点
????? ?
????//需要修正的条件：父节点存在，且父节点的颜色是红色
????while(((parent = parentOf(node)) != null) && isRed(parent)){
????????gparent = parentOf(parent);//获得祖父节点
????????? ?
????????//若父节点是祖父节点的左子节点，下面的else相反
????????if(parent == gparent.left){
????????????RBNode<T> uncle = gparent.right;//获得叔叔节点
????????????? ?
????????????//case1:叔叔节点也是红色
????????????if(uncle != null && isRed(uncle)){
????????????????setBlack(parent);//把父节点和叔叔节点涂黑
????????????????setBlack(gparent);
????????????????setRed(gparent);//把祖父节点涂红
????????????????node = gparent;//把位置放到祖父节点处
????????????????continue;//继续while循环，重新判断
????????????}
????????????? ?
????????????//case2:叔叔节点是黑色，且当前节点是右子节点
????????????if(node == parent.right){
????????????????leftRotate(parent);//从父节点出左旋
????????????????RBNode<T> tmp = parent;//然后将父节点和自己调换一下，为下面右旋做准备
????????????????parent = node;
????????????????node = tmp;
????????????}
????????????? ?
????????????//case3:叔叔节点是黑色，且当前节点是左子节点
????????????setBlack(parent);
????????????setRed(gparent);
????????????rightRotate(gparent);
????????}else{//若父节点是祖父节点的右子节点，与上面的情况完全相反，本质是一样的
????????????RBNode<T> uncle = gparent.left;
????????????? ?
????????????//case1:叔叔节点也是红色的
????????????if(uncle != null && isRed(uncle)){
????????????????setBlack(parent);
????????????????setBlack(uncle);
????????????????setRed(gparent);
????????????????node = gparent;
????????????????continue;
????????????}
????????????? ?
????????????//case2:叔叔节点是黑色的，且当前节点是左子节点
????????????if(node == parent.left){
????????????????rightRotate(parent);
????????????????RBNode<T> tmp = parent;
????????????????parent = node;
????????????????node = tmp;
????????????}
????????????? ?
????????????//case3:叔叔节点是黑色的，且当前节点是右子节点
????????????setBlack(parent);
????????????setRed(gparent);
????????????leftRotate(gparent);
????????}
????}
????setBlack(root);//将根节点设置为黑色
}
?
?
1.在查询性能方面红黑树略微逊色于AVL树，因为红黑树不是严格的平衡树
2.在增删方面，avl每次增删都需要进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于avl树为了维持平衡的开销要小得多
整体来说：红黑树是牺牲了严格的高度平衡的优越条件为 代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。
原文：https://www.cnblogs.com/beeenwei/p/12553174.html