1 描述
在之前描述的AVL树中，对于删除某个元素导致树不平衡的情况，需要进行旋转调整，使之恢复平衡。然而，该过程可能需要沿着parent关系经历O(logn)次旋转操作才可使得整棵树平衡。因此，在此基础上设计出来另外一种数据结构--红黑树，它的添加和删除的旋转操作都是O(1)级别，但需要牺牲一些平衡性。
文章省略了对于B树，AVL树的一些性质和操作的描述，可参考AVL树、B树。
1.1性质
红黑树需满足以下几条性质：
- 结点是RED或者BLACK
- 根结点是BLACK
- 叶子结点外(这里指外部的空节点)都是BLACK
- RED节点的子节点都是BLACK
- RED节点的parent都是BLACK
- 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
- 从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点
- 每一个黑节点和红孩子组合,可得到一棵4阶B树,因此可从B树性质的角度分析红黑树，可参考B树
2 操作流程
2.1 查找元素
红黑树继承于二叉排序树，因此其查找方式和二叉排序树相同。另外，对于结点的旋转，获取前驱后继等操作本文不再赘述，可参考前面的章节：AVL树。
2.2 添加元素
我们对添加的元素默认设置为RED颜色，有可能破坏红黑树的性质，分为以下几种情况，对其进行相应的调整：
-
parent为BLACK：添加后依然满足红黑树的所有性质，同样也满足4阶B树的性质，因此无需调整。
上图将连线画成B树形式，在添加40、78、82、90后依然满足红黑树的所有性质。 -
parent为RED，uncle节点为BLACK的情况**：这里的uncle节点指叔父节点，如56和90的uncle结点位35。在添加元素后，形成Double Red，破坏了红黑树的性质，对其进行调整。事实上在添加元素中，uncle节点为BLACK的情况，意味着uncle节点一定是空节点。主要调整操作为可分为LL、LR、RR、RL四种情况：将旋转后的parent节点染BLACK，左右孩子染成RED。
上图描述了添加元素52,60后的红黑树调整示意图。 -
parent为RED，uncle节点为RED的情况**：该情况在B树角度表示为上溢，如图所示，需要对其进行上溢调整，因此在红黑树中也只需进行对应操作即可。主要调整操作为：将grand节点染红，parent和uncle节点染黑，之后进行将grand节点作为一个新节点插入到红黑树后的调整过程。
上图描述了添加30的调整过程，添加30后，将其祖父节点25染红，并进行作为新结点插入后的重新调整过程，因此将50染红，38、80染黑，最后进行将50继续作为新节点插入后的调整过程，由于50是根结点，因此只需直接染黑即可。
2.3 删除元素
由于红黑继承二叉排序树，因此在删除节点后，如果删除的是度为2的结点，会选择其前驱或者后继来代替被删除的节点，因此最终删除的结点在其转换成B树形式后的叶子节点中，可参考二叉排序树、B树。
-
删除节点为RED：直接删除，无需做任何调整。
如删除途中的17、33、50、72结点。再如，删除38，则会选择其前驱33替换38，最终删除的结点为33。 -
删除节点为BLACK，并且只有1RED个孩子：在二叉排序树中，这种情况不存在其还有2个孩子的情况，原因是会继续向下寻找被删除节点的前驱或后继。因此被删除的节点如果是BLACK，其只可能存在一个孩子或者没有孩子的情况，而且如果有孩子，这个孩子的颜色必定为RED，原因是如果为BLACK，将会破坏红黑树的性质：从根节点到叶子节点的所有路径上不能有2个连续的RED节点。对于上述情况，只需将其孩子替换当前节点，并将其染BLACK即可。
-
上图描述了删除46、76的示意图。 -
删除节点为BLACK，并且没有孩子：即删除的节点为BLACK叶子结点的情况。从B树角度可知（性质8），删除元素后造成下溢，进而对其进行下溢调整。下溢调整有如下几种情况：
1)兄弟节点有多余的红孩子，则可向兄弟节点借一个元素，则只需进行旋转操作即可，如图删除节点88，进行兄弟节点76可借，对80进行LR调整，调整后，上面的节点跟随parent原来的颜色，左右孩子染BLACK，进而得到下图所示。2)兄弟节点没有多余的RED节点，则无法借元素，则只需将parent染BLACK，兄弟节点染成RED即可。当parent原来也是BLACK时，则相当于将原来的parent代替了被删除节点的位置，此时发生下溢，进一步把parent也当成被删除节点处理即可。
上图所示删除88后，将80染黑，76染红，恢复红黑树性质。但当80本身为BLACK时，删除88进行上述操作，相当于将80代替了原来88的位置，造成下溢。
3)兄弟节点为RED结点，在B树角度，兄弟节点应该为BLACK节点。兄弟节点染BLACK,parent节点染成RED,旋转改变兄弟节点，之后回到上述1)2)中的情况。
上图所示删除88，但兄弟节点55位红，将其染黑，父节点80染红，之后旋转调整76为其兄弟，之后进行1)或2)的操作即可。
3 算法描述
本节使用Java语言描述红黑树数据结构，由于红黑树继承于平衡二叉搜索树，并在之前的AVL树、平衡二叉搜索树博客中有描述，这里不在赘述。
3.1 节点设计
基于二叉排序树结点，增加color属性。
private static class RBNode<E> extends Node<E>{
boolean color = RED;
public RBNode(E element,Node<E> parent){
super(element,parent);
}
}
3.2 类设计
public class RBTree<E> extends BBSTree<E> {
private static final boolean RED = false;
private static final boolean BLACK = true;
public RBTree(){
this(null);
}
public RBTree(Comparator<E> comparator){
super(comparator);
}
/**
* 将节点染成对应的颜色
* @param node
* @param color
* @return
*/
private Node<E> color(Node<E> node,boolean color){
if(node == null){
return node;
}
((RBNode<E>)node).color = color;
return node;
}
private Node<E> red(Node<E> node){
return color(node,RED);
}
private Node<E> black(Node<E> node){
return color(node,BLACK);
}
/**
* 查看某个节点的颜色
* @param node
* @return
*/
private boolean colorOf(Node<E> node){
//空节点默认为黑色
return node == null?BLACK:((RBNode<E>)node).color;
}
/**
* 是否为黑色节点
* @param node
* @return
*/
private boolean isBlack(Node<E> node){
return colorOf(node) == BLACK;
}
/**
* 是否为红色节点
* @param node
* @return
*/
private boolean isRed(Node<E> node){
return colorOf(node) == RED;
}
@Override
protected Node<E> createNode(E element,Node<E> parent) {
return new RBNode<>(element,parent);
}
}
3.3 添加后的调整
添加情况参考2.2。
@Override
protected void afterAdd(Node<E> node) {
Node<E> parent = node.parent;
//添加的是根结点
if(parent == null){
black(node);
return;
}
//添加的父结点是黑色
if(isBlack(parent)) return;
Node<E> uncle = parent.sibling();
Node<E> grand = parent.parent;
if(isRed(uncle)){ //B树上溢
black(parent);
black(uncle);
red(grand);
afterAdd(grand);
return;
}
//叔父结点不是红色的情况
if(parent.isLeftChild()){
if(node.isLeftChild()){ //LL
black(parent);
red(grand);
rotateRight(grand);
}else{ //LR
black(node);
red(grand);
red(parent);
rotateLeft(parent);
rotateRight(grand);
}
}else{
if(node.isRightChild()){ //RR
black(parent);
red(grand);
rotateLeft(grand);
}else{ //RL
black(node);
red(grand);
red(parent);
rotateRight(parent);
rotateLeft(grand);
}
}
}
3.4 删除后的调整
删除情况较为复杂，参考2.3的详细操作流程。
@Override
protected void afterRemove(Node<E> node,Node<E> replacement) {
//被删除的结点只会发生在最后一层，即使不是叶子结点也没关系
if(isRed(node)){
return;
}
//用于取代的node结点是红色，自身肯定不会是红色，因为不可能Double red
if(isRed(replacement)){
black(replacement);
return;
}
//来到这里一定是叶子结点
//删除的结点是黑色
Node<E> parent = node.parent; //parent没有断
if(parent == null){ //被删除的是根结点
return;
}
boolean left = parent.left == null || node.isLeftChild();
//由于在儿叉排序树中会断掉left或者right，则根据left或者right是否为空的情况判定自身为left或right
Node<E> sibling = left? parent.right : parent.left;
if(left){ //被删除的结点在左边，兄弟节点在右边，左右操作对称
if(isRed(sibling)){ //兄弟节点是红色，将其转换成兄弟节点是黑色的情况
black(sibling);
red(parent);
rotateLeft(parent);
sibling = parent.right;
}
//兄弟节点是黑色
if(isBlack(sibling.left) && isBlack(sibling.right)){ //空节点也是black
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if(parentBlack){ //父节点为黑，下溢
afterRemove(parent, null);
}
}else{ //兄弟节点至上有一个red
if(isBlack(sibling.right)){ //左边如果是Black，则为LR，则转换成LL的情况
rotateRight(sibling);
sibling = parent.right;
}
color(sibling,colorOf(parent));
black(parent);
black(sibling.right);
rotateLeft(parent);
}
}else{ //被删除结点在右边，兄弟节点在左边
if(isRed(sibling)){ //兄弟节点是红色，将其转换成兄弟节点是黑色的情况
black(sibling);
red(parent);
rotateRight(parent);
sibling = parent.left;
}
//兄弟节点是黑色
if(isBlack(sibling.left) && isBlack(sibling.right)){ //空节点也是black
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if(parentBlack){ //父节点为黑，下溢
afterRemove(parent, null);
}
}else{ //兄弟节点至上有一个red
if(isBlack(sibling.left)){ //左边如果是Black，则为LR，则转换成LL的情况
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling,colorOf(parent));
black(parent);
black(sibling.left);
rotateRight(parent);
}
}
}
4 对比AVL树
- 红黑树保证最长的路径不会是最短路径的2倍,其最短路径为B树路径
- AVL树较平衡,最长最短路径长度差不大于1
- AVL添加元素旋转操作O(1),删除元素旋转操作O(logn)
- 红黑树添加元素和删除元素的旋转操作次数均为O(1)
- AVL树用于查找多增删少的场景
- 红黑树多用于经常需要动态增删元素的场景
5 应用场景
- Java中的TreeMap、TreeSet
- 有序无重树，可用于数据去重
- 数据有序情况下，数据搜索、插入、删除时间复杂度优于链表