前言
红黑树是算法领域中一个著名的二叉查找树实现，它能够以较小的开销保持二叉查找树的平衡。具备平衡性质的二叉查找树能够极大地提高节点的查询速度。举个形象一点的例子：从一个十亿节点的红黑树中查找一个节点，所需要的查询次数不到30，这不禁让人感叹算法的魅力。
红黑树是工程中最常见的二叉查找树的实现，例如在Linux的内存管理和进程管理中就用到了红黑树；Java语言的集合包、C++语言的标准模板库中均提供了红黑树的实现类。
红黑树本身的设计很复杂，多数情况下我们也不需要自己去实现红黑树，但研究红黑树还是有意义的。一方面可以让学习者领略这种神奇的数据结构的奥妙，另一方面可以作为一种思维训练工具，提升自己的算法设计能力。
本文以漫画形式讲述红黑树，第一话讲解二叉查找树的概念和基本操作，包括节点查找、插入、删除；第二话讲解二叉查找树的缺点和红黑树的概念，以及红黑树的节点旋转操作；第三话讲解红黑树的节点插入操作；第四话讲解红黑树的节点删除操作；第五话和彩蛋部分讲解红黑树在插入修正和删除修正时，对各种CASE所进行的调整操作背后的思想。
红黑树的实现中，最难的部分在于实现节点的插入和删除时，要穷举所有可能的CASE，然后对每种CASE进行处理。在理解节点的插入和删除的过程时，读者要把握住一个中心：每种CASE所进行的调整步骤都在尽量恢复插入/删除节点后所违反的红黑树特性，如果当前CASE解决不了，就转成另一种更接近问题解决状态的CASE。每种CASE的所进行的调整步骤都是为了向解决问题的出口更靠近一步，直至找到出口。
漫画采用大量的图示来展示红黑树操作的诸多细节，作者力求详尽，因此篇幅略长。附录给出了完整的二叉查找树定义 + 测试代码，以及红黑树定义 + 测试代码。两份代码均经过了若干次十万数量级随机节点插入和删除测试，结果均无误。读者可贴到自己的 IDE 中，结合本文讲解进行调试研究。
在电脑端本文阅读效果更佳。另外，读者可联系「码海」公众号博主（微信：geekoftaste）获取本漫画的pdf版本。
正文
附录：代码清单
二叉查找树代码
BsTreeTest.java
package bst;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public class BsTreeTest {
public static void main(String[] args) {
// 随机数的上限
int bound = 10000000;
// 随机序列的长度
int seqLen = 100000;
// 随机数生成器
Random random = new Random();
// 根节点值
int rootValue = random.nextInt(bound);
// 随机序列容器
List<Integer> intSeq = new ArrayList<>();
intSeq.add(rootValue);
// 往随机序列容器中添加随机值
while (intSeq.size() < seqLen) {
int rand = random.nextInt(bound);
intSeq.add(rand);
}
System.out.println("插入序列：" + intSeq);
// 创建一个bst
BsTree<Integer> bsTree = new BsTree<>();
BsTreeNode<Integer> root = new BsTreeNode<>(rootValue);
// 把intSeq中的随机数全部插入进去，测试节点插入过程
for (Integer key : intSeq) {
bsTree.insertRecursively(root, new BsTreeNode<Integer>(key));
}
// 插入完成后，打印整个bst的中序遍历结果，验证是否符合二叉搜索树的特性
List<Integer> middleOderOutput1 = new LinkedList<>();
bsTree.middleOder(root, middleOderOutput1);
System.out.println("构造完成，中序遍历结果为：" + middleOderOutput1);
System.out.println();
// 选取一部分节点值，测试节点删除过程
List<Integer> delList = middleOderOutput1.subList(middleOderOutput1.size() / 4, middleOderOutput1.size() / 2);
for (int item : delList) {
bsTree.deleteRecursively(root, item);
}
List<Integer> middleOderOutput2 = new LinkedList<>();
bsTree.middleOder(root, middleOderOutput2);
System.out.println("
删除完成，中序遍历结果为：" + middleOderOutput2);
System.out.println();
// 测试bst中“删除前总节点数目 - 删除节点数目 = 删除后总节点数目”是否成立
System.out.println("
(out1.size()- out2.size()) == delList.size()? " + ((middleOderOutput1.size() - middleOderOutput2.size()) == delList.size()));
// 测试bst中“删除前节点 包含全部 删除后节点”是否成立
System.out.println("out1.containsAll(out2)? " + (middleOderOutput1.containsAll(middleOderOutput2)));
// 测试bst中“删除前节点 包含全部 被删除节点”是否成立
System.out.println("out1.containsAll(delList)? " + (middleOderOutput1.containsAll(delList)));
}
}
BsTree.java
package bst;
import java.util.Collection;
public class BsTree<T extends Comparable<T>> {
/**
* 使用递归实现 BsTree 查找
*
* @param root BST 根节点引用
* @param key 待查找的节点值
* @return 命中的节点
*/
public BsTreeNode<T> searchRecursively(BsTreeNode<T> root, T key) {
if (root == null) {
return null;
}
if (root.nodeKey.compareTo(key) > 0) {
return searchRecursively(root.left, key);
} else if (root.nodeKey.compareTo(key) < 0) {
return searchRecursively(root.right, key);
} else {
return root;
}
}
/**
* 中序遍历 BsTree，打印节点值（递归实现）
*
* @param root
*/
public void inOder(BsTreeNode<T> root) {
if (root == null) {
return;
}
inOder(root.left);
System.out.print("->" + root.nodeKey.toString());
inOder(root.right);
}
/**
* 中序遍历 BsTree，打印节点值（递归实现）
*
* @param root
*/
public void middleOder(BsTreeNode<T> root, Collection<T> collection) {
if (root == null) {
return;
}
middleOder(root.left, collection);
//System.out.print("->" + root.nodeKey.toString());
collection.add(root.nodeKey);
middleOder(root.right, collection);
}
/**
* 向 BsTree 中插入节点（递归实现）
* <p>
* 二叉排序树本身是动态查找表的一种表示形式，有时会在
* 查找过程中插入或者删除表中元素。当因为查找失败而需
* 要插入数据元素时，该数据元素的插入位置一定位于二叉
* 排序树的叶子结点，并且一定是查找失败时访问的最后一
* 个结点的左孩子或者右孩子。
*
* @param root BsTree 根节点引用
* @param key 待插入的节点值
* @return 插入成功返回 true，如果树中有该元素不需要插入则返回 false
*/
public boolean insertRecursively(BsTreeNode<T> root, T key) {
if (root.nodeKey.compareTo(key) > 0) {
if (root.left == null) {
BsTreeNode<T> node = new BsTreeNode(key);
root.left = node;
node.parent = root;
return true;
} else {
return insertRecursively(root.left, key);
}
} else if (root.nodeKey.compareTo(key) < 0) {
if (root.right == null) {
BsTreeNode<T> node = new BsTreeNode(key);
root.right = node;
node.parent = root;
return true;
} else {
return insertRecursively(root.right, key);
}
} else {
return false;
}
}
/**
* 向 BsTree 中插入节点（递归实现）
* <p>
* 二叉排序树本身是动态查找表的一种表示形式，有时会在
* 查找过程中插入或者删除表中元素。当因为查找失败而需
* 要插入数据元素时，该数据元素的插入位置一定位于二叉
* 排序树的叶子结点，并且一定是查找失败时访问的最后一
* 个结点的左孩子或者右孩子。
*
* @param root BsTree 根节点引用
* @param nodeInserted 待插入的节点值
* @return 插入成功返回 true，如果树中有该元素不需要插入则返回 false
*/
public boolean insertRecursively(BsTreeNode<T> root,
BsTreeNode<T> nodeInserted) {
if (root == null) {
root = nodeInserted;
return true;
}
if (root.nodeKey.compareTo(nodeInserted.nodeKey) > 0) {
if (root.left == null) {
root.left = nodeInserted;
nodeInserted.parent = root;
return true;
} else {
return insertRecursively(root.left, nodeInserted);
}
} else if (root.nodeKey.compareTo(nodeInserted.nodeKey) < 0) {
if (root.right == null) {
root.right = nodeInserted;
nodeInserted.parent = root;
return true;
} else {
return insertRecursively(root.right, nodeInserted);
}
} else {
return false;
}
}
/**
* 假设要删除的为结点 p，则对于二叉排序树来说，需要根据结点 p
* 所在不同的位置作不同的操作，有以下 3 种可能：
* 1. 结点 p 为叶子结点，此时只需要删除该结点，并修改其双亲结点的指针即可
* 2. 结点 p 只有左子树或者只有右子树，如果 p 是其双亲节点的左孩子，则直
* ---接将 p 节点的左子树或右子树作为其双亲节点的左子树；反之也是如此，如
* ---果 p 是其双亲节点的右孩子，则直接将 p 节点的左子树或右子树作为其双
* ---亲节点的右子树；
* 3. 结点 p 左右子树都有，此时有两种处理方式：
* ---3.1. 令结点 p 的左子树为其双亲结点的左子树；结点 p 的右子树为其自
* --------身直接前驱结点的右子树
* ---3.2. 用结点 p 的直接前驱（或直接后继）来代替结点 p，同时在二叉排序
* --------树中对其直接前驱（或直接后继）做删除操作（ps：这种方式更好，因
* --------为这样可以最大程度的保证原树的结构，而且不会让树过于倾斜）
*/
public void deleteRecursively(BsTreeNode<T> currentNode, T key) {
if (currentNode == null) {
return;
}
// 当前节点键值大于 key，去左子树寻找
if (currentNode.nodeKey.compareTo(key) > 0) {
deleteRecursively(currentNode.left, key);
}
// 当前节点键值小于 key，去右子树寻找
else if (currentNode.nodeKey.compareTo(key) < 0) {
deleteRecursively(currentNode.right, key);
}
// 当前节点键值等于 key，处理当前节点
else {
// 对于第一种情形，左右子树均为空，直接删掉就是了，不涉及树结构的调整
if (currentNode.right == null && currentNode.left == null) {
BsTreeNode<T> parent = currentNode.parent;
// 通过父节点来删除节点
if (parent.left == currentNode) {
parent.left = null;
}
if (parent.right == currentNode) {
parent.right = null;
}
System.out.print("
case1 delete: " + key);
return;
}
// 对于第二种情形，待删除节点只有左子树，用待删除节点的左子树替换待删除节点即可
else if (currentNode.right == null) {
BsTreeNode<T> rootLeft = currentNode.left;
T temp = rootLeft.nodeKey;
currentNode.left = rootLeft.left;
currentNode.right = rootLeft.right;
currentNode.nodeKey = temp;
// 修正parent引用
if (currentNode.left != null) {
currentNode.left.parent = currentNode;
}
if (currentNode.right != null) {
currentNode.right.parent = currentNode;
}
System.out.print("
case2 delete: " + key);
}
// 对于第三种情形，待删除节点只有右子树，用待删除节点的右子树替换待删除节点即可
else if (currentNode.left == null) {
BsTreeNode<T> rootRight = currentNode.right;
T temp = rootRight.nodeKey;
currentNode.left = rootRight.left;
currentNode.right = rootRight.right;
currentNode.nodeKey = temp;
// 修正parent引用
if (currentNode.left != null) {
currentNode.left.parent = currentNode;
}
if (currentNode.right != null) {
currentNode.right.parent = currentNode;
}
System.out.print("
case3 delete: " + key);
}
/**
* 第四种情形，左右子树都不为空，用待删除节点的直接前驱（或直接后继）
* 来代替待删除节点，同时在二叉排序树中对其直接前驱（或直接后继）做
* 删除操作
*/
else {
// 找到当前节点的的中序前驱节点
BsTreeNode<T> node = currentNode.left;
while (node.right != null) {
node = node.right;
}
// 节点内容替换
currentNode.nodeKey = node.nodeKey;
// 删除前驱节点
deleteRecursively(node, node.nodeKey);
System.out.print("
case4 delete: " + key);
}
}
}
}
class BsTreeNode<T extends Comparable<T>> {
/**
* 关键字（键值）
*/
T nodeKey;
/**
* 左节点引用
*/
BsTreeNode<T> left;
/**
* 右节点引用
*/
BsTreeNode<T> right;
/**
* 父节点引用，进行节点删除的时候会用到
*/
BsTreeNode<T> parent;
public BsTreeNode(T value) {
this.nodeKey = value;
}
public BsTreeNode() {
}
@Override
public String toString() {
return nodeKey.toString();
}
}
红黑树代码
RbTreeTest.java
package rbt;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public class RbTreeTest {
public static void main(String[] args) {
// 随机数的上限
int bound = 1000000000;
// 随机序列的长度
int seqLen = 100000;
// 随机数生成器
Random random = new Random();
// 根节点值
int rootValue = random.nextInt(bound);
// 随机序列容器
List<Integer> intSeq = new ArrayList<>();
intSeq.add(rootValue);
// 往随机序列容器中添加随机值
while (intSeq.size() < seqLen) {
int rand = random.nextInt(bound);
intSeq.add(rand);
}
System.out.println("压测开始，节点数量：" + seqLen);
System.out.println("插入序列：" + intSeq);
// 创建一个rbt
RbTree<Integer> rbTree = new RbTree<>();
// 把intSeq中的随机数全部插入进去，测试节点插入过程
for (Integer key : intSeq) {
rbTree.insert(key);
}
// 插入完成后，打印整个rbt的中序遍历结果，验证是否符合二叉搜索树的特性
List<Integer> middleOderOutput1 = new LinkedList<>();
rbTree.inOrder(middleOderOutput1);
System.out.println("
插入完成，中序遍历结果为：" + middleOderOutput1);
System.out.println();
// 打印整个rbt的形状
rbTree.printTree();
System.out.println();
// 打印根节点到每个叶子节点的路径中，黑节点的数量，验证bst是否符合黑节点完美平衡特性
List<RbTreeNode<Integer>> linkedList = new LinkedList<>();
System.out.println();
rbTree.printAllRootToLeafPaths(linkedList);
System.out.println();
// 选取一部分节点值，测试节点删除过程
List<Integer> delList = middleOderOutput1.subList(middleOderOutput1.size() / 4, middleOderOutput1.size() / 2);
System.out.println("
删除序列：" + delList);
for (Integer key : delList) {
rbTree.remove(key);
}
List<Integer> middleOderOutput2 = new LinkedList<>();
rbTree.inOrder(middleOderOutput2);
System.out.println("
删除完成，中序遍历结果为：" + middleOderOutput2);
System.out.println();
// 打印整个rbt的形状
rbTree.printTree();
System.out.println();
// 打印根节点到每个叶子节点的路径中，黑节点的数量，验证bst是否符合黑节点完美平衡特性
List<RbTreeNode<Integer>> linkedList2 = new LinkedList<>();
System.out.println();
rbTree.printAllRootToLeafPaths(linkedList2);
System.out.println();
// 测试rbt中“删除前总节点数目 - 删除节点数目 = 删除后总节点数目”是否成立
System.out.println("
(out1.size() - out2.size()) == delList.size()? " + ((middleOderOutput1.size() - middleOderOutput2.size()) == delList.size()));
// 测试rbt中“删除前节点 包含全部 删除后节点”是否成立
System.out.println("out1.containsAll(out2)? " + (middleOderOutput1.containsAll(middleOderOutput2)));
// 测试rbt中“删除前节点 包含全部 被删除节点”是否成立
System.out.println("out1.containsAll(delList)? " + (middleOderOutput1.containsAll(delList)));
}
}
RbTree.java
package rbt;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class RbTree<T extends Comparable<T>> {
/**
* 根结点
*/
private RbTreeNode<T> mRoot;
private static final boolean RED = false;
private static final boolean BLACK = true;
public RbTree() {
mRoot = null;
}
/**
* 获取某个节点的父节点
*
* @param node
* @return
*/
private RbTreeNode<T> parentOf(RbTreeNode<T> node) {
return node != null ? node.parent : null;
}
/**
* 获取某个节点的颜色
*
* @param node
* @return
*/
private boolean colorOf(RbTreeNode<T> node) {
return node != null ? node.color : BLACK;
}
/**
* 判断某个节点是否为红色
*
* @param node
* @return
*/
private boolean isRed(RbTreeNode<T> node) {
return ((node != null) && (node.color == RED)) ? true : false;
}
/**
* 判断某个节点是否为黑色
*
* @param node
* @return
*/
private boolean isBlack(RbTreeNode<T> node) {
return !isRed(node);
}
/**
* 设置某个节点为黑色
*
* @param node
*/
private void setBlack(RbTreeNode<T> node) {
if (node != null) {
node.color = BLACK;
}
}
/**
* 设置某个节点为红色
*
* @param node
*/
private void setRed(RbTreeNode<T> node) {
if (node != null) {
node.color = RED;
}
}
/**
* 设置某个节点的父节点
*
* @param node
* @param parent
*/
private void setParent(RbTreeNode<T> node, RbTreeNode<T> parent) {
if (node != null) {
node.parent = parent;
}
}
/**
* 设置某个节点的颜色
*
* @param node
* @param color
*/
private void setColor(RbTreeNode<T> node, boolean color) {
if (node != null) {
node.color = color;
}
}
public void preOrder() {
preOrder(mRoot);
}
/**
* 前序遍历红黑树
*
* @param tree
*/
private void preOrder(RbTreeNode<T> tree) {
if (tree != null) {
System.out.print(tree.nodeKey + "->");
preOrder(tree.left);
preOrder(tree.right);
}
}
/**
* 中序遍历红黑树
*
* @param tree
* @param collection 用于记录遍历的过程
*/
private void inOrder(RbTreeNode<T> tree, Collection<T> collection) {
if (tree != null) {
inOrder(tree.left, collection);
//System.out.print(tree.nodeKey + "->");
collection.add(tree.nodeKey);
// 用于验证节点是否符合“如果一个节点是红色的，则它的子节点必须是黑色的”
if (tree.color == RED) {
if (tree.left != null && tree.left.color == RED) {
System.out.print("
该节点违反红黑树特性！！！
");
}
if (tree.right != null && tree.right.color == RED) {
System.out.print("
该节点违反红黑树特性！！！
");
}
}
inOrder(tree.right, collection);
}
}
public void inOrder(Collection<T> collection) {
inOrder(mRoot, collection);
}
/**
* 后序遍历红黑树
*
* @param tree
*/
private void postOrder(RbTreeNode<T> tree) {
if (tree != null) {
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.nodeKey + "->");
}
}
public void printAllRootToLeafPaths(List<RbTreeNode<T>> path) {
printAllRootToLeafPaths(mRoot, path);
}
/**
* 打印节点root到每个叶子节点（Nil）的路径上的黑节点个数
*
* @param root
* @param path
*/
public void printAllRootToLeafPaths(RbTreeNode<T> root, List<RbTreeNode<T>> path) {
if (root == null) {
return;
}
path.add(root);
if (root.left == null && root.right == null) {
path = path.stream().filter(e -> e.color).collect(Collectors.toList());
//System.out.println("当前路径的黑节点数量：" + path.size());
System.out.print("->" + path.size());
return;
} else {
printAllRootToLeafPaths(root.left, new LinkedList<>(path));
printAllRootToLeafPaths(root.right, new LinkedList<>(path));
}
}
public void printTree() {
printTree(mRoot);
}
/**
* 打印红黑树每一层的节点，格式为：
* 当前节点键值（当前节点的颜色 父节点键值 是父节点的左孩子还是右孩子）
* 例如：1905(B 1971 L)
*
* @param root
*/
public void printTree(RbTreeNode<T> root) {
java.util.LinkedList<RbTreeNode<T>> queue = new java.util.LinkedList<RbTreeNode<T>>();
java.util.LinkedList<RbTreeNode<T>> queue2 = new java.util.LinkedList<RbTreeNode<T>>();
if (root == null) {
return;
}
queue.add(root);
boolean firstQueue = true;
while (!queue.isEmpty() || !queue2.isEmpty()) {
java.util.LinkedList<RbTreeNode<T>> q = firstQueue ? queue : queue2;
RbTreeNode<T> n = q.poll();
if (n != null) {
String pos = n.parent == null ? "" : (n == n.parent.left
? " L" : " R");
String pstr = n.parent == null ? "" : n.parent.toString();
String cstr = n.color ? "B" : "R";
cstr = n.parent == null ? cstr : cstr + " ";
System.out.print(n + "(" + (cstr) + pstr + (pos) + ")" + " ");
if (n.left != null) {
(firstQueue ? queue2 : queue).add(n.left);
}
if (n.right != null) {
(firstQueue ? queue2 : queue).add(n.right);
}
} else {
System.out.println();
firstQueue = !firstQueue;
}
}
}
/**
* （递归实现）查找红黑树中键值为nodeKey的节点
*
* @param root
* @param nodeKey
* @return
*/
private RbTreeNode<T> searchRecursively(RbTreeNode<T> root, T nodeKey) {
if (root == null) {
return root;
}
int cmp = nodeKey.compareTo(root.nodeKey);
if (cmp < 0) {
return searchRecursively(root.left, nodeKey);
} else if (cmp > 0) {
return searchRecursively(root.right, nodeKey);
} else {
return root;
}
}
/**
* 左旋：以某个结点P作为支点(旋转结点)，其右子结点V变为
* 旋转结点P的父结点，右子结点V的左子结点R变为旋转结点
* P的右子结点，左子结点F保持不变。
*
* @param pNode 支点(旋转结点)
*/
private void leftRotate(RbTreeNode<T> pNode) {
// P的右子结点V的左子结点R变为旋转结点P的右子结点
RbTreeNode<T> vNode = pNode.right;
RbTreeNode<T> rNode = vNode.left;
pNode.right = rNode;
// 修正R的parent为P
if (rNode != null) {
rNode.parent = pNode;
}
// 修正V的parent为P原来的parent
vNode.parent = pNode.parent;
if (pNode.parent == null) {
// 如果P原来就没有parent，说明P原来就是根节点。现
// 在V要变成P的parent，则新的根节点要更新为V
this.mRoot = vNode;
} else {
// 如果P原来就有parent，则V取代P作为这个parent的左
// 孩子或右孩子
if (pNode.parent.left == pNode) {
pNode.parent.left = vNode;
} else {
pNode.parent.right = vNode;
}
}
// 旋转结点P变为结点V的左孩子
vNode.left = pNode;
// 结点V变为旋转结点P的父结点
pNode.parent = vNode;
}
/**
* 右旋：以某个结点P作为支点(旋转结点)，其左子结点F变为
* 旋转结点P的父结点，左子结点F的右子结点K变为旋转结点
* P的左子结点，右子结点V保持不变。
*
* @param pNode
*/
private void rightRotate(RbTreeNode<T> pNode) {
// P的左子结点F的右子结点K变为旋转结点P的左子结点
RbTreeNode<T> fNode = pNode.left;
RbTreeNode<T> kNode = fNode.right;
pNode.left = kNode;
// 修正K的parent为P
if (kNode != null) {
kNode.parent = pNode;
}
// 修正F的parent为P原来的parent
fNode.parent = pNode.parent;
if (pNode.parent == null) {
// 如果P原来就没有parent，说明P原来就是根节点。现
// 在F要变成P的parent，则新的根节点要更新为F
this.mRoot = fNode;
} else {
// 如果P原来就有parent，则F取代P作为这个parent的左
// 孩子或右孩子
if (pNode == pNode.parent.right) {
pNode.parent.right = fNode;
} else {
pNode.parent.left = fNode;
}
}
// 旋转结点P变为结点F的右孩子
fNode.right = pNode;
// 结点F变为旋转结点P的父结点
pNode.parent = fNode;
}
/**
* 红黑树插入修正函数
*
* @param currentNode
*/
private void insertFixUp(RbTreeNode<T> currentNode) {
RbTreeNode<T> parent;
RbTreeNode<T> gparent;
// INSERT-FIXUP-CASE-3：当前节点的父节点存在，并且父节点的颜色是红色
while (((parent = parentOf(currentNode)) != null) && isRed(parent)) {
gparent = parentOf(parent);
// 若当前节点的父节点是祖父节点的左孩子
if (parent == gparent.left) {
// INSERT-FIXUP-CASE-3.1：当前节点的叔叔节点是红色
RbTreeNode<T> uncle = gparent.right;
if ((uncle != null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
currentNode = gparent;
continue;
}
// INSERT-FIXUP-CASE-3.2：当前节点的叔叔节点是黑色，且当前节点是右孩子
if (parent.right == currentNode) {
RbTreeNode<T> tmp;
leftRotate(parent);
tmp = parent;
parent = currentNode;
currentNode = tmp;
}
// INSERT-FIXUP-CASE-3.3：当前节点的叔叔节点是黑色，且当前节点是左孩子
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
}
// 若当前节点的父节点是祖父节点的右孩子
else {
// INSERT-FIXUP-CASE-3.1：当前节点的叔叔节点是红色
RbTreeNode<T> uncle = gparent.left;
if ((uncle != null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
currentNode = gparent;
continue;
}
// INSERT-FIXUP-CASE-3.2：当前节点的叔叔节点是黑色，且当前节点是左孩子
if (parent.left == currentNode) {
RbTreeNode<T> tmp;
rightRotate(parent);
tmp = parent;
parent = currentNode;
currentNode = tmp;
}
// INSERT-FIXUP-CASE-3.3：当前节点的叔叔节点是黑色，且当前节点是右孩子
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// INSERT-FIXUP-CASE-1：被插入的节点是根节点，将根节点设为黑色
if (currentNode == mRoot) {
setBlack(this.mRoot);
return;
}
// INSERT-FIXUP-CASE-2：被插入的节点的父节点是黑色，什么也不需要做
if (parentOf(currentNode) != null && isBlack(parentOf(currentNode))) {
// DO-NOTHONG
return;
}
}
/**
* （递归实现）将结点插入到红黑树中
*
* @param root
* @param nodeInserted
* @return
*/
public boolean insertRecursively(RbTreeNode<T> root,
RbTreeNode<T> nodeInserted) {
if (root == null) {
mRoot = nodeInserted;
return true;
}
if (root.nodeKey.compareTo(nodeInserted.nodeKey) > 0) {
if (root.left == null) {
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中
root.left = nodeInserted;
nodeInserted.parent = root;
// 2. 设置节点的颜色为红色
nodeInserted.color = RED;
// 3. 通过旋转和变色将它重新修正为一颗二叉查找树
insertFixUp(nodeInserted);
return true;
} else {
// 向左子树中递归操作
return insertRecursively(root.left, nodeInserted);
}
} else if (root.nodeKey.compareTo(nodeInserted.nodeKey) < 0) {
if (root.right == null) {
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中
root.right = nodeInserted;
nodeInserted.parent = root;
// 2. 设置节点的颜色为红色
nodeInserted.color = RED;
// 3. 通过旋转和变色将它重新修正为一颗二叉查找树
insertFixUp(nodeInserted);
return true;
} else {
// 向右子树中递归操作
return insertRecursively(root.right, nodeInserted);
}
} else {
return false;
}
}
/*
* 新建结点(nodeKey)，并将其插入到红黑树中
*
* 参数说明：
* nodeKey 插入结点的键值
*/
public void insert(T nodeKey) {
RbTreeNode<T> node = new RbTreeNode<T>(nodeKey, BLACK, null, null, null);
// 如果新建结点失败，则返回
if (node != null) {
insertRecursively(mRoot, node);
}
}
/**
* 红黑树删除修正函数
* @param childOfNodeRemoved
* @param parentOfNodeRemoved
*/
private void removeFixUp(RbTreeNode<T> childOfNodeRemoved,
RbTreeNode<T> parentOfNodeRemoved) {
// other是childOfNodeRemoved的兄弟节点
RbTreeNode<T> other;
// REMOVE-FIXUP-CASE-3: childOfNodeRemoved是“黑+黑”节点，
// 且childOfNodeRemoved不是根
while ((childOfNodeRemoved == null || isBlack(childOfNodeRemoved))
&& (childOfNodeRemoved != this.mRoot)) {
if (parentOfNodeRemoved.left == childOfNodeRemoved) {
other = parentOfNodeRemoved.right;
if (isRed(other)) {
// REMOVE-FIXUP-CASE-3.1: childOfNodeRemoved的兄弟
// other是红色
setBlack(other);
setRed(parentOfNodeRemoved);
leftRotate(parentOfNodeRemoved);
other = parentOfNodeRemoved.right;
}
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))) {
// REMOVE-FIXUP-CASE-3.2: childOfNodeRemoved的兄弟
// other是黑色，且other的两个孩子也都是黑色
setRed(other);
childOfNodeRemoved = parentOfNodeRemoved;
parentOfNodeRemoved = parentOf(childOfNodeRemoved);
} else {
if (other.right == null || isBlack(other.right)) {
// REMOVE-FIXUP-CASE-3.3: childOfNodeRemoved的兄弟
// other是黑色，并且other的左孩子是红色，右孩子是黑色
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parentOfNodeRemoved.right;
}
// REMOVE-FIXUP-CASE-3.4: childOfNodeRemoved的兄弟other
// 是黑色，并且other的右孩子是红色，左孩子是任意颜色
setColor(other, colorOf(parentOfNodeRemoved));
setBlack(parentOfNodeRemoved);
setBlack(other.right);
leftRotate(parentOfNodeRemoved);
childOfNodeRemoved = this.mRoot;
break;
}
} else {
other = parentOfNodeRemoved.left;
if (isRed(other)) {
// REMOVE-FIXUP-CASE-3.1: childOfNodeRemoved的兄弟
// other是红色
setBlack(other);
setRed(parentOfNodeRemoved);
rightRotate(parentOfNodeRemoved);
other = parentOfNodeRemoved.left;
}
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))) {
// REMOVE-FIXUP-CASE-3.2: childOfNodeRemoved的兄弟
// other是黑色，且other的两个孩子也都是黑色
setRed(other);
childOfNodeRemoved = parentOfNodeRemoved;
parentOfNodeRemoved = parentOf(childOfNodeRemoved);
} else {
if (other.left == null || isBlack(other.left)) {
// REMOVE-FIXUP-CASE-3.3: childOfNodeRemoved的兄弟
// other是黑色，并且other的左孩子是红色，右孩子是黑色
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parentOfNodeRemoved.left;
}
// REMOVE-FIXUP-CASE-3.4: childOfNodeRemoved的兄弟other
// 是黑色，并且other的右孩子是红色，左孩子是任意颜色
setColor(other, colorOf(parentOfNodeRemoved));
setBlack(parentOfNodeRemoved);
setBlack(other.left);
rightRotate(parentOfNodeRemoved);
childOfNodeRemoved = this.mRoot;
break;
}
}
}
// REMOVE-FIXUP-CASE-1：childOfNodeRemoved是“红+黑”节点 ，
// 直接把childOfNodeRemoved设为黑色
if (childOfNodeRemoved != null && isRed(childOfNodeRemoved)) {
setBlack(childOfNodeRemoved);
return;
}
// REMOVE-FIXUP-CASE-2：childOfNodeRemoved是“黑+黑”节点，
// 且childOfNodeRemoved是根，什么都不做
if (childOfNodeRemoved != null && isBlack(childOfNodeRemoved)
&& childOfNodeRemoved == this.mRoot) {
// DO-NOTHING
return;
}
}
/**
* 删除结点
*
* @param nodeRemoved
*/
private void remove(RbTreeNode<T> nodeRemoved) {
// 被删除节点的左右孩子都不为空的情况
if ((nodeRemoved.left != null) && (nodeRemoved.right != null)) {
removeNodeWithDoubleChild(nodeRemoved);
}
// 被删除节点的左孩子不为空的情况
else if (nodeRemoved.left != null) {
removeNodeWithOnlyLeftChild(nodeRemoved);
}
// 被删除节点的右孩子不为空的情况
else if (nodeRemoved.right != null) {
removeNodeWithOnlyRightChild(nodeRemoved);
}
// 被删除节点的左右孩子都为空的情况
else {
removeNodeWithNoChild(nodeRemoved);
}
}
/**
* 被刪除节点的左右子树均不存在，直接删掉该节点即可
*
* @param nodeRemoved
*/
private void removeNodeWithNoChild(RbTreeNode<T> nodeRemoved) {
RbTreeNode<T> childOfNodeRemoved;
RbTreeNode<T> parenOfNodeRemoved;
boolean colorOfNodeRemoved;
childOfNodeRemoved = null;
parenOfNodeRemoved = nodeRemoved.parent;
colorOfNodeRemoved = nodeRemoved.color;
// 被删除节点不是根节点（根节点不存在父节点）
if (parentOf(nodeRemoved) != null) {
if (parentOf(nodeRemoved).left == nodeRemoved) {
parentOf(nodeRemoved).left = childOfNodeRemoved;
} else {
parentOf(nodeRemoved).right = childOfNodeRemoved;
}
} else {
// 被删除节点是根节点，更新根节点
this.mRoot = childOfNodeRemoved;
}
// 刪除修正
if (colorOfNodeRemoved == BLACK) {
removeFixUp(childOfNodeRemoved, parenOfNodeRemoved);
}
return;
}
/**
* 被删除节点只有右子树，用被删除节点的右子树替换被删除节点即可
*
* @param nodeRemoved
*/
private void removeNodeWithOnlyRightChild(RbTreeNode<T> nodeRemoved) {
RbTreeNode<T> childOfNodeRemoved;
RbTreeNode<T> parenOfNodeRemoved;
boolean colorOfNodeRemoved;
childOfNodeRemoved = nodeRemoved.right;
parenOfNodeRemoved = nodeRemoved.parent;
colorOfNodeRemoved = nodeRemoved.color;
childOfNodeRemoved.parent = parenOfNodeRemoved;
// 被删除节点不是根节点（根节点不存在父节点）
if (parentOf(nodeRemoved) != null) {
if (parentOf(nodeRemoved).left == nodeRemoved) {
parentOf(nodeRemoved).left = childOfNodeRemoved;
} else {
parentOf(nodeRemoved).right = childOfNodeRemoved;
}
} else {
// 被删除节点是根节点，更新根节点
this.mRoot = childOfNodeRemoved;
}
// 刪除修正
if (colorOfNodeRemoved == BLACK) {
removeFixUp(childOfNodeRemoved, parenOfNodeRemoved);
}
return;
}
/**
* 被删除节点只有左子树，用被删除节点的左子树替换被删除节点即可
*
* @param nodeRemoved
*/
private void removeNodeWithOnlyLeftChild(RbTreeNode<T> nodeRemoved) {
RbTreeNode<T> childOfNodeRemoved;
RbTreeNode<T> parenOfNodeRemoved;
boolean colorOfNodeRemoved;
childOfNodeRemoved = nodeRemoved.left;
parenOfNodeRemoved = nodeRemoved.parent;
colorOfNodeRemoved = nodeRemoved.color;
childOfNodeRemoved.parent = parenOfNodeRemoved;
// 被删除节点不是根节点（根节点不存在父节点）
if (parentOf(nodeRemoved) != null) {
if (parentOf(nodeRemoved).left == nodeRemoved) {
parentOf(nodeRemoved).left = childOfNodeRemoved;
} else {
parentOf(nodeRemoved).right = childOfNodeRemoved;
}
} else {
// 被删除节点是根节点，更新根节点
this.mRoot = childOfNodeRemoved;
}
// 刪除修正
if (colorOfNodeRemoved == BLACK) {
removeFixUp(childOfNodeRemoved, parenOfNodeRemoved);
}
return;
}
/**
* 被删除节点的左右孩子都不为空的情况，用被删除节点的直接前驱
* （或直接后继）来代替被删除节点，同时在二叉排序树中对其直接
* 前驱（或直接后继）做删除操作。这里针对后继节点进行操作。
*
* @param nodeRemoved
*/
private void removeNodeWithDoubleChild(RbTreeNode<T> nodeRemoved) {
// 找到当前节点的的中序后继节点，称为取代节点
RbTreeNode<T> replace = nodeRemoved.right;
while (replace.left != null) {
replace = replace.left;
}
// 拷贝替代节点的内容到被删除节点（这里只拷贝nodeKey，实际上一个
// 节点除了有nodeKey域，还有nodeData域，只不过我们简化了节点定
// 义，拷贝过程应该连同nodeData一起拷贝）
nodeRemoved.nodeKey = replace.nodeKey;
// 然后删除替代节点
remove(replace);
return;
}
/**
* 删除键值为nodeKey的结点
*
* @param nodeKey
*/
public void remove(T nodeKey) {
RbTreeNode<T> node;
if ((node = searchRecursively(mRoot, nodeKey)) != null) {
remove(node);
}
}
}
class RbTreeNode<T extends Comparable<T>> {
/**
* 颜色，黑-true / 红-false
*/
boolean color;
/**
* 关键字（键值）
*/
T nodeKey;
/**
* 左孩子
*/
RbTreeNode<T> left;
/**
* 右孩子
*/
RbTreeNode<T> right;
/**
* 父结点
*/
RbTreeNode<T> parent;
public RbTreeNode() {
}
public RbTreeNode(
T nodeKey, boolean color, RbTreeNode<T> parent,
RbTreeNode<T> left, RbTreeNode<T> right) {
this.nodeKey = nodeKey;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return nodeKey.toString();
}
}