[置顶] 数据结构之红黑树

上一节我们自己简单实现了一棵二叉查找树（数据结构之二叉查找树），虽然理论上二叉查找树的搜索时间是Olngn和树高成正比，但是实际上二叉查找树的平衡性并不理想，因此后面又出来了平衡二叉树，红黑树就是一种平衡的二叉查找树，先来看下什么是二叉查找树，对应我们熟悉的二分法查找，二叉查找树非常类似，二叉查找树的定义如下：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； 

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； 

（3）左、右子树也分别为二叉排序树；

以上摘自百度。下面就是一颗二叉查找树：

针对二叉查找树，树的深度并不固定，也就是不同的元素插入顺序会产生不同的二叉查找树，比如最坏的情况会产生下面的树：

这哪是二叉树嘛，这不就是个链表，没错，最坏的情况会变成一个单向的链表，因此后来又发展出了平衡二叉树，比如AVL，红黑树都是一种平衡二叉树。差不多所有的平衡二叉树都是靠旋转的规则来维持整个树的结构的，红黑树也不例外（为了遵循红黑树的定义，有时候还需要改变节点的颜色），下面就来看下红黑树的定义吧。

1. 每个结点或者为黑色或者为红色。 

2. 根结点为黑色。 
       3. 每个叶结点(实际上就是NLL指针)都是黑色的（这里值得讲一下，如果一个节点没有左右孩子，我们把它的左右孩子都看成是叶节点，而它们的颜色是黑色的，这一点很关键因为它能保证红黑树的平衡性）。 
       4. 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）。 
       5. 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。 

记住上面的5个性质，后面对树的操作会经常用到。为了防止忘记，在详细解释一下，第一点，每个节点为黑色或者红色，很简单。第二点，根节点为黑色，也很简单。第三点，每个叶节点都是黑色。看下面的一个例子：

上面左图，依次看每个性质，除了第三条，1满足，2满足，4满足，5子孙叶节点图中只有35和99，从62到它俩包含的黑色节点都为2（不包括黑色的根节点）。抛开第三条上图是一棵红黑树，但是这个棵树的平衡性却不敢恭维。8个节点的树高竟然是4，理论上应该为3。那我们再加上第三条来看下上面这棵树，第三条规定如果节点没有左右孩子则孩子置为NIL，且为黑色，如下图：

这样图中的子孙叶节点就变成了8个，但是从根节点到这8个叶节点，黑色节点的数目就不同了，因此上面的数实际上不是一棵红黑树。这里的子节点其实是我们认为设置的哨兵角色，不存储数据，为什么原则黑色道理也很明显。而它们也有专业的名字叫做外节点，存储数据的节点叫做内节点，为了方便画图后面这些外节点就不画出来了。

红黑树有很好的平衡性，最坏情况下也不会有一条路径是另一条路径的两倍（假设一条路径全是黑色节点，另一条路径是黑红相间），但实际上这种情况出现的概率非常小，因此红黑树的查找效率平均情况下要比普通的二叉查找树要好。

构造红黑树的过程其实就是针对不同的情况来选择是左旋还是右旋是否改变节点的颜色。

同样类似二叉查找树，删除的过程远比新增困难，那我们就从简单的做起，先来实现红黑树的insert操作。

每一个新增的节点都被当做红色节点来处理，这样处理的理由也很简单，新增有可能会破坏树的结构，因此新增的原则是尽可能少得去破坏红黑树的结构，保持该树的红黑特性，新增黑色节点肯定是会违反性质5，但是新增红色节点不会改变路径的黑色节点树，只是有可能违反性质4。

看完新增的第一条原则后，再来看下如果违反了性质，该怎么去修正，旋转！什么是旋转，看下算法导论给出的例子：

先不考虑颜色属性，看一下左旋，旋转就是交换两个节点的位置，但是再交换位置的过程中，肯定不能违反二叉查找树的特性，看左边的图，X是一个其右节点不为空（有内节点）的任意节点，Y的值比X大，当Y成为X的父节点的时候，很明显X需要成为Y的左节点，图中X左子树保持不变，Y的右子树保持不变，需要改变的是Y的左节点变成X的右节点，同理右旋转就不做解释了。下面给出左旋和右旋的代码：

/**
 * 左旋，并且x有右孩子
 * x的左孩子不变，y的右孩子不变
 * @param x
 */
public void leftRotate(Node x)
{
//y是x的右节点
Node y = x.right;

//设置x的右节点
x.right = y.left;
y.left.parent = x;

//设置y的父节点
y.parent = x.parent;

//如果x是根节点
if(x.parent == NIL)
{
root = y;
}
//如果x是左节点
else if (x == x.parent.left)
{

//设置y为父节点的左孩子
x.parent.left = y;
}
else
{
//设置y为父节点的右孩子
x.parent.right = y;
}

//设置x为y的左孩子
y.left = x;
x.parent = y;
}

/**
 * 右旋，并且y有左孩子
 * y的右孩子不变，x的左孩子不变
 * @param x
 */
public void rightRotate(Node y)
{
//x是y的左节点
Node x = y.left;

//设置y的左节点
y.left = x.right;
x.right.parent = y;

//设置x的父节点
x.parent = y.parent;

//如果y是根节点
if(y.parent == NIL)
{
root = x;
}
//如果y是右节点
else if (y == y.parent.right)
{

//设置x为父节点的右孩子
y.parent.right = x;
}
else
{
//设置x为父节点的左孩子
y.parent.left = x;
}

//设置y为x的右孩子
x.right = y;
y.parent = x;
}

新增过程中，可能会违反2和4性质，且2只会违反一次，如果违反性质四，需要分六种情况来分析，但实际上因为左右对称，只有三种情况，下面就以新增节点的父节点是其祖父节点的左孩子来分别看下这三种情况，第一种：

图中n代表新增节点，p代表其父节点，g代表其祖父节点，u代表其叔父节点，如果n的父节点为黑色我们不需要关注，如果p为红色我们需要进行调整，如果u也为红色，因为无论怎么旋转都会有红红出现，所以需要做改变颜色的操作，首先肯定的是不能将n图黑，这会违反性质5，因此需要将p和u涂黑，但这也会违反性质5，但是我们可以将g涂红，因为上到p和u节点必经过g，所以此时的操作并不违反性质5，但是可能会违反性质4，因此需要以g为新节点循环此过程。

分析完情况一再来分析情况二，叔父节点是黑色且n为p的右节点，如下图中间的图片:

此时可以通过一次左旋，将第二种情况转变为第三种情况，即n为p的左节点，第三种情况如下图：

将p和g的颜色交换，然后做右旋即可得到一棵红黑树，因为我们从未改变从p顶点出发到叶节点的黑色节点个数。

上面就是插入的情况，实际p为g的右节点也还有三种类似的情况，就不一一画图了，红黑树的插入可以参考二叉查找树的插入，大体只是多了NIL节点和修正步骤：

/**
 * 首先依照二叉查找树的插入过程
 * @param value
 */
public void insert(int value)
{
Node newNode = null;
if(null == root)
{
newNode = root = new Node(NIL,NIL,NIL,value,false);
}
else
{
newNode = insertNotRoot(value);
}
//由于插入的是红色节点，因此整个过程，只可能为违反2和4，且2只会违反一次
fixRBT(newNode);
}

/**
 * 新插入节点有可能破话红黑树的结构，此方法为调整现有的树，使之始终是一棵红黑树
 * @param newNode
 */
private void fixRBT(Node newNode) {

//当新增节点的父节点是红色时，会违反性质4，并且新增节点肯定有祖父节点且为黑（红色节点不会是根节点）
while(newNode.parent.isBlack == false)
{
//里面需要面对不同的情况做处理，有六种情况，但因为左右对称的情况，实际只需要分析三种情况，先给出新节点的父节点是祖父节点的左节点的场景
if(newNode.parent == newNode.parent.parent.left)
{
Node parent = newNode.parent;
//叔父节点
Node uncle = newNode.parent.parent.right;
//如果叔父是红色，将p和u涂黑，g涂红
if(uncle.isBlack == false)
{
parent.setBlack(true);
uncle.setBlack(true);
parent.parent.setBlack(false);
//以祖父节点为新增节点继续循环
newNode = parent.parent;
}
//否则叔父节点时黑色节点，且新增节点是父节点的右节点
else if(newNode == newNode.parent.right)
{
newNode = newNode.parent;
//以新增节点的父节点为轴左旋，即可变成情况三
leftRotate(newNode);

}
//否则叔父节点为黑色，且新增节点时父节点的左节点
else
{
//设置父节点为黑色
newNode.parent.setBlack(true);
//设置祖父节点为红色
newNode.parent.parent.setBlack(false);
//p,g为轴做右旋
rightRotate(newNode.parent.parent);
}
}
//否则为对称情况，新节点的父节点是祖父节点的右节点
else
{
Node parent = newNode.parent;
//叔父节点
Node uncle = newNode.parent.parent.left;
//如果叔父是红色，将p和u涂黑，g涂红
if(uncle.isBlack == false)
{
parent.setBlack(true);
uncle.setBlack(true);
parent.parent.setBlack(false);
//以祖父节点为新增节点继续循环
newNode = parent.parent;
}
//否则叔父节点时黑色节点，且新增节点是父节点的左节点
else if(newNode == newNode.parent.left)
{
//父节点经过旋转会占据到现在新增节点的位置
newNode = newNode.parent;
//以新增节点和父节点为轴右旋，即可变成情况三
rightRotate(newNode);

}
//否则叔父节点为黑色，且新增节点时父节点的右节点
else
{
//设置父节点为黑色
newNode.parent.setBlack(true);
//设置祖父节点为红色
newNode.parent.parent.setBlack(false);
//p,g为轴左旋
leftRotate(newNode.parent.parent);
}
}
}
//否则父节点是黑色，可能插入的是根节点，设置根节点为黑色，避免遗漏该情况
root.setBlack(true);
}

private Node insertNotRoot(int value) {
Node cur = root;
Node parent = root;
while(null != cur)
{
parent = cur;
//插入左子树
if(value < cur.value)
{
if(NIL == cur.left)
{
Node n = new Node(NIL,NIL,parent,value,false);
parent.left = n;
return n;
}
cur = cur.left;
}
//插入右子树
else
{
if(NIL == cur.right)
{
Node n = new Node(NIL,NIL,parent,value,false);
parent.right = n;
return n;
}
cur = cur.right;
}
}

return null;
}

/**
 * 中序遍历
 * @param n
 */
public void midOrderWalk(Node n)
{
if(null == n || NIL == n)
{
return;
}
midOrderWalk(n.left);
System.out.println(n.value);
midOrderWalk(n.right);
}

以上就是红黑树的插入过程，还附带一个中序遍历。假设一次插入1 6 8 11 13 15 17 22 25 27这十个节点，可以得到如下的一棵红黑树：

从根节点到叶子节点（NIL未画出）的黑色节点数全部为3，最长的一条路径是最右一条。可以看出平衡性比二叉查找树（向右下斜的一条线）好多了。

红黑树的插入比二叉查找树稍微复杂一些，但是红黑树的删除比二叉查找树要复杂的多。但基本上也是基于二叉查找树的变形，因此，在写删除的操作前，还需要给出前驱、后继、最大、最小的代码。这几个方法的代码这里就不贴出来了，因为和二叉查找树的非常类似只是null的地方换成NIL。

直接分析删除的可能性：

熟悉二叉查找树的同学可能会知道，我们再删除某个节点的时候，实际上从逻辑上来理解，该节点左右和父指针有可能不会变，而是去删除一个实际的节点，将该节点的值赋给我们要删的那个节点，从而从理论上达到删除某个节点的效果。

如上图，我们删除的是47节点，实际上从结构上来看，删除的是37节点，37是47的前驱节点。因此理解实际被删除的节点很重要。因为该节点结合红黑树的性质能得到以下几个推理：

1.真正被删除的节点y子节点或者全为NIL或者一个为NIL一个为非NIL节点，没有第三种情况

2.基于推理1，如果y有一个非NIL节点，则该节点肯定为红且该节点孩子节点都为NIL。

3.基于推理2，如果y有非NIL节点，则y肯定是黑色节点，反过来如果y是红色节点，则y的两个孩子肯定是NIL。

因此我们删除的过程也要基于上面的三个推理来做不同的处理，这里将x当成y的孩子节点：

1.假设要删除的是红色节点y，则可以想象，不会对5个性质造成影响，y不会是根节点，删除y不会影响路径黑色节点的个数，更不会存两个红色节点，因此可以不做考虑，直接按照二叉查找树的删除动作来删除即可。如下图经过y或者不经过y对于节点的黑色个数不影响。

2.假设要删除的是黑色节点，则y可能有一个红色节点的孩子（不管是左还是右），如果有孩子则为红，且孩子节点是叶子节点。删除y则肯定会改变路径黑色节点的个数，或者导致红色节点为根。此时将y删除，将x移动到y的位置且变为黑色，则仍然不影响红黑树的任何性质，实际删除操作就是将x替代y，所以不需要做特殊处理。

3.假设要删除的是黑色节点，且y没有孩子则情况实际上要复杂不少。

将y节点删除肯定会违反性质5，经过y的某条路径黑色节点数将少一，因此我们需要针对这种情况做旋转或者修改颜色的属性。这里根据算法导论引入一个概念，双重黑色，即将y的原来的某个节点想象成算作两个黑色，因此，需要将该节点x向上移动，直到找到合适的位置。我们将x的兄弟节点称为w，则需要根据w的情况做不同的处理。

x的兄弟节点w如果为红色，可知x和w的父节点p肯定为黑色，而且w有孩子节点并且全为黑。（情况一）如下图：

此时逻辑上假设x是双黑，因此这棵子树是理论上平衡的，我们需要做的是以x为起点，逐渐向上将x的一重黑色转移，可以想象转移的过程中需要保证树的平衡，假设该重黑色一直被转移到root节点，则直接不做任何操作即可，因为从root的黑色数不影响整棵树的平衡。针对第一种情况，首先将p和w的颜色交换，然后对p做一次左旋。变成下图，整棵树仍然是平横的，其实这也是第二种情况：

可以将上面的情况看做是x的兄弟节点节点w（a）为黑色的情况。其父亲节点p可红可黑，而w的两个孩子全是黑如下图（情况二）：

此时x为双重黑色，w为黑色，我们可以考虑将x的双重颜色去掉一重，将x变为黑色，w变为红色。但此时少了一个黑色，因此考虑将x中的双重颜色上移到父节点，此时父节点变成了双重黑色，如果p为根，则把p的一重黑色去掉即可结束，否则以父节点为x进行while循环，注意如果情况二是由情况一演变而来，此时的新x（p）颜色为红黑，但x的color我们仍然当做红色。直接将x（p）变为黑色流程即可结束。但是如果w的节点不为全黑，而是，w左是红，右是黑。如下图（情况三）：

此时可以交换w和其左孩子的颜色，然后w-a为轴做右旋。变成下图：

此时变为情况四，x的兄弟节点w只有一个右节点为红色，如下图（情况四）：

其中w的左节点的颜色可以为红可为黑（NIL），右节点为红。交换p和w的颜色，然后以p-w为轴左旋，变为下图：

此时x为双重黑色，且左路径加了p为黑色，因此可以将x的双重颜色右移到w的右孩子节点a上。变成如下图：

其实就是将a的颜色变为黑。这里的w可为黑，可为红。

完整的删除代码如下：

public void delete(int value)
{
Node n = searchNode(value);
if(null != n)
{
delete(n);
}
}

/**
 * 删除某个节点
 * 我们删除某个节点，实际上并不一定非要删除它，可以使其他的节点去替代它被删除
 * 因此真正被删除的节点并不一定是n
 * @param n
 */
public Node delete(Node n)
{
//y是真正待删除的元素
Node y = null;
Node x = null;
//如果没有孩子或者有一个孩子
if(NIL == n.left || NIL == n.right)
{
y = n;
}
else
{
//如果n有两个孩子，则另待删除的元素为n的后继，并且n的后继肯定不会有两个孩子节点
y = successor(n);
}
//综上所述，真正被删除的节点y肯定不会有两个孩子节点
//如果y有左孩子
if(y.left != NIL)
{
//x为y的左孩子
x = y.left;
}
else
{
//此处x可能为NIL
x = y.right;
}

//将y删除
x.parent = y.parent;

//如果y是根节点
if(y.parent == NIL)
{
root = x;
}
else if(y == y.parent.left)
{
//y不是根节点且是父节点的左孩子
y.parent.left = x;

}
else
{
//y不是根节点且是父节点的右孩子
y.parent.right = x;
}

//此时已经将y完全删除了，但是要删除的是n节点，因此需要将y的值付给n节点，来达到删除n的目的
if(y.value != n.value)
{
//此时真正将n删除，但实际上n的结构并未改变，而是原来y的结构被改变了
n.value = y.value;
}

//如果y是黑色的需要调整，为红色不需要改变
if(y.isBlack)
{
//此处的x只有两种情况，x肯定是y的唯一的孩子，或者为NIL节点（黑色）
fixDeleteRB(x);
}
return y;
}

/**
 * 当删除的节点为黑色的时候，调整当前树的结构
 * @param x
 */
private void fixDeleteRB(Node x) {
//x节点的兄弟节点
Node w = null;
//当x不是根节点，且x是黑色的时候，(x是NIL节点)
while(x != root && x.isBlack)
{
//如果x是父节点的左节点
if(x == x.parent.left)
{
w = x.parent.right;
//如果w是红色节点
if(!w.isBlack)
{
//交换w和父节点的颜色
w.setBlack(true);
x.parent.setBlack(false);
leftRotate(x.parent);

//旋转后前父节点的右节点为兄弟节点，此时将第一种情况变为后面的2,3,4情况中的一种
w = x.parent.right;
}
//如果w的两个孩子是黑色
if(w.left.isBlack && w.right.isBlack)
{
//将w置为红色
w.setBlack(false);

x = x.parent;
}
//w的右孩子是黑色
else if(w.right.isBlack)
{
w.left.setBlack(true);
w.setBlack(false);
rightRotate(w);
//重新设置x的兄弟节点
w = x.parent.right;
}
else
{
//交换w和p的颜色,其中w为黑色， p不一定
w.setBlack(x.parent.isBlack);
x.parent.setBlack(true);
w.right.setBlack(true);
//p-w左旋，w的右节点仍还是w的右节点
leftRotate(x.parent);
//将x节点重置为root节点，跳出循环
x = root;
}
}
//x是父节点的右节点
else
{
//w是左节点
w = x.parent.left;
//如果w是红色节点
if(!w.isBlack)
{
//交换w和父节点的颜色
w.setBlack(true);
x.parent.setBlack(false);
rightRotate(x.parent);

//旋转后前父节点的左节点为兄弟节点，此时将第一种情况变为后面的2,3,4情况中的一种
w = x.parent.left;
}
//如果w的两个孩子是黑色
if(w.left.isBlack && w.right.isBlack)
{
//将w置为红色
w.setBlack(false);

x = x.parent;
}
//w的右孩子是黑色
else if(w.left.isBlack)
{
w.right.setBlack(true);
w.setBlack(false);
leftRotate(w);
//重新设置x的兄弟节点
w = x.parent.left;
}
else
{
//交换w和p的颜色,其中w为黑色， p不一定
w.setBlack(x.parent.isBlack);
x.parent.setBlack(true);
w.left.setBlack(true);
//p-w右旋，w的左节点仍还是w的左节点
rightRotate(x.parent);
//将x节点重置为root节点，跳出循环
x = root;
}
}
}
x.setBlack(true);
}

终于分析完了，后面有机会再来看看jdk中关于红黑树的实现，TreeMap。实际上思路差不多，但是TreeMap内部的类非常多，代码大概也2000多行，不过有了这篇的基础，再去看TreeMap相信会轻松不少，毕竟最复杂的部门我们已经自己实现一遍了，TreeMap中用到了比较器。