红黑树原理
学习红黑树之前，你首先要有查询二叉树的知识储备，和平衡二叉树（AVL）的知识储备。
红黑树是基于AVL树的一种改良。红黑树平均来看和AVL树一样深，所以从而查找时间一样接近最优。红黑树的有点事执行插入操作所需要的开销相对较小，另外在执行中发生的旋转较少。
红黑树有以下几个条件：
1.每一个节点是红色或黑色（废话）
2.根节点是黑色
3.如果一个节点是红色，子节点必须是黑色
4.从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。
为了保持以上四点，需要在操作时进行一系列旋转和变色。新插入的节点必须默认是红色，原因很简单，如果插入的是黑色，那么肯定违反条件4，因此必须是红色。如果插入后父节点是黑色，那么插入完成。如果是红色，则需要进行变色和旋转。
首先规定插入节点是C(current)，父节点是P(parent)，祖父节点是G(grand)，叔叔节点(祖父节点的另一个子节点)是U（uncle）。
大概分四种情况：
1.插入的是根节点
直接插入，然后变色为红色
2.插入的节点父节点是黑色
直接插入。
3.插入的节点父节点是红色，叔叔节点是null或者是黑色
3.1 P是G的左子节点，C是P的左子节点
3.1.1
这个时候要对P节点和G节点进行变色，然后对G进行右旋转，操作完成。
这种情况还有一种镜像情况：
3.1.2
处理方式是一样的，只不过这个是进行左旋。
3.2 P是G的左子节点，C是P的右子节点
3.2.1
这种情况下首先对P节点进行左旋，然后就变成了3.1.1的情况，再按照3.1.1处理即可。
这种情况同样也有一种镜像情况：
3.2.2
处理方式也差不多，先对P节点右旋，在按照3.1.2进行处理即可。
4.父节点是红色，uncle节点也是红色
4.1
首先把P节点U节点以及G节点进行变色，变色后P，U节点为黑色，G为红色，如果此时不满足红黑树性质(比如G.parent是红色)，把G作为插入节点，向上进行递归处理，直到满足条件为止。
上代码：
public class RBTree<T extends Comparable> {
private RBNode<T> root;
private RBNode<T> current;
// 右旋
private RBNode<T> singleRotateToRight(RBNode<T> top) {
RBNode<T> newTop = top.left;
newTop.parent = top.parent;
top.left = newTop.right;
if (top.left != null) top.left.parent = top;
newTop.right = top;
top.parent = newTop;
return newTop;
}
//左旋
private RBNode<T> singleRotateToLeft(RBNode<T> top) {
RBNode<T> newTop = top.right;
newTop.parent = top.parent;
top.right = newTop.left;
if (top.right != null) top.right.parent = top;
newTop.left = top;
top.parent = newTop;
return newTop;
}
public void insert(T data) {
root = insert(data, root);
balanceInserted();
}
private RBNode<T> insert(T data, RBNode<T> node) {
if (node == null) {
node = new RBNode<>(data);
current = node;
} else {
if (data.compareTo(node.data) < 0) {
// 左侧
node.left = insert(data, node.left);
node.left.parent = node;
} else if (data.compareTo(node.data) > 0) {
// 右侧
node.right = insert(data, node.right);
node.right.parent = node;
}
}
return node;
}
private void balanceInserted() {
if (current == null) return;
if (current == root) {
root.isRed = false;
current = null;
return;
}
if (current.parent == root) {
return;
}
RBNode<T> parent = current.parent;
RBNode<T> grand = parent.parent;
RBNode<T> great = grand.parent;
RBNode<T> uncle;
if (!parent.isRed) return; // parent是黑色 不需要调整
// parent是红色
if (parent == grand.left) {
uncle = grand.right;
if (uncle == null || !uncle.isRed) {
// uncle是黑色或者是null
if (current == parent.left) {
// parent 左侧， child左侧
grand.isRed = true;
parent.isRed = false;
if (great == null) {
root = singleRotateToRight(grand);
root.isRed = false;
} else if (great.left == grand){
great.left = singleRotateToRight(grand);
} else {
great.right = singleRotateToRight(grand);
}
} else {
// parent左侧，child右侧
grand.left = singleRotateToLeft(parent);
current = grand.left.left;
balanceInserted();
}
} else {
// uncle是红色
uncle.isRed = false;
parent.isRed = false;
grand.isRed = true;
if (current == root) {
root.isRed = false;
} else {
current = grand;
balanceInserted();
}
}
} else {
uncle = grand.left;
if (uncle == null || !uncle.isRed) {
// uncle是黑色或者是null
if (current == parent.right) {
// parent 右侧， child右侧
grand.isRed = true;
parent.isRed = false;
if (great == null) {
root = singleRotateToLeft(grand);
root.isRed = false;
} else if (great.left == grand) {
great.left = singleRotateToLeft(grand);
} else {
great.right = singleRotateToLeft(grand);
}
} else {
// parent 右侧， child左侧
grand.right = singleRotateToRight(parent);
current = grand.right.right;
balanceInserted();
}
} else {
// uncle是红色
uncle.isRed = false;
parent.isRed = false;
grand.isRed = true;
if (current == root) {
root.isRed = false;
} else {
current = grand;
balanceInserted();
}
}
}
current = null;
}
public void printTree() {
printTree(root);
}
private void printTree(RBNode<T> node) {
if (node != null) {
System.out.println(node.toString());
printTree(node.left);
printTree(node.right);
}
}
}
tips:学习的时候容易有一个误区，总是想搞清楚为什么满足了这四个条件就能保持平衡，怀着这种论证的态度去学习红黑树非常可怕，毫无进展，而且根本没必要。直接根据定义去写一写，写出来再回过头去看，效率更好。
