红黑树

一、产生背景

1. BST（binary search tree 二叉搜索树）树的的平衡性问题：
   1. 如果插入BST中数据顺序随机，则平衡性较好。
   2. 如果插入BST中数据顺序有序，则平衡性很差，是一条顺序链。
2. 为了改进BST的平衡性产生了红黑树。

二、基本概念

1. 红黑树（red-black tree，简称RB-tree）
2. 红黑树是自平衡的BST，是BST的扩充二叉树。
3. 结点颜色：结点分为“红色”和“黑色”。
4. 根结点：根结点永远是“黑色”；
5. 外部叶结点：叶结点都是扩充的外部结点（Nil），叶结点都是空的“黑色”结点。
6. 内部结点：“红”结点的两个子结点都是“黑”，不允许两个连续的“红”结点。
7. 深度特征：任何结点到其子孙外部结点的每条简单路径都包含相同数目的“黑”结点（此处体现出了红黑树的平衡性）。
8. 红黑树的阶
   1. 结点的阶：rank，也称“黑色高度”。
      1. 从该结点到叶结点的黑色结点数量
      2. 不包括该结点本身，包括叶结点。
      3. 叶结点的阶是0。
   2. 根的阶称为红黑树的阶。

三、性质：

1. 红黑树是扩充二叉树，叶结点都是扩充的空结点；
2. 阶为k的红黑树路径长度最短为k（全是黑），最长为2k（一黑一红）。
3. 阶为k的红黑树的内部节点：内部节点数量最少时，是一个全黑的完全满二叉树，个数为2k-1。
4. 有n个内部结点的红黑树树高最大为2log2(n+1)+1 。

四、红黑树插入

1. 先使用BST插入算法（先找到结点所在位置，将新结点作为叶结点连接上去。如果还不明白，就需要先去了解BST的插入删除操作）；
2. 把新结点标为红色，如果父结点是黑色，则结束。（红黑树是通过黑色结点来控制树高，维持深度特征，所以新插入点标为红色，不会影响深度特征。）
3. 否则，双红冲突，需要双红调整。
4. 双红冲突调整：

假设当前双红结点为X，父结点为A，祖父节点为B，叔父结点为C，只要分析C的颜色（因为X和A都是红色，所以X和A的子结点都是黑色，B也为黑色，只有C结点的颜色不确定）。

（1）情况一：C是黑色。

重构：重新调整XAB结构（不会增加树的阶数。因为C为黑色，重构XAB后不会产生新的冲突，所以重构C）。

XAB共有4种结构，以下用具体数值“2/4/6”说明

（2）情况二：C是红色。

因为叔父为红色，重构仍具有双红冲突，所以需要换色。

换色：父结点和叔父结点换为黑色，祖父结点换为红色。换色操作会往祖先的方向传递，所以还要继续平衡检查。（只有传递到根结点才会增加树的阶数）。

五、红黑树删除

1. 先调用BST的删除算法。
   1. 如果待删除结点的左右子结点有一个为空，直接删除，把子结点挂接上就行了。
   2. 如果左右子结点都不空，则和右子树最小结点交换值（颜色不变），然后删除。（颜色是维持树的平衡，只与位置有关，与值无关，所以换值不换色）
2. 再检查平衡。
   1. 如果被删结点是红色，则直接删除，结束。否则被删结点是黑色，则进行下列调整。
   2. 如果后继结点（挂接上来的结点）是红色，则将此结点标为黑色，结束。否则，如果后继结点是黑色（Nil叶结点就是黑色结点），则进行双黑调整，此结点称为双黑结点（因为删掉的结点为黑色，后继也为黑色，此时后继这条路径上就少了一个黑色结点，必须调整）。
3. 双黑调整：（分析兄弟和侄子的颜色）

假设双黑结点为X，其兄弟结点为C，其父节点为B，主要分析C的情况。

情况1：C为黑色，且C子结点中有红色（假设为D），则D变为黑色再重构BCD，结束。

情况2：C为黑色，且C子结点都是黑色，则换色，C变为红色，B变为黑色。如果B原来是红色，则调整结束。如果父节点B原来为黑色，则B变成了双黑结点，还需要向上调整。

情况3：C为红色，则旋转，C旋转为父节点，C继承B的颜色，B变为红色。因为C为红色，则C的子结点必定都是黑色，则X的新兄弟是黑色，按照情况1或2继续调整。

六、红黑树性能及适用范围

1. 性能：查找、插入、删除的时间代价都是logN。
2. 适用范围：红黑树适用于内存中小规模的数据索引。外存或内存中大规模数据索引适用B树或B+树。