wen 红黑树——一种自平衡的二叉树 – touch
红黑树——一种自平衡的二叉树
一、红黑树简介
普通二叉树在数据不够均匀的情况下，可能导致左右子树高度会相差比较大，最坏情况下树的结构相当于一个链表，时间复杂度为n。为了使二叉树在最坏情况下也能有log(n)的性能，需要对二叉树进行平衡操作，相应的算法有很多，红黑树就是其中一种算法。红黑树是一种自平衡的二叉搜索树，它每一个节点有一个存储位表示颜色。通过对路径上的颜色约束，红黑树保证没有一条路径比其他路径长2倍，因而是接近平衡的。相对于普通的二叉搜索树，红黑树在最坏的情况下保证插入和删除操作的时间复杂度是log(n)
一颗红黑树需要满足下列5条规则：
- 每一个节点是红色和黑色的一种
- 根节点是黑色的
- null节点是黑色，也就是所以的叶子节点都是黑色
- 红色节点不能相邻（也就是红色节点的孩子必定是黑色）
- 从任意一个节点到叶子节点（不包含这个节点），黑色节点的数量相同，这个规则也叫红黑树的黑高
红黑树的搜索与一般的搜索二叉树没有其他区别，主要的区别是插入和删除操作，因为这两个操作会修改二叉树结构，导致红黑树规则被破坏。红黑树通过变色、左旋、右旋来修复规则被破坏的情况，下面简单介绍一下这三个规则。
1、变色
变色，顾名思义就是改变红黑树的颜色，也就是红变黑，黑变红。变色作用的是单个节点，一些文章把变色总结成了复合操作其实是不对的，变色规则需要结合情况具体分析，死记不利于理解红黑树的（说不定还记不住）。实际上变色目的是改变节点路径上黑色数量，把一个节点变成黑色，可以增加这个节点路径上黑色节点的数量，反之则减少黑色节点的数量。
变色示意图：
2、左旋
某个节点左旋，这个节点的右孩子不能为空。把一个节点向左旋转，“右孩子”替换节点位置，把节点作为“右孩子”新左节点，“右孩子”的“左孩子”变成节点新的右孩子。规则有点绕，看一下示意图就明白了：
图中B是A的右孩子，提升B的位置，A作为B的左孩子，然后把C作为A的右孩子。左旋只会改变旋转节点右边的子树，不会改变节点的左子树，如图D相对于A的位置还是不变的。左旋的一个特性是会把右子树的高度变低，左子树变高。另一个特性是可以调换左右子树的元素。
3、右旋
某个节点右旋，这个节点的左孩子不能为空。把一个节点向右旋转，“左孩子”替换节点位置，把节点作为“左孩子”新右节点，“左孩子”的“右孩子”变成节点新的左孩子。示意图如下：
图中B是A的左孩子，提升B的位置，A作为B的右孩子，然后把C作为A的左孩子。右旋只会改变旋转节点左边的子树，不会改变节点的右子树，如图D相对于A的位置还是不变的。右旋的一个特性是会把左子树的高度变低，右子树变高。另一个特性是可以调换左右子树的元素。
二、红黑树的插入
1、叔叔节点
首先介绍一下叔叔节点，叔叔节点顾名思义就是父亲节点的兄弟。例如下面这个结构，C节点的父亲为B，叔叔节点为D：
2、新节点的颜色分析
首先可以证明插入的新节点一定是红节点。如果插入节点是黑节点，那么当插入第二个节点，规则5肯定无法满足了（例如从根节点到左右叶节点的黑高不一样）。由于插入黑色节点必然会破坏红黑树的规则，所以不如一开始插入红色节点高效，所以插入的节点需要是红节点。
如上图，插入的新节点0如果是黑色，会导致根节点5到叶子节点的距离不一致。此时只能把新节点0变回红色，同理多层节点情况下如果新节点是黑色也一定要执行变色或旋转才能修复规则
3、插入位置是根节点
如果插入的位置是根节点，则直接把这个节点变成黑色，即可满足红黑树所有性质
4、插入位置的父亲节点是黑色
在一个黑色节点的下方插入一个红色节点，由于红色节点不提供黑色数量，此时直接插入新节点即可。
如图，在一个黑色节点（5）下方插入一个红色节点，不会破坏红黑树任何规则
5、插入位置的父节点是红色
如果插入节点的父亲节点是红色，那么很明显此时红黑树不满足规则4（红色节点不能相邻），此时就需要通过变色/旋转操作来修复破坏的红黑树规则。由于规则4（红色节点不能相邻）的约束，因为插入前是满足红黑树规则的，所以此时爷爷节点必定是黑色。所以此时只有两种情况：
- 节点的叔叔节点是红节点
- 节点的叔叔节点是黑节点
5.1、节点的叔叔节点是红节点
已知插入前父亲节点和叔叔节点是红色，那么根据红黑树规则，爷爷节点必定是黑色。此时只要把爷爷节点的黑色分给父亲和叔叔就行了，也就是把父亲节点和叔叔节点变成黑色，爷爷节点变成红色。如下图所示：
如图，插入了一个新节点15，破坏了规则4（红色节点不能相邻）。因为叔叔节点0是红色的，可以把爷爷节点5的颜色分给叔叔节点0和父亲节点10。由于爷爷节点的左右子树同时增加的1的黑色，所以此时规则5也可以被满足。
但是由于我们不知道爷爷节点5的父亲是什么颜色，我们需要把检查的标记定位到爷爷节点5上，再次检查红黑树是否因为此次变色操作破坏了其他规则。
5.2、节点的叔叔节点是黑节点
如果叔叔节点是黑色，所以通过拆分爷爷节点颜色来修复规则（拆分颜色后叔叔相当于有2层黑）。那可不可以把新节点直接换到叔叔节点下呢？答案是不可以，因为节点的不光要满足红黑树的规则，也要满足搜索二叉树的规则，我们不可以随便交换节点的位置，否则搜索的时候就会出问题。虽然直接调换位置不行，但是可以通过旋转来间接调换位置。
以节点插入的子树是其爷爷的右子树为例，此时插入的新节点15：
5.2.1是插入后红黑树情况、5.2.2是以爷爷节点5左旋后红黑树情况、5.2.2是变色后红黑树情况
因为要换一个节点到另一边，所以对爷爷节点5进行左旋，然而左旋会使叔叔节点的子树的黑色数量+1，父亲节点的子树黑色数量少1，虽然修复了规则4，但是又新破坏了规则5，所以这时需要一个变色操作来修复再次被破坏的规则5。很显然旋转后只需要之前爷爷节点5变红，父亲节点10变黑就能修复规则5。
但是假设插入的节点值是7，直接左旋会把新节点7也带到左子树，所以此时先要以父亲节点进行一次右旋，转换为图5.2.1中类似的情况。
然后再以爷爷节点5进行左旋和变色即可恢复规则
同理，如果节点插入的子树是其爷爷的左子树也是类似的情况，这里就不多赘述。
6、插入操作伪代码
//node的属性color、left、right，parent分别为节点的颜色、节点的左子节点、节点的右子节点、节点的父亲
//枚举RED为红，BLACK为黑
//leftRotate为左旋函数
//rightRotate为左旋函数
//Root为根节点的指针
//fixInsertRule的node参数为新插入的节点
fixInsertRule(node){
while(node != ROOT and node.parent.color == RED){
grandparent = node.parent.parent//爷爷节点，由于父亲节点是红色，爷爷节点颜色必定是黑色
if(node.parent == grandparent.right){
uncle = grandparent.left;//叔叔节点
if(uncle.color == RED){//叔叔节点是红色
uncle.color = BLACK;
node.parent.color = BLACK;
grandparent.color = RED;
//把检查节点定位到爷爷节点上，继续下一次的循环
node = grandparent;
}else{//叔叔节点是黑色
if(node == node.parent.left){
//先要以父亲进行一次右旋
//这里需要注意的是右旋后原来的父亲变成孩子，原来的孩子变成父亲
//所以爷爷节点和叔叔节点还是不变的
node = node.parent;
rightRotate(node);
}
//为了方便，先变颜色
node.parent.color = BLACK;
grandparent.color = RED;
//以爷爷节点左旋
leftRotate(grandparent);
}
}else{
//节点位置是爷爷节点的左子树的情况，这里省略...
}
}
//旋转和变色后可能会导致根节点会变红，重新设置根节点为黑色即可
ROOT.color = BLACK;
}
三、红黑树的删除
相对于插入操作，二叉树的节点删除的方式有很多种。比如下面这颗树，需要删除节点20。既可以使用节点10来替换被删除的20节点，然后把节点30连接到左子树最大的节点后面。也可以使用节点30来替换被删除节点，然后把节点10连接到右子树最小的节点后面
但是这两种方案都不太适合红黑树，红黑树在插入时会平衡左右子树的高度，上面两种方案会让删除节点左右子树变成极大的不平衡，所以红黑树的删除需要找一个影响结构最小的删除方案。
使用后继节点替代被删除节点是一个很好的方案（前继节点也行，本文以后继节点进行分析），由于是后继节点，那么后继节点最多只会有一个右孩子，使用后继节点替换删除节点，并不会影响前继节点的子树。所以只需要对后继节点右子树进行向上检查即可修复规则。
使用后继节点的删除方案。只会影响后继节点所在的子树。
使用后继节点替换删除节点，只需要把后继节点的颜色变成和删除节点一样。然后从后继节点的右孩子开始检查红黑树是否满足。由于删除前是满足红黑树规则的，所以后继节点和后继右孩子的颜色只会有这几种情况。
- 后继节点是红色，后继右孩子是黑色。此时后继节点的父亲一定为黑
- 后继节点是黑色，后继右孩子是红色。后继节点的父亲的颜色不确定
- 后继节点是黑色，后继右孩子是黑色。后继节点的父亲的颜色不确定
1、后继节点是红色
因为后继节点是红色，说明后继右孩子必定是黑色，父亲节点必定也是黑色。使用一个黑色节点替换红色节点的位置，既不会破坏规则4，也不会破坏规则5。此时无需对树的结构进行修复。
2、后继节点是黑色，后继右孩子是红色
把后继右孩子变成黑色，即可满足规则5
3、后继节点是黑色，后继右孩子是黑色
因为后继右孩子本身是黑色，无法继续变黑，如果要满足规则5，需要后继右孩子具有2层的黑色属性才行。既然一个节点不能有2层黑色，可以想办法把多余的这层黑色移到合适的位置来修复规则5。
根据后继右孩子的兄弟节点颜色，又可以分为这几种情况：
- 兄弟节点是红色
- 兄弟节点是黑色，兄弟节点的孩子都是黑色。父亲节点颜色不确定
- 兄弟节点是黑色，兄弟节点的其中一个孩子是红色。父亲节点颜色不确定
3.1、后继右孩子的兄弟节点是红色
因为兄弟节点是红色，那么父亲节点必定为黑。此时对父亲节点进行旋转和变色操作即可把兄弟节点变成黑色，也就是情况1可以转化成情况2和情况3。
以上图为例，假设节点0为后继右孩子节点，10为兄弟节点。以父亲节点5进行左旋+变色可以把节点0的兄弟节点变成黑色。此时转化为3.2或3.3的场景，这个旋转+变色操作并不会使黑色节点数量发生变化，需要继续执行后续场景的操作。
3.2、后继右孩子的兄弟节点是黑色，兄弟节点的孩子都是黑色
可以把兄弟节点设置成红色，相当于提取了兄弟和自己的一层黑色给父亲，因为无法确定父亲节点的颜色，需要继续以父亲节点作为检查节点重新规则检查。
3.2、后继右孩子的兄弟节点是黑色，兄弟节点的其中一个孩子是红色
加上后继节点的颜色是父亲节点的左孩子，兄弟节点的右孩子是红色。此时以父亲节点进行左旋，把父亲节点和兄弟节点的右孩子的颜色也变成黑色，此时相当于后继节点这边的子树多了一个黑色节点，且兄弟节点这边的黑色节点数量不变，规则5被修复。
旋转后把原来的父亲节点5染黑，兄弟节点10的颜色改成和原父亲节点5一样的颜色。白色的节点表示颜色不确定
如果兄弟节点的左孩子是红色，可以先以兄弟节点进行右旋，这样就转换成上面的“兄弟节点的右孩子是红色”的情况了。
旋转兄弟节点，把情况转换“兄弟节点的右孩子是红色”。白色的节点表示颜色不确定
4、删除操作的伪代码
//node的属性color、left、right，parent分别为节点的颜色、节点的左子节点、节点的右子节点、节点的父亲
//枚举RED为红，BLACK为黑
//leftRotate为左旋函数
//rightRotate为左旋函数
//Root为根节点的指针
//nodeParent为后继右节点的父节点，因为后继右节点可能为空，需要传入它的新父节点
//nodeParent为后继右节点
//调用fixDeleteRule前已经确认后继节点是黑色了
fixDeleteRule(nodeParent,node){
while(node != ROOT and node.color == BLACK){
if(node == nodeParent.left){
//如果节点是父亲节点的左孩子
borther = nodeParent.right;//兄弟节点
if(borther.color == RED){
borther.color = black;
nodeParent.color = RED;
leftRotate(nodeParent);
borther = nodeParent.left;
}
if(borther == null or (borther.left.color == BLACK and borther.right.color == BLACK)){
borther.color = RED;
//颜色被提取到父亲节点上了，设置新的检查节点为父亲节点
node = nodeParent;
nodeParent = node.parent;
}else{
if(borther.left.color == RED){
borther.color = RED;
borther.left.color = BLACK;
rightRotate(borther);
}
//剩下的情况必定是兄弟节点的右孩子为红色
borther.color = nodeParent.color;
nodeParent.color = BLACK;
borther.right.color = BLACK;
leftRotate(nodeParent);
//规则已经修复，设置为根指针
node = Root;
}
}else{
//node是nodeParent的右孩子的情况，代码略...
}
}
//有可能node变成了根节点，需要修复一下颜色
node.color = BLACK;
}
