红黑树

编辑中

• 树：非线性存储结构，由 n 个有限结点组成一个具有层次关系的集合。、
• 二叉搜索树：左孩子小于父节点，右孩子大于父节点。
• AVL 树（平衡树）：具有二叉搜索树的全部特性，左右子树高度差至多为1，插入或删除节点时需要左旋和右旋保持树对的平衡。

再插入、删除很频繁的场景中，平衡树需要频繁着进行调整，会使平衡树的性能大打折扣，为解决这个问题，提出了红黑树。

1. 红黑树性质

1. 每个节点要么是黑色，要么是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。
4. 每个红色节点的两个子节点一定都是黑色。 （不能有两个红色节点相邻）
5. 任意一节点到每个叶子节点的路径都包含数量相同的黑色节点，俗称：黑高。
   • 可以推断出：如果一个节点存在黑子节点，你们该节点肯定有两个子节点。

红黑树并不是一个完美平衡二叉查找树，从图中可以看到，根节点 P 的左子树高于右子树。但左右子树黑节点的层数相等，所以红黑树这种平衡为黑色完美平衡。

2. 红黑树查找

与二叉搜索树的查找方式一样

3. 红黑树平衡

红黑树保持自平衡依靠：左旋、右旋、变色

• 变色：节点颜色红变黑，或者黑变红。

• 左旋：以某节点作为支点（旋转节点），其右子结点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。

• 右旋：以某节点作为支点（旋转节点），其左子结点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。

左旋图示

左旋动图

右旋图示

右旋动图

4. 红黑树插入

插入操作包括两部分工作：

1. 查找插入的位置
2. 插入后自平衡

注意：插入节点，必须为红色，因为红色在父节点（如果存在）为黑色节点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入节点是黑色，那么插入位置所在的子树黑色节点总是多 1，必须做自平衡。

红黑树插入情况分析：

情景1：红黑树为空树

直接把插入节点作为根节点，并把插入的节点设为黑色，因为性质 2 规定根节点是黑色。

情景2：插入节点的 Key 已存在

更新当前节点的值，为插入节点的值。

情景3：插入节点的父节点为黑色

由于插入节点是红色的，插入后并不影响红黑树的平衡。根据 Q 的大小选择插入的左右节点。

情景4：插入节点的父节点为红色

依据性质2可知，根节点是黑色，如果插入节点的父节点为红色，那么该父节点不可能为根节点，所以插入节点总是存在祖父节点。

情景4.1：叔叔节点存在并且为红色节点，即父节点和叔叔节点都为红色

依据性质4可知，红色节点不能相连，所以祖父节点肯定为黑色。

因为不可以同时存在两个相连的红节点，那么此时该插入子树的红黑层数的情况是：黑红红，显然最简单的处理方式是改成：红黑红。

处理：

1. 将 P 和 U 改成黑色
2. 将 PP 改成红色
3. 将 PP 设置为当前节点，进行后续

可以看到，将 PP 节点设为红色，如果 PP 的父节点是黑色，那么无需做任何处理；但，如果 PP 的父节点是红色就违反了红黑树的性质，所以需要将 PP 设置为当前节点，继续做插入操作自平衡处理，直到平衡为止。

情景4.2：叔叔节点不存在或为黑节点，并且插入节点的父节点是祖父节点的左子节点

情景4.2.1：新插入节点，为左子节点（LL双红）

处理：

1. 变色：将 P 设置为黑色，将 PP 设置为红色
2. 对 PP 节点进行右旋

情景4.2.2：新插入节点，为右子节点（LR双红）

处理方式

1. P 节点左旋（得到了 4.2.1 的情况：LL 双红）
2. 变色：将 I 设置为黑色，将 PP 设置为红色
3. 对 PP 节点进行右旋

情景4.3：叔叔节点不存在或为黑色，插入节点的父节点是祖父节点的右子节点

也就是情景 4.2 的相反情况。

情景4.3.1：新插入节点为父节点的右子节点（RR双红）

处理：

1. 变颜色：将 P 设置为黑色，将 PP 设置为红色
2. 对 PP 进行左旋

情景4.3.2：新插入节点为父节点的左子节点（RL双红）

处理

1. P 节点右旋（得到了 4.3.1 的情况：RR 双红）
2. 变色：将 I 设置为黑色，将 PP 设置为红色
3. 对 PP 节点进行左旋

5. 红黑树插入案例分析

下面看看这棵红黑树，需要插入新的节点 7.

简化一下，把 NIL 节点去掉。

先将准备插入的节点改成红色，也就是红色节点7，找到它应该插入的位置，应该为 8 的左节点。

现在就属于情景 4.1，叔叔节点存在并且为红色节点。可以将父节点和叔叔节点变成黑色，爷爷节点变成红色，将爷爷节点置为当前节点。

此时的当且节点为红 15，属于情景 4.2.2，爷爷节点为黑色，父节点为红色，叔叔节点为红色，LR 双红。通过将节点 5 左旋，获得 4.2.1 的情况 LL 双红。

将节点 15 和 19 变色，并将 19 设置为当前节点

对节点 19 进行右旋，此时就得到最后的红黑树