红黑树——一种自平衡的二叉树
一、红黑树简介
普通二叉树在数据不够均匀的情况下，可能导致左右子树高度会相差比较大，最坏情况下树的结构相当于一个链表，时间复杂度为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 = RE