【tree】红黑树（下）

2024-03-23 11:23:34

本文目录

一、基本概念
- 红黑树的定义
- NIL叶节点的讨论
  - 引用值为null
  - 引用值为特殊节点NIL
二、删除节点
- 删除逻辑
- fixup逻辑
  - fixup原则
  - fixup原理
    - 进入fixup的条件
    - fixup的入参（fixup的起点）依赖于NIL的实现方式
    - fixup的逻辑
  - fixup源码：fixupAfterDelete(node)
三、源码及测试
- 源码
- 测试和分析

系列目录

《树》
《树的遍历》
《二叉查找树》
《AVL》
《红黑树（上）》
《红黑树（下）》
《B树》
《B+树》
《大顶堆、小顶堆》

一、基本概念

1、红黑树的定义

红黑树：首先是一颗二叉查找树，其次对于树中的任意一个节点，都满足以下5个性质

节点颜色不是红色就是黑色；
根节点黑色；
叶节点黑色（NIL节点）；（这条性质需要讨论一下）
红节点只能有黑孩子；
对于所有的叶节点，其高度路径上都拥有相同数量的黑色节点；

二叉查找树的定义，见第三篇博客《二叉查找树》。

2.NIL节点

红黑树的五个性质中，NIL节点的规定一直不好理解。

NIL节点：如果一个节点没有子节点或父节点，则该节点相应的指针属性的值为NIL，我们把这些NIL视为指向红黑树叶节点的指针（外部节点），而把带关键字的节点视为树的内部节点。

在树的一般定义中，如果一个节点没有孩子，那么这个节点就被视为叶节点。

但是在红黑树中不一样：

A.引用值为null：如果一个节点的孩子或父亲值为null，那么这个值为null的孩子或父亲就被视为NIL叶节点；
B.引用值为特殊节点NIL：或者你也可以理解成有一个特殊的节点NIL，如果一个节点没有孩子或父亲（值为null），那么就把孩子节点或父节点的引用指向一个特殊的节点，这个特殊的节点就叫NIL。

以上两种理解都可以实现红黑树，其中引用值为null是JDK中TreeMap的实现采用的方式，而引用值为特殊节点NIL是《算法导论》中讲解红黑树采用的方式。

A.引用值为null

这也是本文借鉴JDK中TreeMap的源码而采用的实现方式。

在具体的代码实现中，逻辑是这样的：如果节点为空，则返回黑色，否则返回节点的颜色。

实现代码如下：

	private static final boolean RED = true;
	private static final boolean BLACK = false;

    /**
	 * 返回节点颜色：如果是节点为null（NIL节点），则返回黑色，否则返回节点颜色
	 * @param node
	 * @return RED=true，BLACK=false，节点默认为红色
	 */
	private boolean color(Node<K, V> node) {
		return Objects.isNull(node) ? BLACK : node.color;
	}

B.引用值为特殊节点NIL

当然你也可以定义一个黑色的静态节点NIL，默认赋值给class Node的parent、left、right属性，或者在构造函数中赋值给parent、left、right。

《算法导论》中图示如下：

二、删除节点

1.删除逻辑

红黑树首先是一颗二叉查找树，所以红黑树的删除逻辑和二叉查找树基本保持一致；红黑树和AVL树都属于自平衡二叉树，所以也会像AVL树一样，在最后还需要判断删除操作是否违反了红黑树的性质。

删除逻辑：从根结点出发

如果查找key小于节点key，则向左走；
如果查找key大于节点key，则向右走；
如果查找key等于节点key，则说明该节点即为待删除结点，此时有两种情况：
- 待删除结点有两个孩子：这种情形，为了保证二叉排序树的顺序性（即大于左孩子小于右孩子），需要从左子树或右子树中找一个最接近待删除节点的节点来替换它，即左子树的最大节点或右子树的最小节点
  - 左子树的最大节点，即左子树的最右节点
  - 右子树的最小节点，即右子树的最左节点（本文选择的实现方式）
- 待删除结点最多只有一个孩子：直接让子节点代替删除节点的位置
如果查找到最后一个不为null的节点还没找到，则直接返回；
最后从实际删掉的节点的后继节点开始判断，判断删除操作是否违反了红黑树的性质，如果违反则需要fixup来修复；

注意加粗标红的这一段文字，如果删除操作破坏了红黑树的性质，那么fixup的起点是实际删除节点的后继节点。

什么是“实际删除节点”？要怎么理解“实际删除节点”这个概念？

回看删除逻辑中标绿的这一段（即当查找key相等进入删除操作），有两种情况：

待删除节点有两个孩子；
待删除节点最多有一个孩子；

当待删除节点最多有一个孩子，直接让待删除结点的后继节点替换其位置，因此实际从树种摘掉的节点就是待删除结点，所以这种情形待删除节点就是实际删除节点。

当待删除结点有两个孩子，我们找右子树的最左节点来替换待删除结点，这时候只需要把右子树最左节点的key-value覆盖待删除结点的key-value，然后从树中摘除右子树最左节点即可，所以这种情形实际删除节点是右子树最左节点。此时，右子树的最左节点要么是一个叶子节点，要么最多有一个右孩子，一定不会有左孩子、更不会有两个孩子。所以替换key-value的方式，将两个孩子的case最终转换为最多有一个孩子的情况。

至于在remove操作时，this.root的引用逻辑，相对就比较简单了：

如果待删除节点是叶子节点且是根节点：this.root = null;
如果待删除节点是分支节点但只有一个孩子：this.root指向其后继节点；
如果待删除结点是分支节点且有两个孩子：this.root不变，因为我们的实现是找到右子树的最左节点，然后将右子树最左节点的key-value拷贝替换待删除节点的key-value，最后实际摘掉的是带删除节点右子树的最左节点，根节点除了替换key-value，其他组织结构保持不变；

实现代码如下，其中selectNode方法源码和介绍在《红黑树（上）》中查询节点部分给出，删除节点的修复逻辑fixupAfterDelete方法我们在后一节展“fixup逻辑”中开分析：

	/**
	 * 删除节点，分成两种情况，需要找到实际删除的节点realDelNode
	 * 1.待删除结点最多有一个孩子：这种情况下，待删除节点就是实际删除的节点
	 * 2.待删除节点有两个孩子：这种情况下，实际删除的节点是待删除结点右子树的最左节点
	 * 所以，无论待删除结点是最多一个孩子还是两个孩子，最终都转换为最多一个孩子的形式
	 * 当实际删除节点是一个黑节点的时候，破坏了红黑树的性质5，此时需要fixup。
	 * fixup的起点是realDelNode的后继节点，所以还需要进一步考虑readDelNode是否有后继的问题。
	 * 根据上面删除的讨论，最终实际删除的节点realDelNode最多有一个孩子：
	 * 1.如果realDelNode是非叶子节点，那么fixupNode就是实际删除节点的唯一孩子
	 * 2.如果realDelNode是叶子节点，那么fixupNode就是realDelNode（把realDelNode假想成一个NIL节点），做完fixup之后再摘掉这个实际需要删除的叶子节点
	 * @param key
	 */
	public void remove(K key) {
		if (Objects.isNull(key))
			throw new NullPointerException();
		Node<K, V> deleteNode = selectNode(key);
		// 树中不存在要删除的节点
		if (Objects.isNull(deleteNode) || key.compareTo(deleteNode.key) != 0)
			return;
		/*
		 * 如果待删除节点有两个孩子，那么实际删除的节点是其右子树的最左节点
		 * 所以我们将其右子树最左节点的KV拷贝覆盖待删除结点的KV，然后deleteNode指向右子树最左节点
		 * 这样一来，两个孩子的情形就转换成了最多一个孩子的形式
		 */
		if (Objects.nonNull(deleteNode.leftChild) && Objects.nonNull(deleteNode.rightChild)) {
			Node<K, V> realDelNode = findMin(deleteNode.rightChild);
			deleteNode.key = realDelNode.key;
			deleteNode.value = realDelNode.value;
			deleteNode = realDelNode;
		}
		// 到这里，deleteNode全部转换成最多一个孩子的情形
		/*
		 * 接下来要考虑deleteNode是否是叶子节点：
		 * 1.如果非叶子，其孩子节点需要覆盖删除deleteNode，则fixupNode为其孩子节点
		 * 2.否则deleteNode作为叶子节点，fixupNode就是deleteNode，做完fixup之后再摘掉该节点
		 */
		Node<K, V> fixupNode = Objects.nonNull(deleteNode.leftChild) ? deleteNode.leftChild : deleteNode.rightChild;
		if (Objects.nonNull(fixupNode)) {
			// 非叶子，后继节点替代deleteNode
			fixupNode.parent = deleteNode.parent;
			if (Objects.nonNull(deleteNode.parent)) {
				if (deleteNode.equals(deleteNode.parent.leftChild))
					deleteNode.parent.leftChild = fixupNode;
				else
					deleteNode.parent.rightChild = fixupNode;
			} else
				// 实际删除节点是分支节点但只有一个孩子时，this.root指向替换它的后继节点
				this.root = fixupNode;
			deleteNode.parent = deleteNode.leftChild = deleteNode.rightChild = null;
			// 对于实际删除节点有后继节点的情况，fixup的起点是替换deleteNode的后继节点fixupNode
			if (!deleteNode.color)
				fixupAfterDelete(fixupNode);
		} else {
			// 实际删除节点是一个叶节点且是根节点，this.root = null并返回
			if (Objects.isNull(deleteNode.parent)) {
				this.root = null;
				return;
			}
			// 对于实际删除节点没有后继节点的情况，先将deleteNode看作NIL节点做fixup，之后再摘掉
			// fixup中修复的4个case都不会将其变为分支节点，始终是叶子节点
			if (!deleteNode.color)
				fixupAfterDelete(deleteNode);
			if (Objects.nonNull(deleteNode.parent)) {
				if (deleteNode.equals(deleteNode.parent.leftChild))
					deleteNode.parent.leftChild = null;
				else
					deleteNode.parent.rightChild = null;
				deleteNode.parent = null;
			}
		}
	}

经过二叉查找树的删除逻辑，最后还需要判断删除操作是否违反了红黑树的性质，如果违反则需要fixup。

2.fixup逻辑

A.fixup原则

insert和remove操作都会破坏红黑树的性质，两者都遵循相同的修复原则。

红黑树fixup的原则如下：

基本操作：变色和旋转；
操作原则：
1. 尽量在子树内通过基本操作（变色+旋转）修复问题；
2. 如果无法在子树内修复问题，那需要将问题向上回溯直至根节点；

其中变色即修改node.color属性，实现代码如下：

	/**
	 * 防止空指针
	 * @param node
	 * @param color
	 */
	private void setColor(Node<K, V> node, boolean color) {
		if (Objects.nonNull(node))
			node.color = color;
	}

旋转和AVL树一致，分为左旋和右旋，其中入参node为需要旋转的子树的根节点，实现代码如下：

	/**
	 * 向左旋转，需要处理三处总六条关系
	 * @param node 需要旋转的子树的根节点
	 */
	private void rotateLeft(Node<K, V> node) {
		if (Objects.nonNull(node)) {
			Node<K, V> newRoot = node.rightChild;
			// 第一处，处理node.right指向newRoot.left的关系
			node.rightChild = newRoot.leftChild;
			if (Objects.nonNull(newRoot.leftChild))
				newRoot.leftChild.parent = node;
			// 第二处：处理node.parent指向newRoot的关系
			newRoot.parent = node.parent;
			if (Objects.isNull(node.parent))
				this.root = newRoot;
			else if (node == node.parent.leftChild)
				node.parent.leftChild = newRoot;
			else
				node.parent.rightChild = newRoot;
			// 第三处：处理newRoot指向node的关系
			newRoot.leftChild = node;
			node.parent = newRoot;
		}
	}

	/**
	 * 向右旋转，需要处理三处总六条关系
	 * @param node 需要旋转的子树的根节点
	 */
	private void rotateRight(Node<K, V> node) {
		if (Objects.nonNull(node)) {
			Node<K, V> newRoot = node.leftChild;
			// 第一处：处理node.left指向newRoot.right的关系
			node.leftChild = newRoot.rightChild;
			if (Objects.nonNull(newRoot.rightChild))
				newRoot.rightChild.parent = node;
			// 第二处：处理node.parent指向newRoot的关系
			newRoot.parent = node.parent;
			if (Objects.isNull(node.parent))
				this.root = newRoot;
			else if (node == node.parent.leftChild)
				node.parent.leftChild = newRoot;
			else
				node.parent.rightChild = newRoot;
			// 第三处：处理newRoot指向node的关系
			newRoot.rightChild = node;
			node.parent = newRoot;
		}
	}

B.fixup原理

我们推演一下删除一个node可能出现的10种情形。

删除node的场景：remove(key)在红黑树中定位到待删除结点

1.待删除结点是叶子节点
- 待删除节点是红叶子：直接摘掉，删除成功；
- 待删除结点是黑叶子：删除操作违反了红黑树性质5，需要fixup，fixup后面展开讨论；
2.待删除节点是分支节点，但只有一个孩子
- 待删除结点是红分支：后继替换，删除成功；
- 待删除结点是黑分支：删除操作违反了红黑树性质5，需要fixup
  - 如果其孩子是红节点：孩子变色替换，fixup完成；
  - 如果其孩子是黑节点：fixup后面展开讨论；
3.待删除节点是分支节点，有两个孩子：从上面“删除逻辑”章节的源码和分析可知，两个节点的case最终被转换为本场景种的“1.待删除结点是叶子节点”和“2.待删除结点是分支节点，但只有一个孩子”，待删除结点并没有从树中摘掉，而是将待删除节点右子树的最左孩子的key-value复制替换待删除结点的key-value，实际删除节点是待删除结点右子树的最左孩子
- 实际删除节点是叶节点
  - 实际删除节点是红叶子：直接摘掉，删除成功；
  - 实际删除节点是黑叶子：删除操作违反了红黑树性质5，需要fixup，fixup后面展开讨论；
- 实际删除节点是分支节点，但只有一个孩子
  - 实际删除节点是红分支：后继替换，删除成功；
  - 实际删除节点是黑分支：删除操作违反了红黑树性质5，需要fixup
    - 如果其孩子是红节点：孩子变色替换，fixup完成；
    - 如果其孩子是黑节点：fixup后面展开讨论；
- 实际删除节点是分支节点，有两个孩子：这种情况不会出现，待删除结点右子树的最左节点要么是一个叶节点，要么只有一个孩子且只能是右孩子；

所以，从以上覆盖红黑树删除操作所有10个场景中标红的部分（即需要fixup的场景）可知：

进入fixup的条件：只有当实际删除的节点是黑色节点，才需要fixup；
fixup的入参：fixup的起点是实际删除节点的后继节点；
fixup逻辑：因为删除操作导致该高度路径上的黑色节点数量减一，所以fixup需要在该高度路径上补充一个黑节点
1. 此时如果后继节点是红色，则变色后替换即可修复；
2. 如果后继节点是黑色，我们在下文“实际删除节点的后继节点是黑色场景”中展开讨论；

当实际删除的节点是黑节点时，在remove方法中做判断然后进入fixupAfterDelete做修复：

public void remove(K key) {
    // 省略二叉查找树的删除逻辑
    // 如果实际删除节点是黑色，那么就需要进入fixupAfterDelete进行修复
    if (!deleteNode.color)
		fixupAfterDelete(fixupNode);
}

fixupAfterDelete方法的入参是实际删除节点的后继节点（即fixup的起点是实际删除节点的后继节点）：remove方法的实现将待删除节点有两个孩子的场景转换成了最多一个孩子的场景，所以

如果删除节点是分支节点：因为只有一个孩子，所以fixupAfterDelete(node)的入参node就是其后继节点
如果删除节点是叶子节点：那么fixupAfterDelete(node)的入参node依赖于你对红黑树性质3（NIL叶节点是黑色）的实现方式，你可以回看本文1.2 NIL叶节点的讲解；
- 《算法导论》中性质3（NIL叶节点是黑色）的实现：如果一个节点的父亲、孩子为null，则指向一个特殊的黑节点，这个节点就是T.NIL
  - 所以在《算法导论》的实现中，fixup的入参就是实际删除节点的后继节点，如果实际删除节点是叶子节点，那么它的后继就是T.NIL节点；
- JDK TreeMap中性质3（NIL叶节点是黑色）的实现：如果节点为null则返回黑色，否则返回节点颜色，所以在JDK TreeMap的实现中
  - 实现代码：return Objects.isNull(node) ? BLACK : node.color
  - 如果实际删除节点是分支节点，则fixup入参是实际删除节点的后继节点；
  - 如果实际删除节点是叶子节点，则fixup的入参就是实际删除节点，这里延迟删除节点，而将实际删除节点假想成T.NIL黑节点做fixup，等到fixup之后，再摘掉实际删除节点，fixup不会将叶节点变成非叶节点

《算法导论（第三版）》：

JDK TreeMap源码：

到这里，我们已经讨论了：

进入fixupAfterDelete(node)方法的条件：实际删除节点是黑色，则需要fixup；
fixupAfterDelete(node)方法的入参node：依赖于对红黑树NIL叶节点的实现，但逻辑上都可视为实际删除节点的后继节点；

关于fixupAfterDelete(node)方法，我们还需要讨论该方法中做fixup的逻辑，再回顾一下上文删除node的10个场景：

如果后继节点node是红色，则变成黑色即可修复；
如果后继节点node是黑色，那就比较麻烦了，我们在接下来的“实际删除节点的后继节点node是黑色的场景中”讨论；

实际删除节点的后继节点node是黑色的场景：实际删除节点是黑色，该分支的高度路径上黑色节点数量减一，违反了红黑树的性质5（所有叶节点的高度路径上都有相同数量的黑色节点），fixup的目的是在该高度路径上补充一个黑节点，如果此时实际删除节点的后继节点node也是黑色

注意：下文配图中，黑色节点黑色，灰色节点红色，白色节点可以是黑色也可以是红色
case 1: node的兄弟节点sibling是红色
- 子树情形：node黑色，sibling红色，parent一定是黑色，sibling的两个孩子一定是黑色
- 操作：sibling置黑，parent置红，旋转将sibling变成子树的根节点，node的引用值维持不变，更新node的sibling
- 解释：这种情形无法修复，在摘掉节点的高度路径上的结构是黑色node+黑色parent，这样是没办法在子树中该路径上增加一个黑节点，所以通过变色+旋转将case1转换成case2/3/4
  - 因为sibling红色，所以sibling的两个孩子一定是黑色
  - 旋转之后，sibling其中的一个孩子会变成node的兄弟节点，而这个节点一定是黑色
  - node的sibling是黑色，则属于case 2/3/4之一，具体属于哪一种，要看sibling的两个孩子的情况

case 2: node的兄弟节点sibling是黑色，且sibling的两个孩子也是黑色
- 字数情形：node黑色，sibling黑色，sibling的两个孩子也是黑色
- 操作：sibling置红，node指向parent
- 解释：因为node黑色，sibling黑色，所以parent可以是红色也可以是黑色
  - 前提：node所在路径因为删除操作导致黑色节点减一，此时将sibling置红导致sibling路径的黑色节点数量也减一，意味着parent作为根节点的子树黑色数量减一
  - 如果parent是黑色：此时将node指向parent，相当于将问题向上回溯
  - 如果parent是红色：此时只需要将parent置黑即可修复（parent左右子树的黑色节点数量都加一），所以将node指向parent，再次while循环时发现node红色随即跳出循环，然后setColor(node, BLACK)完成修复

case 3: node的兄弟节点sibling是黑色，sibling非拐点孩子黑色，拐点孩子红色
- 子树情形：node黑色，sibling黑色，parent可以是红色也可以是黑色
  - 如果node是左孩子，则sibling是右孩子，sibling非拐点孩子即sibling.right黑色，sibling拐点孩子即sibling.left红色
  - 如果node是右孩子，则sibling是左孩子，sibling非拐点孩子即sibling.left黑色，sibling拐点孩子即sibling.right红色
- 操作：sibling置红，sibling拐点孩子置黑，以sibling作为子树的根节点发生旋转，消除拐点
- 解释：和case2类似，因为node和sibling都是黑色，所以父节点可以是黑色也可以是红色，但是因为sibling有一个红孩子，所以无法像case2那样通过变色进行修复或将问题向上回溯，而是要想办法把sibling的红孩子补充到node所在的路径（因为删除操作导致该路径上黑节点数量减一），所以sibling置红，sibling拐点的红孩子置黑，旋转之后消除拐点，而不破坏红黑树其他性质，将case3转换成case4

case 4: node的兄弟节点sibling是黑色，非拐点孩子红色（拐点孩子可红可黑）
- 子树情形：node黑色，sibling黑色，parent可以是红色也可以是黑色
  - 如果node是左孩子，则sibling是右孩子，sibling非拐点孩子即sibling.right红色，拐点孩子可以是红色也可以是黑色
  - 如果node是右孩子，则sibling是左孩子，sibling非拐点孩子即sibling.left红色，拐点孩子可以是红色也可以是黑色
- 操作：sibling置parent的颜色，parent置黑，sibling非拐点红孩子置黑，然后旋转将sibling变成子树的根节点，node指向根节点
- 解释：
  - 目的：因为删除操作导致node所在路径的黑色节点数量减一，所以要通过fixup在该路径上增加一个黑节点
  - 如果父节点是黑色：
    - 此时node黑色，parent黑色，sibling黑色，sibling非拐点孩子红色
    - sibling置父节点色还是黑色，父节点置黑还是黑色
    - 将sibling拐点的红孩子置黑，导致sibling路径黑色节点数量加一，然后通过旋转将sibling变成子树新的根节点，这样node路径黑色节点数量加一恢复正常，sibling路径黑色节点数量减一恢复正常
    - fixup后node指向根节点的目的：修复完成，跳出循环结束fixupAfterDelete方法的执行
  - 如果父节点是红色：
    - 此时node黑色，sibling黑色，parent红色，sibling非拐点孩子红色，sibling拐点孩子可能是红色（可以是红色也可以是黑色）
    - sibling置parent的颜色，所以sibling置红，sibling路径黑色节点数量减一，并且sibling和子节点发生双红缺陷
    - parent原来红色现在置黑，sibling路径黑色节点数量加一恢复，node路径黑色节点数量加一恢复
    - sibling非拐点孩子置黑，修复红双缺陷，但是仍旧存在两个问题：sibling路径黑色节点数量又加一，如果sibling拐点孩子红色，那sibling红色，红双问题依旧可能存在
    - 此时再发生旋转，将sibling旋转为子树的根节点，原来黑色的parent旋转到node路径，sibling路径黑色节点数量减一恢复；sibling拐点的孩子变成了原parent的孩子，修复可能存在的红双缺陷
    - 最后node指向根节点的目的：修复完成，跳出循环结束fixupAfterDelete方法的执行

C.fixupAfterDelete源码

	/**
	 * 删掉了一个黑节点，违反了红黑树的性质5，此时fixup需要想办法在该路径上加一个黑节点
	 * 1.删除节点的后继node是一个红节点，只需要将node变色即可
	 * 2.删除节点的后继node是一个黑节点，需要旋转+变色+向上回溯
	 * @param node
	 */
	private void fixupAfterDelete(Node<K, V> node) {
		while (node != this.root && !color(node)) {
			// fixupNode是左孩子
			if (node == left(parent(node))) {
				Node<K, V> sibling = right(parent(node));
				/*
				 * case1: node的兄弟sibling是红色
				 * 操作：sibling置黑，父节点置红，然后左旋，之后修正sibling的引用
				 * 解释：node黑色，兄弟节点红色，那父节点一定是黑色
				 * 所以在该子树中删除了黑色节点的高度路径上的结构是：黑色node+黑色父节点
				 * 这样是没办法在该高度路径上增加一个黑节点的，所以先变色+旋转，转换成case2\3\4
				 */
				if (color(sibling)) {
					setColor(sibling, BLACK);
					setColor(parent(node), RED);
					rotateLeft(parent(node));
					sibling = right(parent(node));
				}
				/*
				 * case2: 到这里node的兄弟节点sibling一定是黑色，sibling的两个孩子也是黑色
				 * 操作：将兄弟节点sibling置红，node指向父节点
				 * 解释：node黑色，sibling黑色，parent可以是黑色也可以是红色
				 * 此时先将sibling置红，则其高度路径上黑色减1，也就意味着parent子树的左右孩子黑色都减1
				 * 1.如果parent是红色，node指向父节点，此时会跳出while循环，然后将parent置黑即可修复
				 * 2.如果parent是黑色，node指向父节点，此时parent左右子树的黑色高度都减1，相当于将问题继续向上回溯
				 */
				if (!color(left(sibling)) && !color(right(sibling))) {
					setColor(sibling, RED);
					node = parent(node);
				} else {
					// sibling左右孩子不全都是黑色的情况
					/*
					 * case3: sibling黑色，sibling.right黑色，sibling.left只能是红色（sibling两个孩子都是黑色的情况在if中处理了）
					 * 操作：sibling置红，sibling.left置黑，sibling右旋，然后修正node的sibling
					 * 解释：node黑色，sibling黑色，所以父节点可以是红色也可以是黑色
					 * 和case2类似，因为node和sibling都是黑色，所以父节点可以是黑色也可以是红色，但是因为sibling有一个红孩子
					 * 所以无法像case2那样通过变色进行修复或将问题向上回溯，而是要想办法把sibling的红孩子补充到node所在的路径（因为删除操作导致该路径上黑节点数量减一）
					 * 所以sibling置红，sibling拐点的红孩子置黑，旋转之后消除拐点，而不破坏红黑树其他性质，将case3转换成case4
					 */
					if (!color(right(sibling))) {
						setColor(sibling, RED);
						setColor(left(sibling), BLACK);
						rotateRight(sibling);
						sibling = right(parent(node));
					}
					/*
					 * case4: sibling黑色，sibling.right红色，
					 * 操作：sibling设置为父节点的颜色，parent置黑，sibling.right置黑，parent向左旋转，node指向根节点
					 * 解释：这个比较麻烦，见blog的分析
					 */
					setColor(sibling, color(parent(node)));
					setColor(parent(node), BLACK);
					setColor(right(sibling), BLACK);
					left(parent(node));
					node = this.root;
				}
			} else {
				Node<K, V> sibling = left(parent(node));
				if (color(sibling)) {
					setColor(sibling, BLACK);
					setColor(parent(node), RED);
					rotateRight(parent(node));
					sibling = left(parent(node));
				}
				if (!color(left(sibling)) && !color(right(sibling))) {
					setColor(sibling, RED);
					node = parent(node);
				} else {
					if (!color(left(sibling))) {
						setColor(right(sibling), BLACK);
						setColor(sibling, RED);
						rotateLeft(sibling);
						sibling = left(parent(node));
					}
					setColor(sibling, color(parent(node)));
					setColor(parent(node), BLACK);
					setColor(left(sibling), BLACK);
					rotateRight(parent(node));
					node = this.root; // node指向根节点的目的是跳出循环
				}
			}
		}
		// 1.删除节点的后继是一个红孩子，直接变色即可修复
		// 2.上面while，fixupNode中向上回溯成根节点或指向红节点
		setColor(node, BLACK);
	}

三、红黑树源码和测试

1.源码

package cn.wxy.blog2;

import java.util.Objects;
import cn.wxy.blog2.TraversalTreeTool.TreeNode;

/**
 * 红黑树源码
 * @author 王大锤
 * @date 2021年6月25日
 */
public class RBTree<K extends Comparable<K>, V> {
	private static final boolean RED = true;
	private static final boolean BLACK = false;

	static class Node<K extends Comparable<K>, V> implements TreeNode<K, Node<K, V>> {
		private K key;
		private V value;
		private boolean color = RED; // 节点默认是红色
		private Node<K, V> parent;
		private Node<K, V> leftChild;
		private Node<K, V> rightChild;

		public Node() {
		}

		public Node(K key, V value, Node<K, V> parent) {
			this.key = key;
			this.value = value;
			this.parent = parent;
		}

		public K getKey() {
			return key;
		}

		public void setKey(K key) {
			this.key = key;
		}

		public Node<K, V> getParent() {
			return parent;
		}

		public void setParent(Node<K, V> parent) {
			this.parent = parent;
		}

		public Node<K, V> getLeftChild() {
			return leftChild;
		}

		public void setLeftChild(Node<K, V> leftChild) {
			this.leftChild = leftChild;
		}

		public Node<K, V> getRightChild() {
			return rightChild;
		}

		public void setRightChild(Node<K, V> rightChild) {
			this.rightChild = rightChild;
		}

		@Override
		public String toString() {
			return this.key + ":" + value + ":" + (this.color ? "red " : "black ");
		}
	}

	private Node<K, V> root;

	public RBTree() {
	}

	public Node<K, V> getRoot() {
		return this.root;
	}

	/**
	 * select/insert/remove都需要用到这个方法
	 * 1.如果是空树，则返回null
	 * 2.如果树中包含key节点，则返回该节点
	 * 3.如果树中没有key节点，则返回最后一次查找的节点
	 * 这里不需要判断key是否为null，这个判断放在select/insert/remove调用selectNode之前，保证调用selectNode不会传入null
	 * @param key
	 * @return
	 */
	private Node<K, V> selectNode(K key) {
		Node<K, V> current = null;
		Node<K, V> find = this.root;
		while (Objects.nonNull(find)) {
			current = find;
			int compare = key.compareTo(find.key);
			if (compare < 0)
				find = find.leftChild;
			else if (compare > 0)
				find = find.rightChild;
			else
				break;
		}
		return current;
	}

	public V select(K key) {
		if (Objects.isNull(key))
			throw new NullPointerException();
		Node<K, V> node = selectNode(key);
		if (Objects.nonNull(node) && key.equals(node.key))
			return node.value;
		return null;
	}

	public void insert(K key, V value) {
		if (Objects.isNull(key))
			throw new NullPointerException();
		Node<K, V> current = selectNode(key);
		// 对于空树的情况，新插入的节点安作为根节点，节点默认红色，需要修改为黑色
		if (Objects.isNull(current)) {
			this.root = new Node<K, V>(key, value, null);
			this.root.color = BLACK;
			return;
		}
		int compare = key.compareTo(current.key);
		// 插入的节点已经存在红黑树中，只需要修改value即可
		if (compare == 0) {
			current.value = value;
			return;
		}
		// 插入的节点不在树中
		Node<K, V> newNode = new Node<K, V>(key, value, current);
		if (compare < 0)
			current.leftChild = newNode;
		else if (compare > 0)
			current.rightChild = newNode;
		// 插入节点如果违反红黑树属性4，则需要fixup
		fixupAfterInsert(newNode);
	}

	/**
	 * insert时，如果违反了红黑树的性质1（根节点只能是黑色）或性质4（红节点只能有黑孩子），则需要fixup
	 * 1.如果node是根节点，则只需要将node的颜色置黑即可
	 * 2.如果node非根节点，并且node.parent的颜色是红色，此时node的爷爷节点只能是黑色：
	 * case1:如果node的叔叔节点是红色，此时需要变色在子树内修复并将问题向上回溯（父节点和叔叔节点置黑，爷爷节点置红，当前节点指向爷爷节点）
	 * case2:如果node的叔叔节点是黑色，此时变色无法在子树内修复问题，如果node和父节点发生拐点，则当前节点指向父节点并发生单旋，将问题转换成case3
	 * case3:如果node的叔叔节点是黑色，此时变色无法在子树内修复问题，如果node和父节点没有拐点，则父节点变黑，爷爷节点变红，爷爷节点发生旋转
	 * @param node
	 */
	private void fixupAfterInsert(Node<K, V> node) {
		while (Objects.nonNull(node) && node != this.root && color(parent(node))) {
			// 父节点是左孩子的情况
			if (node.parent == left(parent(node.parent))) {
				Node<K, V> uncle = right(parent(node.parent));
				/*
				 * case1: 父节点红色，叔叔节点是红色（即父节点的兄弟节点是红色）
				 * 操作：parent和uncle置黑，爷爷节点置红，node指向爷爷节点
				 * 解释：父节点红色，则爷爷节点一定是黑色，如果此时叔叔节点也是红色，那么通过变色就能在子树内部修复问题
				 * 但是爷爷节点变红，爷爷节点的父节点如果也是红色那么同样违反性质4，所以node指向爷爷节点，需要向上回溯
				 */
				if (color(uncle)) {
					setColor(node.parent, BLACK);
					setColor(uncle, BLACK);
					setColor(parent(node.parent), RED);
					node = parent(node.parent);
				} else {
					/*
					 * case2: 父节点红色，叔叔节点是黑色，且发生拐点
					 * 操作：node指向父节点，然后左旋
					 * 解释：因为左旋之后原来的父节点变子节点，所以node先指向父节点再左旋
					 * 这样维持原问题node红父节点红，但是转换成了case3
					 */
					if (node == right(node.parent)) {
						node = node.parent;
						rotateLeft(node);
					}
					/*
					 * case3: 父节点红色，叔叔节点黑色，未发生拐点
					 * 操作：父节点置黑，爷爷节点置红，然后爷爷节点为子树根节点发生右旋
					 * 解释：父节点置黑修复双红问题，但是该高度路上黑色节点数目加1，所以爷爷节点置红恢复
					 * 但是爷爷节点置红，叔叔节点路径上的黑色节点数量减1，所以右旋后置黑的父节点变成子树新的根节点，修复双红问题
					 */
					setColor(node.parent, BLACK);
					setColor(parent(node.parent), RED);
					rotateRight(parent(node.parent));
				}
				// 父节点是右孩子的情况
			} else {
				Node<K, V> uncle = left(parent(node.parent));
				if (color(uncle)) {
					setColor(node.parent, BLACK);
					setColor(uncle, BLACK);
					setColor(parent(node.parent), RED);
					node = parent(node.parent);
				} else {
					if (node == left(node.parent)) {
						node = node.parent;
						rotateRight(node);
					}
					setColor(node.parent, BLACK);
					setColor(parent(node.parent), RED);
					rotateLeft(parent(node.parent));
				}
			}
		}
		/*
		 * 1.如果是根节点，直接置黑即可修复
		 * 2.如果是费根节点，在上面while循环中有可能将一个红节点旋转到根节点从而跳出循环，此时只需要置黑就行
		 */
		this.root.color = BLACK;
	}

	/**
	 * 删除节点，分成两种情况，需要找到实际删除的节点realDelNode
	 * 1.待删除结点最多有一个孩子：这种情况下，待删除节点就是实际删除的节点
	 * 2.待删除节点有两个孩子：这种情况下，实际删除的节点是待删除结点右子树的最左节点
	 * 所以，无论待删除结点是最多一个孩子还是两个孩子，最终都转换为最多一个孩子的形式
	 * 当实际删除节点是一个黑节点的时候，破坏了红黑树的性质5，此时需要fixup。
	 * fixup的起点是realDelNode的后继节点，所以还需要进一步考虑readDelNode是否有后继的问题。
	 * 根据上面删除的讨论，最终实际删除的节点realDelNode最多有一个孩子：
	 * 1.如果realDelNode是非叶子节点，那么fixupNode就是实际删除节点的唯一孩子
	 * 2.如果realDelNode是叶子节点，那么fixupNode就是realDelNode（把realDelNode假想成一个NIL节点），做完fixup之后再摘掉这个实际需要删除的叶子节点
	 * @param key
	 */
	public void remove(K key) {
		if (Objects.isNull(key))
			throw new NullPointerException();
		Node<K, V> deleteNode = selectNode(key);
		// 树中不存在要删除的节点
		if (Objects.isNull(deleteNode) || key.compareTo(deleteNode.key) != 0)
			return;
		/*
		 * 如果待删除节点有两个孩子，那么实际删除的节点是其右子树的最左节点
		 * 所以我们将其右子树最左节点的KV拷贝覆盖待删除结点的KV，然后deleteNode指向右子树最左节点
		 * 这样一来，两个孩子的情形就转换成了最多一个孩子的形式
		 */
		if (Objects.nonNull(deleteNode.leftChild) && Objects.nonNull(deleteNode.rightChild)) {
			Node<K, V> realDelNode = findMin(deleteNode.rightChild);
			deleteNode.key = realDelNode.key;
			deleteNode.value = realDelNode.value;
			deleteNode = realDelNode;
		}
		// 到这里，deleteNode全部转换成最多一个孩子的情形
		/*
		 * 接下来要考虑deleteNode是否是叶子节点：
		 * 1.如果非叶子，其孩子节点需要覆盖删除deleteNode，则fixupNode为其孩子节点
		 * 2.否则deleteNode作为叶子节点，fixupNode就是deleteNode，做完fixup之后再摘掉该节点
		 */
		Node<K, V> fixupNode = Objects.nonNull(deleteNode.leftChild) ? deleteNode.leftChild : deleteNode.rightChild;
		if (Objects.nonNull(fixupNode)) {
			// 非叶子，后继节点替代deleteNode
			fixupNode.parent = deleteNode.parent;
			if (Objects.nonNull(deleteNode.parent)) {
				if (deleteNode.equals(deleteNode.parent.leftChild))
					deleteNode.parent.leftChild = fixupNode;
				else
					deleteNode.parent.rightChild = fixupNode;
			} else
				// 实际删除节点是分支节点但只有一个孩子时，this.root指向替换它的后继节点
				this.root = fixupNode;
			deleteNode.parent = deleteNode.leftChild = deleteNode.rightChild = null;
			// 对于实际删除节点有后继节点的情况，fixup的起点是替换deleteNode的后继节点fixupNode
			if (!deleteNode.color)
				fixupAfterDelete(fixupNode);
		} else {
			// 实际删除节点是一个叶节点且是根节点，this.root = null并返回
			if (Objects.isNull(deleteNode.parent)) {
				this.root = null;
				return;
			}
			// 对于实际删除节点没有后继节点的情况，先将deleteNode看作NIL节点做fixup，之后再摘掉
			// fixup中修复的4个case都不会将其变为分支节点，始终是叶子节点
			if (!deleteNode.color)
				fixupAfterDelete(deleteNode);
			if (Objects.nonNull(deleteNode.parent)) {
				if (deleteNode.equals(deleteNode.parent.leftChild))
					deleteNode.parent.leftChild = null;
				else
					deleteNode.parent.rightChild = null;
				deleteNode.parent = null;
			}
		}
	}

	/**
	 * 删掉了一个黑节点，违反了红黑树的性质5，此时fixup需要想办法在该路径上加一个黑节点
	 * 1.删除节点的后继node是一个红节点，只需要将node变色即可
	 * 2.删除节点的后继node是一个黑节点，需要旋转+变色+向上回溯
	 * @param node
	 */
	private void fixupAfterDelete(Node<K, V> node) {
		while (node != this.root && !color(node)) {
			// fixupNode是左孩子
			if (node == left(parent(node))) {
				Node<K, V> sibling = right(parent(node));
				/*
				 * case1: node的兄弟sibling是红色
				 * 操作：sibling置黑，父节点置红，然后左旋，之后修正sibling的引用
				 * 解释：node黑色，兄弟节点红色，那父节点一定是黑色
				 * 所以在该子树中删除了黑色节点的高度路径上的结构是：黑色node+黑色父节点
				 * 这样是没办法在该高度路径上增加一个黑节点的，所以先变色+旋转，转换成case2\3\4
				 */
				if (color(sibling)) {
					setColor(sibling, BLACK);
					setColor(parent(node), RED);
					rotateLeft(parent(node));
					sibling = right(parent(node));
				}
				/*
				 * case2: 到这里node的兄弟节点sibling一定是黑色，sibling的两个孩子也是黑色
				 * 操作：将兄弟节点sibling置红，node指向父节点
				 * 解释：node黑色，sibling黑色，parent可以是黑色也可以是红色
				 * 此时先将sibling置红，则其高度路径上黑色减1，也就意味着parent子树的左右孩子黑色都减1
				 * 1.如果parent是红色，node指向父节点，此时会跳出while循环，然后将parent置黑即可修复
				 * 2.如果parent是黑色，node指向父节点，此时parent左右子树的黑色高度都减1，相当于将问题继续向上回溯
				 */
				if (!color(left(sibling)) && !color(right(sibling))) {
					setColor(sibling, RED);
					node = parent(node);
				} else {
					// sibling左右孩子不全都是黑色的情况
					/*
					 * case3: sibling黑色，sibling.right黑色，sibling.left只能是红色（sibling两个孩子都是黑色的情况在if中处理了）
					 * 操作：sibling置红，sibling.left置黑，sibling右旋，然后修正node的sibling
					 * 解释：node黑色，sibling黑色，所以父节点可以是红色也可以是黑色
					 * 和case2类似，因为node和sibling都是黑色，所以父节点可以是黑色也可以是红色，但是因为sibling有一个红孩子
					 * 所以无法像case2那样通过变色进行修复或将问题向上回溯，而是要想办法把sibling的红孩子补充到node所在的路径（因为删除操作导致该路径上黑节点数量减一）
					 * 所以sibling置红，sibling拐点的红孩子置黑，旋转之后消除拐点，而不破坏红黑树其他性质，将case3转换成case4
					 */
					if (!color(right(sibling))) {
						setColor(sibling, RED);
						setColor(left(sibling), BLACK);
						rotateRight(sibling);
						sibling = right(parent(node));
					}
					/*
					 * case4: sibling黑色，sibling.right红色，
					 * 操作：sibling设置为父节点的颜色，parent置黑，sibling.right置黑，parent向左旋转，node指向根节点
					 * 解释：这个比较麻烦，见blog的分析
					 */
					setColor(sibling, color(parent(node)));
					setColor(parent(node), BLACK);
					setColor(right(sibling), BLACK);
					left(parent(node));
					node = this.root;
				}
			} else {
				Node<K, V> sibling = left(parent(node));
				if (color(sibling)) {
					setColor(sibling, BLACK);
					setColor(parent(node), RED);
					rotateRight(parent(node));
					sibling = left(parent(node));
				}
				if (!color(left(sibling)) && !color(right(sibling))) {
					setColor(sibling, RED);
					node = parent(node);
				} else {
					if (!color(left(sibling))) {
						setColor(right(sibling), BLACK);
						setColor(sibling, RED);
						rotateLeft(sibling);
						sibling = left(parent(node));
					}
					setColor(sibling, color(parent(node)));
					setColor(parent(node), BLACK);
					setColor(left(sibling), BLACK);
					rotateRight(parent(node));
					node = this.root; // node指向根节点的目的是跳出循环
				}
			}
		}
		// 1.删除节点的后继是一个红孩子，直接变色即可修复
		// 2.上面while，fixupNode中向上回溯成根节点或指向红节点
		setColor(node, BLACK);
	}

	/**
	 * 防止空指针
	 * @param node
	 * @return
	 */
	private boolean color(Node<K, V> node) {
		return Objects.isNull(node) ? BLACK : node.color;
	}

	/**
	 * 防止空指针
	 * @param node
	 * @param color
	 */
	private void setColor(Node<K, V> node, boolean color) {
		if (Objects.nonNull(node))
			node.color = color;
	}

	/**
	 * 防止空指针
	 * @param node
	 * @return
	 */
	private Node<K, V> parent(Node<K, V> node) {
		return Objects.isNull(node) ? null : node.parent;
	}

	/***
	 * 防止空指针
	 * @param node
	 * @return
	 */
	private Node<K, V> left(Node<K, V> node) {
		return Objects.isNull(node) ? null : node.leftChild;
	}

	/**
	 * 防止空指针
	 * @param node
	 * @return
	 */
	private Node<K, V> right(Node<K, V> node) {
		return Objects.isNull(node) ? null : node.rightChild;
	}

	/**
	 * 向左旋转，需要处理三处总六条关系
	 * @param node 需要旋转的子树的根节点
	 */
	private void rotateLeft(Node<K, V> node) {
		if (Objects.nonNull(node)) {
			Node<K, V> newRoot = node.rightChild;
			// 第一处，处理node.right指向newRoot.left的关系
			node.rightChild = newRoot.leftChild;
			if (Objects.nonNull(newRoot.leftChild))
				newRoot.leftChild.parent = node;
			// 第二处：处理node.parent指向newRoot的关系
			newRoot.parent = node.parent;
			if (Objects.isNull(node.parent))
				this.root = newRoot;
			else if (node == node.parent.leftChild)
				node.parent.leftChild = newRoot;
			else
				node.parent.rightChild = newRoot;
			// 第三处：处理newRoot指向node的关系
			newRoot.leftChild = node;
			node.parent = newRoot;
		}
	}

	/**
	 * 向右旋转，需要处理三处总六条关系
	 * @param node 需要旋转的子树的根节点
	 */
	private void rotateRight(Node<K, V> node) {
		if (Objects.nonNull(node)) {
			Node<K, V> newRoot = node.leftChild;
			// 第一处：处理node.left指向newRoot.right的关系
			node.leftChild = newRoot.rightChild;
			if (Objects.nonNull(newRoot.rightChild))
				newRoot.rightChild.parent = node;
			// 第二处：处理node.parent指向newRoot的关系
			newRoot.parent = node.parent;
			if (Objects.isNull(node.parent))
				this.root = newRoot;
			else if (node == node.parent.leftChild)
				node.parent.leftChild = newRoot;
			else
				node.parent.rightChild = newRoot;
			// 第三处：处理newRoot指向node的关系
			newRoot.rightChild = node;
			node.parent = newRoot;
		}
	}

	private Node<K, V> findMin(Node<K, V> node) {
		if (Objects.isNull(node))
			return null;
		while (Objects.nonNull(node.leftChild))
			node = node.leftChild;
		return node;
	}
}

2.测试和分析

在《红黑树（上）》中，insert的测试我们构建了一颗红黑树，代码和图示如下，在此基础上做remove测试，需要测试的用例有：

删除根节点：14
删除红叶子：17
删除红分支：11和20
删除黑叶子：10
删除黑分支：30

虽然没有包括全部完整的用例，但是差不多得了，写blog真的是太费时间了！

建树代码：

	public static void main(String[] args) {
		RBTree<Integer, String> tree = new RBTree<Integer, String>();
		tree.insert(30, "30");
		tree.insert(20, "20");
		tree.insert(10, "10");
		tree.insert(11, "11");
		tree.insert(12, "12");
		tree.insert(15, "15");
		tree.insert(14, "14");
		tree.insert(16, "16");
		tree.insert(31, "31");
		tree.insert(17, "17");
		// TODO 添加需要测试的删除操作
		
		traversal(tree.getRoot());
	}

	private static <K extends Comparable<K>, V> void traversal(TreeNode<K, ?> root) {
		System.out.print("先序遍历：");
		TraversalTreeTool.preorderTraversalByRecursion(root);
		System.out.println();
		System.out.print("中序遍历：");
		TraversalTreeTool.inorderTraversalByRecursion(root);
		System.out.println();
		System.out.print("后序遍历：");
		TraversalTreeTool.postorderTraversalByRecursion(root);
		System.out.println();
		System.out.print("层序遍历：");
		TraversalTreeTool.levelTraversal(root);
		System.out.println();
	}

构建的红黑树图示：

删掉根节点：node 14

tree.remove(tree.getRoot().getKey());

先序遍历：15:15:black 11:11:red 10:10:black 12:12:black 20:20:red 16:16:black 17:17:red 30:30:black 31:31:red
中序遍历：10:10:black 11:11:red 12:12:black 15:15:black 16:16:black 17:17:red 20:20:red 30:30:black 31:31:red
后序遍历：10:10:black 12:12:black 11:11:red 17:17:red 16:16:black 31:31:red 30:30:black 20:20:red 15:15:black
层序遍历：15:15:black 11:11:red 20:20:red 10:10:black 12:12:black 16:16:black 30:30:black 17:17:red 31:31:red

删掉红叶子：node 17

tree.remove(17);

先序遍历：14:14:black 11:11:red 10:10:black 12:12:black 20:20:red 16:16:black 15:15:red 30:30:black 31:31:red
中序遍历：10:10:black 11:11:red 12:12:black 14:14:black 15:15:red 16:16:black 20:20:red 30:30:black 31:31:red
后序遍历：10:10:black 12:12:black 11:11:red 15:15:red 16:16:black 31:31:red 30:30:black 20:20:red 14:14:black
层序遍历：14:14:black 11:11:red 20:20:red 10:10:black 12:12:black 16:16:black 30:30:black 15:15:red 31:31:red

删掉红分支：node 11

tree.remove(11);

先序遍历：14:14:black 12:12:black 10:10:red 20:20:red 16:16:black 15:15:red 17:17:red 30:30:black 31:31:red
中序遍历：10:10:red 12:12:black 14:14:black 15:15:red 16:16:black 17:17:red 20:20:red 30:30:black 31:31:red
后序遍历：10:10:red 12:12:black 15:15:red 17:17:red 16:16:black 31:31:red 30:30:black 20:20:red 14:14:black
层序遍历：14:14:black 12:12:black 20:20:red 10:10:red 16:16:black 30:30:black 15:15:red 17:17:red 31:31:red

删掉红分支：node 20

tree.remove(20);

先序遍历：14:14:black 11:11:red 10:10:black 12:12:black 30:30:red 16:16:black 15:15:red 17:17:red 31:31:black
中序遍历：10:10:black 11:11:red 12:12:black 14:14:black 15:15:red 16:16:black 17:17:red 30:30:red 31:31:black
后序遍历：10:10:black 12:12:black 11:11:red 15:15:red 17:17:red 16:16:black 31:31:black 30:30:red 14:14:black
层序遍历：14:14:black 11:11:red 30:30:red 10:10:black 12:12:black 16:16:black 31:31:black 15:15:red 17:17:red

删掉黑叶子：node 10

tree.remove(10);

先序遍历：14:14:black 11:11:black 12:12:red 20:20:red 16:16:black 15:15:red 17:17:red 30:30:black 31:31:red
中序遍历：11:11:black 12:12:red 14:14:black 15:15:red 16:16:black 17:17:red 20:20:red 30:30:black 31:31:red
后序遍历：12:12:red 11:11:black 15:15:red 17:17:red 16:16:black 31:31:red 30:30:black 20:20:red 14:14:black
层序遍历：14:14:black 11:11:black 20:20:red 12:12:red 16:16:black 30:30:black 15:15:red 17:17:red 31:31:red

因为贪图简便，沿用了《红黑树（上）》中建树的例子，所以不太好测其他case，你copy代码过去自己测一测把，thanks老铁！

参考资料：

《算法导论》
《数据结构和算法：Java语言描述》
《大话数据结构》
JDK TreeMap源码

码农公寓