一.红黑树规则
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色
- 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
- 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。（插入新值时，其一定为红色节点。否则不符合4条件）
二.插入节点
1. 红黑树的平衡
红黑树的平横有三种方法
1.左旋
2.右旋
3.改变节点颜色
2. 左旋
左旋
3. 右旋
右旋
4.红黑树插入的三种情况
（1）case 1 新插入节点的父节点是红色，其父节点的兄弟节点也是红色时，通过变色操作调整平衡
1.gif
（2）case2 新插入节点的父节点为红色，父节点的兄弟节点为黑色时，且父节点、祖父节点和新节点3个节点在同一方向上（一条直线）
2.gif
（3）case3 新插入节点的父节点为红色，父节点的兄弟节点为黑色时，且父节点、祖父节点和新节点3个节点不在同一方向上（不是一条直线）该种情况需要旋转2次。
3.gif
总结：所以红黑树插入会有6种情况，插入时父节点在祖父节点的左边或者在祖父节点右边。并分别有case1-case3三种情况，加起来即六种情况
5 .put 方法实现（来自jdk1.8treemap源码）
Node<K,T> root;
static final boolean RED=true;
static final boolean BLACK=false;
public boolean put(K key,T object)
{
if(root == null)
{
root = new Node<>(key,object,null);
root.color=BLACK;
return true;
}
else
{
int cmp;
Node<K,T> parent;
Node<K,T> t = root;
//比较key值的大小
Comparable<? super K> tComparabler = (Comparable<? super K>) key;
do
{
parent = t;
cmp = tComparabler.compareTo(t.key);
if(cmp < 0)
{
t = t.left;
}
else if(cmp > 0)
{
t = t.right;
}
else
{
t.object = object;
return true;
}
}
while (t != null);
Node<K,T> targetNode = new Node<>(key,object, parent);
if(cmp > 0)
{
parent.right = targetNode;
}
else if(cmp < 0)
{
parent.left = targetNode;
}
//平衡红黑树
fixAfterInsertion(targetNode);
}
return true;
}
6.平衡的实现（来自jdk1.8treemap源码）
private void fixAfterInsertion(Node<K,T> x)
{
x.color=RED;
while (x!=null&&x!=root&&x.parent.color==RED)
{
if(parentof(x)==leftOf(parentof(parentof(x))))
{
Node<K,T> y = rightOf(parentof(parentof(x)));
if(colorOf(y)==RED) //case 1
{
setColor(parentof(x),BLACK);
setColor(y, BLACK);
setColor(parentof(parentof(x)),RED);
x=parentof(parentof(x));
}else {
if(x==rightOf(parentof(x))) //case 3;
{
x=parentof(x);
rotalLeft(x);
}
setColor(parentof(x),BLACK); //case 2;
setColor(parentof(parentof(x)),RED);
rotalRight(parentof(parentof(x)));
}
}
else {
Node<K,T> y = leftOf(parentof(parentof(x)));
if(colorOf(y)== RED)
{
setColor(parentof(x),BLACK);
setColor(parentof(parentof(x)),RED);
x=parentof(parentof(x));
}
else
{
if(x==leftOf(parentof(x)))
{
x=parentof(x);
rotalRight(x);
}
setColor(parentof(x),BLACK);
setColor(parentof(parentof(x)),RED);
rotalLeft(parentof(parentof(x)));
}
}
}
root.color=BLACK;
}
7.左旋，右旋实现（来自jdk1.8treemap源码）
private void rotalRight(Node<K,T> x)
{
if(x.left==null)
{
throw new RuntimeException("不能右旋，左子节点为空");
}
Node<K,T> left = x.left;
if(parentof(x)==null)
{
root=left;
}else if(leftOf(parentof(x))==x)
{
parentof(x).left=left;
}
else if(rightOf(parentof(x))==x)
{
parentof(x).right=left;
}
left.parent=x.parent;
x.parent=left;
x.left=left.right;
if(left.right!=null)
{
left.right.parent=x;
}
left.right=x;
}
private void rotalLeft(Node<K,T> x)
{
if(x.right==null)
{
throw new RuntimeException("不能左旋，右子节点为空");
}
Node<K,T> right = x.right;
if(parentof(x)==null&&root==x)
{
root=right;
}else if(x==rightOf(parentof(x)))
{
parentof(x).right=right;
}else if(x==leftOf(parentof(x)))
{
parentof(x).left=right;
}
right.parent=x.parent;
x.parent=right;
x.right=right.left;
if(right.left!=null){
right.left.parent=x;
}
right.left=x;
}
三.删除节点
- 删除节点的四种情况
- 待删除节点的兄弟节点是红色。
- 待删除节点的兄弟节点是黑色，且兄弟节点的子节点都是黑色。
- 待删除节点的兄弟节点是黑色，如果兄弟节点在右侧，且兄弟节点的左
子节点是红色，右子节点是黑色。如果兄弟节点在左侧，就是兄弟节点的
右子节点是红色，左节点是黑色。 - 待删除节点的兄弟节点是黑色，如果兄弟节点在右侧，且兄弟节点的右子节点是红色，左子节点是任意颜色。如果兄弟节点在左侧，则就是兄弟节点的左子节点是红色，右子节点是任意色。
- 动图演示
case 1：对于 Case 1,首先改变父节点和兄弟节点颜色(兄弟节点变为黑色，父节点变为红色)，再对父节点做一次旋转（红色的兄弟节点在右侧，左旋。红色的兄弟节点在左侧，右旋），操作后，红黑的规则没有被破坏，树的黑色高度没变化，原兄弟节点的一个子节点变成删除节点的新兄弟节点。
1.gif
case 2：对于Case 2，删除节点后其父节点的左子树比右子树黑高度小1，此时需要把兄弟节点改为红色，则左右子树黑高度就相同了。此时将删除节点的父节点变为新的节点，然后继续向上迭代调整，修正平衡
2.gif
case 3：对于Case 3，兄弟节点在右侧时，交换兄弟节点和其左子节点(红色)的颜色，并对兄弟节点进行右旋，于是被删除节点的新兄弟是一个有红色右子节点的黑色节点。相反，兄弟节点在左侧时，交换兄弟节点和其右子节点(红色)的颜色，并对兄弟节点进行左旋，于是被删除节点的新兄弟是一个有红色左子节点的黑色节点
3.gif
case 4：对于Case 4，兄弟节点在右侧时，兄弟节点和父节点交换颜色，把兄弟节点的右子节点设为黑色，并对删除节点的父节点做一次左旋转。
兄弟节点在左侧时，兄弟节点和父节点交换颜色，把兄弟节点的左子节点设为黑色，并对删除节点的父节点做一次右旋转。（经过case4后，红黑树完全平衡）
最后将删除节点直接指向根节点，循环结束。
4.gif
-
删除节点平衡红黑树的代码演示（来着jdk1.8threemap源码）
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); //情况1 rotateLeft(parentOf(x)); sib = rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); //情况2 x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); //情况3 rotateRight(sib); sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); 情况4 rotateLeft(parentOf(x)); x = root; } } else { // symmetric Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK);}
