金典系列之红黑树

---

1. 定义

红黑树（Red Black Tree）是一种特化的AVL树（平衡二叉树）,因此它也是自平衡二叉查找树。对其进行插入和删除操作时，都需要通过特定操作（包括左旋、右旋等）,来保持其平衡性，从而获得较高的查找性能。

---

2. 红黑树存在的意义

在二叉查找树中，AVL树的查找效率是最高效的。既然AVL树的查找效率最高，那为何需要引入红黑树呢？其原因在于AVL树对于平衡（任意节点左右子树高度差不大于1）的要求极高。这种就造成新节点的插入极易导致AVL数不平衡，从而进行平衡调整。调整的过程非常耗时。因此，这才有了红黑树的用武之地。红黑树可以简单理解为在AVL树的一种改进，改进主要体现在，以舍弃查询效率为代价，放宽平衡条件。从而大大减少因新节点插入而导致的平衡调整。尽管红黑树放宽了平衡条件，但通过对任何一条从根到空节点的路径上各个结点的颜色进行约束，红黑树可以确保没有一条路径会比其他路径长出2倍，因而红黑树是近似平衡的。

---

3. 约束特征

1. 节点的颜色只能是黑色或红色
2. 根节点颜色只能是黑色
3. 所有叶子节点都是黑色
4. 每个红色节点的两个子节点都是黑色，即叶子到根的所有路径上不能有两个连续的红色节点
5. 从任意节点到叶子节点的所有路径都包含相同数目的黑色节点，故红黑树又被称为黑色完美平衡数

由上诉特征5可以推出：如果一个节点存在黑色子节点，那么该节点一定存在两个子节点（另一个子节点可以为红色节点）

---

4. 模型图

根据红黑色的约束特征，可以初步得到红黑树的模型图，具体效果如下：

---

5. 搜索过程

红黑树的搜索过程与二叉查找树一致，给定待搜索数 N ，用红黑树 T 其搜索过程如下：

N 首先与 T 的根节点作为当前节点（C）进行比较

• 如果 C 为空，则说明N不存在与该红黑树，查找结束
• 如果 N 等于 C，返回 C ，查找结束
• 如果 N 大于 C，将 N 与 C 的右子节点（R）进行比较，并将 R 置为当前节点 C，重复上述步骤
• 如果 N 小于 C，将 N 与 C 的左子节点（L）进行比较，并将 L 置为当前节点 C，重复上述步骤

给定待搜索整数35，及一棵红黑树，该红黑树如下图所示：

具体过程如下图所示：

---

6. 插入过程

新节点的插入，势必会违反红黑树的特征约束条件，打破红黑树原有的平衡。一旦红黑树的平衡被打破，则需要通过节点的左旋和右旋来达到节点插入后的平衡状态。

其中左旋（E节点）过程如下图所示：

右旋（S节点）过程如下图所示：

6.1 插入前存在的情况

规定待插入节点，即当前节点为C（Current），其父节点为P（Parent），祖父节点为G（Grand），叔叔节点为U（Uncle）。 由于插入红色节点不会影响路径上的黑节点数，因此规定待插入的节点初始颜色为红色。

6.1.1 红黑树为空

将C节点置黑，设为根节点

6.1.2 待插入节点已存在

找到已存在的节点，替换节点内容即可，不需要进行平衡调整

6.1.3 待插入节点的父节点为黑色

直接插入，不需要进行平衡调整

6.1.4 待插入节点的父节点为红色

由上述限制4【红色节点不能相连】 可以得出，待插入节点的祖父节点为黑色

6.1.4.1 叔叔节点存在且为红节点

模型图如下所示：

调整过程如下：

（1）将P和U置为黑色

（2）将G置为红色

（3）将G设为当前节点，进行后续处理

调整过程图如下所示：

如果G节点的父节点为黑色，则完成平衡调整，反之，将G节点设备当前节点，继续做插入平衡操作，直到平衡为之。

6.1.4.2 叔叔节点存在且为黑节点

情况模型图如下所示：

此时需要分类讨论，即需要区分待插入节点是P节点的左孩子还是右孩子

首先对上述图形的情形1进行分析

1）C是P的左孩子，即LL双红（C和P节点均为左子树，且为红节点），模型图如下所示：

调整过程如下：

（1）P节点置为黑色，G节点置为红色

（2）对G节点进行右旋

调整过程图如下所示：

2）C是P的右孩子，即LR双红（P节点为左子树，C节点为右子树，且为红节点），模型图如下所示：

调整过程如下：

（1）P节点进行左旋，得到LL双红（C节点和P节点组成）

（2）参照上述LL双红的情况进行处理

调整过程图如下入所示：

其次对上述图形的情形2进行分析，其过程与情形2类型

1）C是P的右孩子，即RR双红（C和P节点均为右子树，且为红节点），模型图如下所示：

调整过程如下：

（1）P节点置为黑色，G节点置为红色

（2）对G节点进行左旋

调整过程图如下所示：

2）C是P的左孩子，即RL双红（P节点为右子树，C节点为左子树，且均为红节点），模型图如下所示：

调整过程如下：

（1）P节点进行右旋，得RR双红（C节点和P节点组成）

（2）参照上述RR双红的情况进行处理

调整过程图如下所示：

6.1.5 插入案例

---

7. Java 实现

7.1 红黑树和节点类

/*** 红黑树类* getter、setter省略* 插入、左旋、右旋代码后续单独给出*/
public class RBTree<K extends Comparable, V> {// 根节点private TreeNode root;/*** 红黑树节点类* getter、setter省略*/public static final class TreeNode<K extends Comparable, V> {private NodeColorEnum color;private K k;private V v;private TreeNode parent;private TreeNode leftChild;private TreeNode rightChild;// 节点初始状态置为黑色public TreeNode(K k, V v) {this.k = k;this.v = v;this.color = RED;}}// 辅助方法/*** 获取当前节点的爷爷节点*/public static TreeNode grandOf(TreeNode treeNode) {if (treeNode != null && treeNode.parent != null) {return treeNode.parent.parent;}return null;}/*** 获取当前节点的爸爸节点*/public static TreeNode parentOf(TreeNode treeNode) {if (treeNode != null) {return treeNode.parent;}return null;}/*** 判断当前节点是否为根节点*/public static boolean isRoot(TreeNode treeNode) {if (treeNode == null) {return false;}return treeNode.parent == null;}/*** 节点置红*/public static void setRed(TreeNode treeNode) {if (treeNode != null) {treeNode.color = RED;}}/*** 节点置黑*/public static void setBlack(TreeNode treeNode) {if (treeNode != null) {treeNode.color = BLACK;}}/*** 判断当前节点是否为红节点*/public static boolean isRed(TreeNode treeNode) {if (treeNode == null) {return false;}return treeNode.color.getColor();}/*** 判断当前节点是否为黑节点*/public static boolean isBlack(TreeNode treeNode) {return treeNode == null || !treeNode.color.getColor();}
}

7.1 左旋实现

左旋过程：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2tFx5km6-1590497506168)(E:\个人工作资料目录\笔记文件夹\数据结构\红黑树\left_rotate.gif)]

代码实现：

/*** 左旋：**      g                        g*      |                        |*      p      --p节点左旋-->      r*     / \                      / \*    l   r                    p   rc*       / \                  / \*      lc rc                l  lc** 节点p左旋具体步骤如下：*    1. p的右子节点事项lc，lc的父节点指向p*    2. p的父节点【g】不为空时，r的父节点指向p的父节点【g】，【g】的子树节点指向r*    3. p的父节点指向r，r的左子树指向p*/
private void leftRotate() {// 1. p的右子节点事项lc，lc的父节点指向p// this为p节点Node r = this.rightChild;this.rightChild = r.leftChild;if (r.leftChild != null) {r.leftChild.parent = this;}// 2. p的父节点【g】不为空时，r的父节点指向p的父节点【g】，【g】的子树节点指向rif (this.parent != null) {if (this.parent.leftChild == this) {this.parent.leftChild = r;} else {this.parent.rightChild = r;}}// 3. p的父节点指向r，r的左子树指向pthis.parent = r;r.leftChild = this;
}

7.2 右旋实现

右旋过程：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xTH3ZCsI-1590497506168)(E:\个人工作资料目录\笔记文件夹\数据结构\红黑树\right_rotate.gif)]

代码实现：

/*** 右旋：**      g                        g*      |                        |*      p      --p节点右旋-->     l*     / \                      / \*    l   r                    lc  p*   / \                          / \*  lc rc                        rc  r** 节点p右旋具体步骤如下：*    1. p的左子节点指向rc，rc的父节点指向p*    2. p的父节点【g】不为空时，l的父节点指向p的父节点【g】，【g】的子树指向l*    3. l的右子节点指向p，p的父节点指向l*/
private void rightRotate() {// 1. p的左子节点指向rc，rc的父节点指向p// this为p节点Node l = this.leftChild;this.leftChild = l.rightChild;if (l.rightChild != null) {l.rightChild.parent = this;}// 2. p的父节点【g】不为空时，l的父节点指向p的父节点【g】，【g】的子树指向lif (this.parent != null) {if (this.parent.leftChild == this) {this.parent.leftChild = l;} else {this.parent.rightChild = l;}}// 3. p的父节点指向l，l的右子节点指向pthis.parent = l;l.rightChild = this;
}

7.3 新节点插入

代码实现：

/*** 插入：*   不需要进行平衡调整：*     情形1：红黑树为空*     情形2：待插入节点已存在*     情形3：插入节点的父节点为黑色*/
public void insert(K k, V v) {TreeNode<K, V> insertNode = new TreeNode<>(k, v);// 情形1：红黑树为空if (root == null) {this.root = insertNode;this.root.color = BLACK;return;}TreeNode parent = null;TreeNode current = root;while (current != null) {parent = current;int cmp = current.k.compareTo(insertNode.k);if (cmp > 0) {current = current.leftChild;}// 情形2：待插入节点已存在else if (cmp == 0) {current.v = insertNode.v;return;} else {current = current.rightChild;}}insertNode.parent = parent;if (insertNode.k.compareTo(parent.k) > 0) {parent.rightChild = insertNode;} else {parent.leftChild = insertNode;}// 情形3：插入节点的父节点为黑色if (isBlack(parent)) {return;}// 除了上述3中情形外，需要对新插入的节点进行平衡调整balanceInsertion(insertNode);
}

插入平衡调整：

/*** 插入平衡：*   需要进行平衡调整：*     情形4：插入节点的父节点为红色*        4.1：叔叔节点存在且为红色（父叔双红）  -->  叔叔和父节点置黑，爷爷节点置为红，将爷爷节点置为当前节点，进行后续操作*        4.2：叔叔节点为黑色或为空，父节点为爷爷节点的左子节点*          4.2.1：待插入节点为父节点的左子节点（LL双红）*          4.2.2：待插入节点为父节点的右子节点（LR双红）*        4.3：叔叔节点为黑色或为空，父节点为爷爷节点的右子节点*          4.3.1：待插入节点为父节点的左子节点（RL双红）*          4.3.2：待插入节点为父节点的右子节点（RR双红）***/
private void balanceInsertion(TreeNode node) {if (isRoot(node)) {node.color = BLACK;return;}TreeNode parent = parentOf(node);TreeNode grand = grandOf(node);// 获取待平衡节点的叔叔节点TreeNode uncle = parent.leftChild == node ? grand.rightChild : grand.leftChild;// 情形4.1：叔叔节点存在且为红色（父叔双红）//         叔叔和父节点置黑，爷爷节点置为红，将爷爷节点置为当前节点，进行后续操作if (isRed(uncle)) {parent.color = BLACK;uncle.color = BLACK;grand.color = RED;balanceInsertion(grand);return;}// 情形4.2：叔叔节点为黑色或为空，父节点为爷爷节点的左子节点if (isBlack(uncle)) {if (parent == grand.leftChild) {// 4.2.2：待平衡节点为父节点的右子节点（LR双红）//        父节点左旋if (node == parent.rightChild) {leftRotate(parent);}// LL双红情况（情形4.2.1及情形4.2.2父节点左旋得到）grand.color = RED;parent.color = BLACK;rightRotate(grand);}// 4.3：叔叔节点为黑色或为空，父节点为爷爷节点的右子节点else {// 4.3.2：待插入节点为父节点的右子节点（RR双红）//        父节点置为黑色，爷爷节点置为红色，爷爷节点左旋// 4.3.1：待插入节点为父节点的左子节点（RL双红）//        父节点右旋，形成RR双红if (node == parent.leftChild) {rightRotate(parent);}// RR双红情况（情形4.3.2及情形4.3.1父节点右旋旋得到）parent.color = BLACK;grand.color = RED;leftRotate(grand);}}
}

---