数据结构与算法（十三）——红黑树1 - Craftsman-L
source link: https://www.cnblogs.com/originator/p/16025880.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
数据结构与算法（十三）——红黑树1
红黑树是一种自平衡的排序二叉树，常用于关联数组、字典，在各种语言的底层实现中被广泛应用，Java 的 TreeMap 和 TreeSet 就是基于红黑树实现的，在 JDK 8 的HashMap中也有应用。
红黑树是在排序二叉树的基础上定义的，且还要满足以下性质（重要）：（请务必先学习排序二叉树，排序二叉树先看这篇 二叉树）
（1）每个结点要么是黑色，要么是红色。
（2）根结点是黑色。
（3）所有叶子结点都是黑色（这里说的叶子结点指 NIL 结点，空结点，即：空结点为黑色）。
（4）从任意一个结点到其所有叶子结点，所经过的黑色结点数目必须相等。
（5）所有红色结点的两个孩子结点必须是黑色（即，红色结点不能连续）。
代码示例：红黑树-树结点结构
1 protected static class RBNode<T extends Comparable<T>> {
2 private T value;
3 // 默认为 红色 结点
4 private boolean red = true;
5
6 private RBNode<T> left;
7 private RBNode<T> right;
8 private RBNode<T> parent;
9 }
树结点关系
2、左旋（重要）
代码示例：对 node 左旋
1 // 左旋
2 private void leftRotate(RBNode<T> node) {
3 if (node == null) {
4 return;
5 }
6 final RBNode<T> p = node.parent;
7
8 // 左旋. 应该认为 temp 不为null
9 final RBNode<T> temp = node.right;
10 node.right = temp.left;
11 if (temp.left != null) {
12 // 该结点可能不存在
13 temp.left.parent = node;
14 }
15
16 temp.left = node;
17 node.parent = temp;
18
19 // 旋转完成.修正根结点与父结点
20 // 1.node为根结点
21 if (node == root) {
22 root = temp;
23 temp.parent = null;
24 return;
25 }
26
27 // 2.node不为根结点
28 // node 为父结点的右孩子
29 if (node == p.right) {
30 p.right = temp;
31 } else {
32 p.left = temp;
33 }
34 temp.parent = p;
35 }
3、右旋（重要）
代码示例：对 node 右旋
1 // 右旋
2 private void rightRotate(RBNode<T> node) {
3 if (node == null) {
4 return;
5 }
6
7 final RBNode<T> p = node.parent;
8
9 // 右旋. 应该认为 temp 不为null
10 final RBNode<T> temp = node.left;
11 node.left = temp.right;
12 if (temp.right != null) {
13 // 该结点可能不存在
14 temp.right.parent = node;
15 }
16
17 temp.right = node;
18 node.parent = temp;
19
20 // 旋转完成.修正根结点与父结点
21 // 1.node为根结点
22 if (node == root) {
23 root = temp;
24 temp.parent = null;
25 return;
26 }
27
28 // 2.node不为根结点
29 // node 为父结点的右孩子
30 if (node == p.right) {
31 p.right = temp;
32 } else {
33 p.left = temp;
34 }
35 temp.parent = p;
36 }
由于树的左子树和右子树是对称的，所以只讨论一边的情况即可。插入的原则满足排序二叉树的规则。而红黑树的插入还要满足红黑树的性质，所以插入完成后，还要对红黑树进行调整。调整的原则（重要）：
（1）按排序二叉树的插入规则插入新结点（newNode）。
（2）新插入的结点默认为红色。
（3）若 newNode 为根结点，则变为黑色，插入完毕。
（4）若 newNode 不为根结点，若其父结点为黑色，插入完毕。
（5）若 newNode 不为根结点，若其父结点为红色，则按下面的情况讨论（下面也主要讨论这种情况）。
以 {7, 3, 10, 1(5)} 为例，添加 {7, 3, 10} 的结果很容易理解。
插入1(5)时，
情况一：newNode（1或5） 的叔叔结点（10）存在且为红色。
调整方案：父结点（3）与叔叔结点（10）变为黑色；祖父结点变为红色；新增结点 newNode 指向祖父结点（7），做递归的调整（这里newNode == root，则变为黑色即可）。
情况二：newNode（1或5） 的叔叔结点（10）不存在，或者为黑色。
调整方案：分为左左、左右、右右、右左讨论。（下面的讨论中，不妨将叔叔结点画为黑色）
左左：newNode == 祖父结点的左孩子的左孩子。
调整方案：先对祖父结点（7）右旋；父结点变为黑色，祖父结点变为红色。
左右：newNode == 祖父结点的左孩子的右孩子。
调整方案：先对父结点（3）左旋；后续调整同"左左"的方案。（需注意newNode的位置不同）
3、右右（与左左对称）
右右：newNode == 祖父结点的右孩子的右孩子。
调整方案：先对祖父结点（7）左旋；父结点变为黑色，祖父结点变为红色。
右左：newNode == 祖父结点的右孩子的左孩子。
调整方案：先对父结点（10）右旋；后续调整同"右右"的方案。（需注意newNode的位置不同）
代码示例：完整的红黑树插入及调整
完整的红黑树插入代码
代码示例：测试
1 public class Main {
2 public static void main(String[] args) {
3 Integer[] integers = {15, 7, 45, 3, 10, 25, 55, 1, 5, 75};
4 RBTree<Integer> tree = new RBTree<>(integers);
5
6 tree.infixOrder();
7 }
8 }
9
10 // 结果
11 -->1:红-->3:黑-->5:红-->7:红-->10:黑-->15:黑-->25:黑-->45:红-->55:黑-->75:红
最后，推荐一个在线构建红黑树的地址：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 用于读者验证上述代码的结果。上述测试案例构建的红黑树为：
见下一篇。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK