红黑树

定义

1. 节点是红色或黑色
2. 根节点是黑色
3. 所有null节点是黑色
4. 每个红色节点的两个子节点都是黑色（即两个红色节点不能相邻）
5. 从任一节点到每个null节点的所有路径都包含==相同数目的黑色节点==（重要性质）

性质

从根节点到null节点的路径中，最长路径不大于最短路径的两倍长。

证明：

路径最短 ===》 只有黑色节点

路径最长 ===》 每两个黑色节点之间加一个红色节点

即：最长路径 = 最短路径 * 2 - 1

红黑树的时间复杂度和空间复杂度：O(logn)

操作

所有的操作都是在操作一颗BST之后再维护红黑树特有的性质

二叉搜索树的性质：左小右大

红黑树中经常使用的操作：BST的左旋和右旋

重点需要注意经过操作后，红黑树的定义有没有被破坏

插入操作

先按照BST的插入操作进行操作，然后分析如下几种情况。

情况一

描述：被插入的节点为根节点

操作： 直接将插入节点的颜色涂成黑色即可（定义1）

情况二

描述：被插入的节点的父节点是 黑色

操作： 直接将插入节点的颜色涂成 红色 即可（为了维护定义5，因此这个新插入的节点不能是黑色）

情况三

描述：被插入的节点的父节点是 红色

---

先将此节点变为 红色（定义5），然后分以下几种情况来讨论：

3.1. 被插入节点的叔叔节点也是红色（递归操作）

操作：

• 将父节点设为黑色
• 将叔叔节点（当前节点的祖父节点的另一个子节点）设为黑色
• 将祖父节点（父节点的父节点）设为红色
• 将祖父节点设为当前节点，看是否满足其他情况，再继续对祖父节点进行操作，直至其满足红黑树的定义
  

3.2. 当前节点的叔叔节点是黑色，且当前节点是其父节点的右孩子

操作：

• 将父节点作为新的当前节点
• 然后以此时的当前节点（即之前的父节点）为支点进行 左旋
• 再看此时的状态是否符合其他情况
  

3.3. 叔叔节点是黑色，且当前节点是其父节点的左孩子

操作：

• 将父节点设为黑色
• 将祖父节点变为红色
• 然后以祖父节点为支点进行 右旋
  

一个综合性的例子

删除操作

先按照BST的删除操作对要删除的节点进行删除：

1. 只有一个子节点： 直接删除，然后将子节点直接拿过来即可
2. 没有子节点： 直接删除
3. 有两个子节点： 找到当前子节点右子树的最小值，然后剪切到所删除的节点处，然后将断开的节点直接接到剪切节点的父节点上（即第一种情况）

删除后，将删除节点的颜色加到删除位置的节点上

如过被删除的点有孩子节点，累加颜色：

如果被删除的节点（设是黑色节点）没有孩子节点，那么颜色会被累加到null节点上（null节点也是黑色的，因此此时null节点为黑+黑）：

然后考虑如下几种情况

情况一

描述：刚刚被删除的位置（后面将此位置称为x）的节点现在为红+黑节点

操作： 将x置为黑色即可

情况二

描述：x是根节点

操作： 将x置为黑色即可

情况三

此时的节点一定是 黑+黑 ，且不是根节点

然后分以下几种情况来讨论：

3.1. x 的兄弟节点为红色

操作：

• 将 x 的兄弟节点设为黑色
• 将 x 的父节点设为红色
• 对 x 的父节点进行左旋
• 左旋后，重新设置 x 的兄弟节点
  

3.2. x 的兄弟节点为黑色且x的兄弟节点的两个孩子节点都是黑色

操作：

• 将 x 的兄弟节点设为红色
• 将当前节点的一个黑色加到父节点上
  

3.3. x 的兄弟节点为黑色且x的兄弟节点的左孩子为红色，右孩子为黑色

操作：

• 将 x 的兄弟节点的左孩子设为黑色
• 设 x 的兄弟节点设为红色
• 对 x 的兄弟节点进行右旋
• 右旋后，重新设置 x 的兄弟节点
  

3.4. x 的兄弟节点为黑色且x的兄弟节点的右孩子为红色，左孩子为任意颜色

操作：

• 将 x 的父节点的颜色赋值给 x 的兄弟节点
• 设 x 的父节点设置为黑色
• 对 x 的兄弟节点的右孩子设置为黑色
• 对 x 的父节点进行左旋
  

情况3.1、3.2最多递归logn层，因此时间复杂度为logn级别