数据结构与算法（十三）——红黑树1 数据结构与算法（十三）—

一、概述 1、介绍
红黑树是一种自平衡的排序二叉树，常用于关联数组、字典，在各种语言的底层实现中被广泛应用，Java 的 TreeMap 和 TreeSet 就是基于红黑树实现的，在 JDK 8 的HashMap中也有应用。
红黑树是在排序二叉树的基础上定义的，且还要满足以下性质（重要）：（请务必先学习排序二叉树，排序二叉树先看这篇二叉树）
（1）每个结点要么是黑色，要么是红色。
（2）根结点是黑色。
（3）所有叶子结点都是黑色（这里说的叶子结点指 NIL 结点，空结点，即：空结点为黑色）。
（4）从任意一个结点到其所有叶子结点，所经过的黑色结点数目必须相等。
（5）所有红色结点的两个孩子结点必须是黑色（即，红色结点不能连续）。
代码示例：红黑树-树结点结构

1 protected static class RBNode> { 2private T value; 3// 默认为红色结点 4private boolean red = true; 5 6private RBNode left; 7private RBNode right; 8private RBNode parent; 9 }

树结点关系

文章图片

2、左旋（重要）
动图：

文章图片

文章图片

【数据结构与算法（十三）——红黑树1】代码示例：对 node 左旋

1 // 左旋 2 private void leftRotate(RBNode node) { 3if (node == null) { 4return; 5} 6final RBNode p = node.parent; 7 8// 左旋. 应该认为 temp 不为null 9final RBNode temp = node.right; 10node.right = temp.left; 11if (temp.left != null) { 12// 该结点可能不存在 13temp.left.parent = node; 14} 15 16temp.left = node; 17node.parent = temp; 18 19// 旋转完成.修正根结点与父结点 20// 1.node为根结点 21if (node == root) { 22root = temp; 23temp.parent = null; 24return; 25} 26 27// 2.node不为根结点 28// node 为父结点的右孩子 29if (node == p.right) { 30p.right = temp; 31} else { 32p.left = temp; 33} 34temp.parent = p; 35 }

3、右旋（重要）
动图：

文章图片

文章图片

代码示例：对 node 右旋

1 // 右旋 2 private void rightRotate(RBNode node) { 3if (node == null) { 4return; 5} 6 7final RBNode p = node.parent; 8 9// 右旋. 应该认为 temp 不为null 10final RBNode temp = node.left; 11node.left = temp.right; 12if (temp.right != null) { 13// 该结点可能不存在 14temp.right.parent = node; 15} 16 17temp.right = node; 18node.parent = temp; 19 20// 旋转完成.修正根结点与父结点 21// 1.node为根结点 22if (node == root) { 23root = temp; 24temp.parent = null; 25return; 26} 27 28// 2.node不为根结点 29// node 为父结点的右孩子 30if (node == p.right) { 31p.right = temp; 32} else { 33p.left = temp; 34} 35temp.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）不存在，或者为黑色。
调整方案：分为左左、左右、右右、右左讨论。（下面的讨论中，不妨将叔叔结点画为黑色）
1、左左
左左：newNode == 祖父结点的左孩子的左孩子。
调整方案：先对祖父结点（7）右旋；父结点变为黑色，祖父结点变为红色。

文章图片

2、左右
左右：newNode == 祖父结点的左孩子的右孩子。
调整方案：先对父结点（3）左旋；后续调整同"左左"的方案。（需注意newNode的位置不同）

文章图片

3、右右（与左左对称）
右右：newNode == 祖父结点的右孩子的右孩子。
调整方案：先对祖父结点（7）左旋；父结点变为黑色，祖父结点变为红色。

文章图片

4、右左
右左：newNode == 祖父结点的右孩子的左孩子。
调整方案：先对父结点（10）右旋；后续调整同"右右"的方案。（需注意newNode的位置不同）

文章图片

5、总结

文章图片

代码示例：完整的红黑树插入及调整

文章图片

1 public class RBTree> { 2// 根结点 3private RBNode root; 4 5public RBTree() { 6} 7 8public RBTree(T[] arr) { 9if (arr == null || arr.length == 0) { 10return; 11} 12 13for (T i : arr) { 14this.add(i); 15} 16} 17 18// 添加结点 19public void add(T value) { 20RBNode newNode = new RBNode<>(value); 21if (root == null) { 22root = newNode; 23newNode.red = false; 24return; 25} 26 27// 1.添加 28this.add(root, newNode); 29 30// 2.调整 31this.fixUp(newNode); 32} 33 34private void fixUp(RBNode newNode) { 35if (newNode == root) { 36newNode.red = false; 37return; 38} 39 40// newNode 的父结点为黑色 41if (!newNode.parent.red) { 42return; 43} 44 45/* 1.newNode 的叔叔结点存在且为红色。*/ 46final RBNode uncle = newNode.getUncle(); 47if (uncle != null && uncle.red) { 48newNode.parent.red = false; 49uncle.red = false; 50 51newNode.parent.parent.red = true; 52this.fixUp(newNode.parent.parent); 53} else { 54/* 2.newNode 的叔叔结点不存在，或者为黑色。*/ 55final RBNode grandFather = newNode.getGrandFather(); 56// 2.1左左 57if (newNode == grandFather.left.left) { 58this.rightRotate(grandFather); 59newNode.parent.red = false; 60grandFather.red = true; 61} 62// 2.2左右 63else if (newNode == grandFather.left.right) { 64this.leftRotate(newNode.parent); 65this.rightRotate(grandFather); 66newNode.red = false; 67grandFather.red = true; 68} 69// 2.3右右 70else if (newNode == grandFather.right.right) { 71this.leftRotate(grandFather); 72newNode.parent.red = false; 73grandFather.red = true; 74} 75// 2.4右左 76else if (newNode == grandFather.right.left) { 77this.rightRotate(newNode.parent); 78this.leftRotate(grandFather); 79newNode.red = false; 80grandFather.red = true; 81} 82} 83} 84 85// 按排序二叉树的规则插入结点 86private void add(RBNode root, RBNode newNode) { 87if (newNode.value.compareTo(root.value) <= 0) { 88if (root.left == null) { 89root.left = newNode; 90newNode.parent = root; 91} else { 92this.add(root.left, newNode); 93} 94} else { 95if (root.right == null) { 96root.right = newNode; 97newNode.parent = root; 98} else { 99this.add(root.right, newNode); 100} 101} 102} 103 104// 左旋 105private void leftRotate(RBNode node) { 106if (node == null) { 107return; 108} 109final RBNode p = node.parent; 110 111// 左旋. 应该认为 temp 不为null 112final RBNode temp = node.right; 113node.right = temp.left; 114if (temp.left != null) { 115// 该结点可能不存在 116temp.left.parent = node; 117} 118 119temp.left = node; 120node.parent = temp; 121 122// 旋转完成.修正根结点与父结点 123// 1.node为根结点 124if (node == root) { 125root = temp; 126temp.parent = null; 127return; 128} 129 130// 2.node不为根结点 131// node 为父结点的右孩子 132if (node == p.right) { 133p.right = temp; 134} else { 135p.left = temp; 136} 137temp.parent = p; 138} 139 140// 右旋 141private void rightRotate(RBNode node) { 142if (node == null) { 143return; 144} 145 146final RBNode p = node.parent; 147 148// 右旋. 应该认为 temp 不为null 149final RBNode temp = node.left; 150node.left = temp.right; 151if (temp.right != null) { 152// 该结点可能不存在 153temp.right.parent = node; 154} 155 156temp.right = node; 157node.parent = temp; 158 159// 旋转完成.修正根结点与父结点 160// 1.node为根结点 161if (node == root) { 162root = temp; 163temp.parent = null; 164return; 165} 166 167// 2.node不为根结点 168// node 为父结点的右孩子 169if (node == p.right) { 170p.right = temp; 171} else { 172p.left = temp; 173} 174temp.parent = p; 175} 176 177// 中序遍历 178public void infixOrder() { 179this.infixOrder(root); 180} 181 182private void infixOrder(RBNode root) { 183if (root != null) { 184this.infixOrder(root.left); 185System.out.print("-->" + root.value + ":" + (root.red ? "红" : "黑")); 186this.infixOrder(root.right); 187} 188} 189 190/** 191* 红黑树树结点结构 192*/ 193protected static class RBNode> { 194private T value; 195// 默认为红色结点 196private boolean red = true; 197 198private RBNode left; 199private RBNode right; 200private RBNode parent; 201 202public RBNode() { 203} 204 205public RBNode(T value) { 206this.value = https://www.it610.com/article/value; 207} 208 209// 返回结点的度 210public int getDegree() { 211if (this.left == null && this.right == null) { 212return 0; 213} 214 215if ((this.left != null && this.right == null) || (this.left == null && this.right != null)) { 216return 1; 217} 218 219return 2; 220} 221 222public RBNode getUncle() { 223final RBNode grandFather = this.parent.parent; 224final RBNode parent = this.parent; 225 226if (parent == grandFather.left) { 227return grandFather.right; 228} 229 230if (parent == grandFather.right) { 231return grandFather.left; 232} 233 234return null; 235} 236 237public RBNode getGrandFather() { 238return this.parent.parent; 239} 240 241@Override 242public String toString() { 243return "RBNode{" + 244"value="https://www.it610.com/article/+ value + 245", red=" + red + 246'}'; 247} 248} 249 }

完整的红黑树插入代码代码示例：测试

1 public class Main { 2public static void main(String[] args) { 3Integer[] integers = {15, 7, 45, 3, 10, 25, 55, 1, 5, 75}; 4RBTree tree = new RBTree<>(integers); 5 6tree.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用于读者验证上述代码的结果。上述测试案例构建的红黑树为：