红黑树
上一篇我们介绍了二叉搜索树，二叉搜索树对于某个节点而言，其左子树的节点关键值都小于该节点关键值，
右子树的所有节点关键值都大于该节点关键值。二叉搜索树作为一种数据结构，其查找、插入和删除操作的时间复
杂度都为O(logn),底数为2。但是我们说这个时间复杂度是在平衡的二叉搜索树上体现的，也就是如果插入的数据是
随机的，则效率很高，但是如果插入的数据是有序的，比如从小到大的顺序【10,20,30,40,50】插入到二叉搜索树
中： 从大到小就是全部在左边，这和链表没有任何区别了，这种情况下查找的时间复杂度为O(N)，而不是O(logN)。当
然这是在最不平衡的条件下，实际情况下，二叉搜索树的效率应该在O(N)和O(logN)之间，这取决于树的不平衡程
度。
那么为了能够以较快的时间O(logN)来搜索一棵树，我们需要保证树总是平衡的（或者大部分是平衡的），也
就是说每个节点的左子树节点个数和右子树节点个数尽量相等。红-黑树的就是这样的一棵平衡树，对一个要插入
的数据项（删除也是），插入例程要检查会不会破坏树的特征，如果破坏了，程序就会进行纠正，根据需要改变树
的结构，从而保持树的平衡。
1.红黑树的特征
有如下两个特征：
- 节点都有颜色；
- 在插入和删除的过程中，要遵循保持这些颜色的不同排列规则。
第一个很好理解，在红-黑树中，每个节点的颜色或者是黑色或者是红色的。当然也可以是任意别的两种颜
色，这里的颜色用于标记，我们可以在节点类Node中增加一个boolean型变量isRed，以此来表示颜色的信息。
第二点，在插入或者删除一个节点时，必须要遵守的规则称为红-黑规则：
- 每个节点不是红色就是黑色的；
- 根节点总是黑色的；
- 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）,(也就是从每个叶子到根的所有路径上不能有两个连续的红色节点)；
- 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。
从根节点到叶节点的路径上的黑色节点的数目称为黑色高度，规则 4 另一种表示就是从根到叶节点路径上的黑色高度必须相同。
注意：新插入的节点颜色总是红色的，这是因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能
性更小，原因是插入黑色节点总会改变黑色高度（违背规则4），但是插入红色节点只有一半的机会会违背规则
3（因为父节点是黑色的没事，父节点是红色的就违背规则3）。另外违背规则3比违背规则4要更容易修正。当插
入一个新的节点时，可能会破坏这种平衡性，那么红-黑树是如何修正的呢？
2.红黑树的自我修正
红-黑树主要通过三种方式对平衡进行修正，改变节点颜色、左旋和右旋。
2.1改变节点颜色
/**
* b=black(黑色) r=red(红色)
* b50
* / \
* r25 r60
* /
* r15(要插入的节点，红色违反规则3，黑色违反规则4)
*
*
* b50
* / \
* b25 b60
* /
* r15
*
*
*/
新插入的节点为15，一般新插入颜色都为红色，那么我们发现直接插入会违反规则3，改为黑色却发现违反规则
4。这时候我们将其父节点颜色改为黑色，父节点的兄弟节点颜色也改为黑色。通常其祖父节点50颜色会由黑色变
为红色，但是由于50是根节点，所以我们这里不能改变根节点颜色。
2.2 右旋
首先要说明的是节点本身是不会旋转的，旋转改变的是节点之间的关系，选择一个节点作为旋转的顶端，如果做
一次右旋，这个顶端节点会向下和向右移动到它右子节点的位置，它的左子节点会上移到它原来的位置。右旋的顶
端节点必须要有左子节点。
2.3 左旋
左旋的顶端节点必须要有右子节点。
注意：我们改变颜色也是为了帮助我们判断何时执行什么旋转，而旋转是为了保证树的平衡。光改变节点颜色
是不能起到任何作用的，旋转才是关键的操作，在新增节点或者删除节点之后，可能会破坏二叉树的平衡，那么何
时执行旋转以及执行什么旋转，这是我们需要重点关注的。
3.左旋和右旋代码
- 节点类
节点类和二叉树的节点类差不多，只不过在其基础上增加了一个 boolean 类型的变量来表示节点的颜色。
public class RBNode<T extends Comparable<T>> {
boolean color;//颜色(true:红 false:黑)
T key;//关键值
RBNode<T> left;//左子节点
RBNode<T> right;//右子节点
RBNode<T> parent;//父节点
public RBNode(boolean color,T key,RBNode<T> parent,RBNode<T> left,RBNode<T> right){
this.color = color;
this.key = key;
this.parent = parent;
this.left = left;
this.right = right;
}
//获得节点的关键值
public T getKey(){
return key;
}
//打印节点的关键值和颜色信息
public String toString(){
return ""+key+(this.color == true ? "R":"B");
}
}
- 左旋的具体实现
/*************对红黑树节点x进行左旋操作 ******************/
/*
* 左旋示意图：对节点x进行左旋
* p p
* / /
* x y
* / \ / \
* lx y - - - - - ‐‐> x ry
* / \ / \
* ly ry lx ly
* 左旋做了三件事：
* 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
* 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
* 3. 将y的左子节点设为x，将x的父节点设为y
*/
private void leftRotate(RBNode<T> x){
//1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
RBNode<T> y = x.right;
x.right = y.left;
if(y.left != null){
y.left.parent = x;
}
//2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
y.parent = x.parent;
if(x.parent == null){
this.root = y;//如果x的父节点为空(即x为根节点)，则将y设为根节点
}else{
if(x == x.parent.left){//如果x是左子节点
x.parent.left = y;//则也将y设为左子节点
}else{
x.parent.right = y;//否则将y设为右子节点
}
}
//3. 将y的左子节点设为x，将x的父节点设为y
y.left = x;
x.parent = y;
}
- 右旋的具体实现
/*************对红黑树节点y进行右旋操作 ******************/
/*
* 左旋示意图：对节点y进行右旋
* p p
* / /
* y x
* / \ / \
* x ry ‐‐> lx y
* / \ / \
* lx rx rx ry
* 右旋做了三件事：
* 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
* 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
* 3. 将x的右子节点设为y，将y的父节点设为x
*/
private void rightRotate(RBNode<T> y){
//1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
RBNode<T> x = y.left;
y.left = x.right;
if(x.right != null){
x.right.parent = y;
}
//2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
x.parent = y.parent;
if(y.parent == null){
this.root = x;//如果y的父节点为空(即y为根节点)，则旋转后将x设为根节点
}else{
if(y == y.parent.left){//如果y是左子节点
y.parent.left = x;//则将x也设置为左子节点
}else{
y.parent.right = x;//否则将x设置为右子节点
}
}
//3. 将x的左子节点设为y，将y的父节点设为y
x.right = y;
y.parent = x;
}
4.插入操作
和二叉树的插入操作一样，都是得先找到插入的位置，然后再将节点插入。先看看插入的前段代码：
/*********************** 向红黑树中插入节点 **********************/
public void insert(T key){
RBNode<T> node = new RBNode<T>(true, key, null, null, null);
if(node != null){
insert(node);
}
}
public void insert(RBNode<T> node) {
RBNode<T> current = null;//表示最后node的父节点
RBNode<T> x = this.root;//用来向下搜索
//1.找到插入位置
while (x != null) {
current = x;
int cmp = node.key.compareTo(x.key);
if (cmp < 0) {
x = x.left;
} else {
x = x.right;
}
}
node.parent = current;//找到了插入的位置，将当前current作为node的父节点
//2.接下来判断node是左子节点还是右子节点
if (current != null) {
int cmp = node.key.compareTo(current.key);
if (cmp < 0) {
current.left = node;
} else {
current.right = node;
}
} else {
this.root = node;
}
//3.利用旋转操作将其修正为一颗红黑树
insertFixUp(node);
}
这与二叉搜索树中实现的思路一样，这里不再赘述，主要看看方法里面最后一步insertFixUp(node)操作。因
为插入后可能会导致树的不平衡，insertFixUp(node) 方法里主要是分情况讨论，分析何时变色，何时左旋，何时
右旋。我们先从理论上分析具体的情况，然后再看insertFixUp(node) 的具体实现。
如果是第一次插入，由于原树为空，所以只会违反红-黑树的规则2，所以只要把根节点涂黑即可；
如果插入节点的父节点是黑色的，那不会违背红-黑树的规则，什么也不需要做；
但是遇到如下三种情况，我们就要开始变色和旋转了：
- 插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色。
- 插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的右子节点。
- 插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的左子节点。
下面我们挨个分析这三种情况都需要如何操作，然后给出实现代码。
在下面的讨论中，使用N,P,G,U表示关联的节点。
- N(now)表示当前节点，
- P(parent)表示N的父节点，
- U(uncle)表示N的叔叔节点，
- G(grandfather)表示N的祖父节点，也就是P和U的父节点。
对于情况1：插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色。此时，肯定存在祖父节
点，但是不知道父节点是其左子节点还是右子节点，但是由于对称性，我们只要讨论出一边的情况，另一种情况自
然也与之对应。这里考虑父节点是其祖父节点的左子节点的情况，如下左图所示：
/**
*b=black(黑色) r=red(红色)
*情况1
* b11
* / \
* r2 b14
* / \ /
* b1 b7 r15
* / \
* r5 r8
* /
* r4(N:当前节点)
*
*/
对于这种情况，我们要做的操作有：将当前节点(4) 的父节点(5) 和叔叔节点(8) 涂黑，将祖父节点(7)涂红,变成了下图所示的情况。
再将当前节点指向其祖父节点，再次从新的当前节点开始算法（具体看下面的步骤）。
这样下图就变成情况2了。
/**
*b=black(黑色) r=red(红色)
*情况2
* b11
* / \
* / \
* r2 b14
* / \ /
* b1 r7(N) r15
* / \
* b5 b8
* /
* r4
*/
对于情况2：插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的右子节点。
我们要做的操作有：将当前节点(7)的父节点(2)作为新的节点，以新的当前节点为支点做左旋操作。完成后如下图所示，
这样下图就变成情况3了。
/**
*b=black(黑色) r=red(红色)
*情况3
* b11
* / \
* / \
* r7 b14
* / \ /
* / \ /
* r2(N) b8 r15
* / \
* b1 b5
* /
* r4
*/
对于情况3：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。
我们要做的操作有：将当前节点的父节点(7)涂黑，将祖父节点(11)涂红，在祖父节点为支点做右旋操作。最后把根节点涂黑，整个
红-黑树重新恢复了平衡，如下图所示。至此，插入操作完成！
/**
*b=black(黑色) r=red(红色)
*最终
* b7
* / \
* / \
* r2(N) r11
* / \ / \
* / \ / \
* b1 b5 b8 b14
* / /
* r4 r15
*
*/
我们可以看出，如果是从情况1开始发生的，必然会走完情况2和3，也就是说这是一整个流程，当然咯，实际
中可能不一定会从情况1发生，如果从情况2开始发生，那再走个情况3即可完成调整，如果直接只要调整情况3，
那么前两种情况均不需要调整了。故变色和旋转之间的先后关系可以表示为：变色->左旋->右旋。
至此，我们完成了全部的插入操作。下面我们看看insertFixUp方法中的具体实现（可以结合上面的分析图，
更加利与理解）：
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);//将根节点设置为黑色
}
其中一些使用的私有方法如下：
public class RBTree<T extends Comparable<T>> {
//表示根节点
private RBNode root;
//省略上面已贴出的方法
private void setRed(RBNode rbNode){
rbNode.color = true;
}
private void setBlack(RBNode rbNode){
rbNode.color = false;
}
private boolean isRed(RBNode rbNode){
return rbNode.color;
}
private RBNode parentOf(RBNode rbNode){
return rbNode.parent;
}
}
5.删除操作
上面探讨完了红-黑树的插入操作，接下来讨论删除，红-黑树的删除和二叉查找树的删除是一样的，只不过删除后
多了个平衡的修复而已。我们先来回忆一下二叉搜索树的删除：
- 如果待删除的节点没有子节点，那么直接删除即可。
- 如果待删除的节点只有一个子节点，那么直接删掉，并用其子节点去顶替它。
- 如果待删除的节点有两个子节点，这种情况比较复杂：首先找出它的后继节点，然后处理“后继节点”和“被删除节点的父节点”之间的关系，最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系。每一步中也会
有不同的情况。
实际上，删除过程太复杂了，很多情况下会采用在节点类中添加一个删除标记，并不是真正的删除节点。详细的删除我们这里不做讨论。
6.红黑树的效率
红黑树的查找、插入和删除时间复杂度都为O(log2N)，额外的开销是每个节点的存储空间都稍微增加了一点，因
为一个存储红黑树节点的颜色变量。插入和删除的时间要增加一个常数因子，因为要进行旋转，平均一次插入大约
需要一次旋转，因此插入的时间复杂度还是O(log2N),(时间复杂度的计算要省略常数)，但实际上比普通的二叉树是
要慢的。
大多数应用中，查找的次数比插入和删除的次数多，所以应用红黑树取代普通的二叉搜索树总体上不会有太多
的时间开销。而且红黑树的优点是对于有序数据的操作不会慢到O(N)的时间复杂度。
联系作者
微信公众号
xiaomingxiaola
（BossLiu）
QQ群
58726094
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 384276224@qq.com
