背景知识

二叉树

定义：

二叉树（Binary Tree）是n(n >= 0)个节点的有限集合。该集合或者未空集（称为空二叉树），或者由一个根节点和两棵互不相交的，分别称为根节点的左子树和右子树的二叉树组成。

二叉树特点

每个节点最多有两棵子树。所以二叉树中不存在大于2的节点。
左子树和右子树是有顺序的，次序不能任一颠倒。就像人的双手和双脚，显然左手和右手，左脚和右脚都是不能颠倒顺序呼唤的，否则那也太别扭了。
即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。

特殊二叉树

斜树：顾名思义，斜树一定是斜的，所有的节点都只有左子树的二叉树叫左斜树，所有节点都是只有右子树的二叉树叫右斜树，两者统称为斜树。
满二叉树：在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
完全二叉树：对一棵具有n个节点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树编号为i的节点在二叉树中位置完全相同，则称该二叉树为完全二叉树。满二叉树一定是完全二叉树，但完全二叉树不一定是满的。
赫夫曼树：是一种带权路径长度最短的树。

平衡二叉树：是一种 二叉排序树（或者叫二叉查找树），其中每个节点的左子树和右子树的高度差至多等于1.
那么什么是二叉排序树呢？二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：

1
2
3

若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
它的左右子树也分别为二叉排序树。

红黑树：具体定义和性质请往下看。

红黑树

定义：

红黑树，一种自平衡的 二叉查找树，但在每个节点上有一个额外的存储位表示节点的颜色，可以是Red或者Black。这些颜色位用来确保红黑树在插入和删除操作后仍能近乎平衡。

红黑树示意图

红黑树的五个性质：

* 性质一：节点要么是红色要么是黑色。
* 性质二：根节点是黑色。
* 性质三：所有叶子节点都是黑色（叶子是NIL节点，被称为<font color=#00ffff size=4>黑哨兵</font>）。
* 性质四：每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
* 性质五：从任一节点到每个叶子节点的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

红黑树的应用场景

到此，我们可能已经对红黑树有了一点初步的认识了，但是我们却不知道为什么要有红黑树，红黑树是为了解决什么问题被提出来的呢？
我们知道，二叉查找树在大多数情况下查找和插入在效率上是没有问题的，但是在最坏的情况下效率比较低，但是平衡二叉树能够保证在最坏的情况下也能达到lgN，要实现这一目标，我们就要保证在插入完成后始终保持平衡状态。在一棵具有N个节点的树中，我们希望该树的高度能够维持在lgN左右，这样我们就能保证只需要lgN次比较操作就可以查找到想要的值。不幸的是，每次插入元素之后维持树的平衡状态太昂贵。所以就出现一些新的数据结构来保证在最坏的情况下插入和查找效率都能保证在对数的时间复杂度内完成。而我们所讲的红黑树就属于此新的数据结构之一，除此之外还有B树等数据结构。

HashMap Java1.8版本对HashMap做了优化，采用数组＋链表＋红黑树的数据结构，除此之外TreeMap也是采用的红黑树的数据结构来实现的。

旋转操作

左旋和右旋

红黑树查询操作

红黑树插入操作

若将一个节点插入到红黑树中，我们需要执行哪些操作呢？

首先，将红黑树当作一棵二叉查找树，将节点插入；
其次，将待插入节点着色为红色；
最后，通过“旋转和重新着色”等一系列操作来修正该树，使之重新成为一棵红黑树。

下面分别解释一下这三步操作：

第一步：将红黑树当作一棵二叉查找树，将节点插入

红黑树本身就是一棵二叉查找树，将新节点插入后，该树仍然是一棵二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，那么旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一棵二叉查找树的事实。

第二步：将待插入节点着色为红色

为什么插入的节点是红色，而不是黑色呢？

如果插入的是黑色节点，则肯定会在某条路径上增加黑色节点的数目，从而导致整棵树高度的不平衡，也就违反了红黑树的第五条性质；但如果新节点的父节点为红色时（如下图），将会违反红黑树性质四：一条路径上不能出现连续的两个红色节点，这时就需要通过一系列操作来使红黑树保持平衡。

红黑树之插入红色节点

若将插入节点更改为“红色”节点，会违背红黑树的哪些性质呢？

对于性质一，因为我们已经将插入节点涂成红色了，所以肯定不会违背。
对于性质二，因为我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找树的特点。插入操作不会改变根节点，所以根节点依然是黑色，也不会违背该性质。
对于性质三：因为叶子节点是黑哨兵，都是一些空节点，我们此时插入的是非空节点，所以也不会违背该性质。
对于性质四：有可能会违背。
对于性质五：因为插入的是红色节点，肯定不会影响某条路径上的黑色节点的数目的，所以肯定不会违背性质五。

经过上面的分析可知，想办法使之满足“性质四”，就可以将树重新构造成红黑树了。

第三步：通过“旋转和重新着色”等一系列操作来修正该树，使之重新成为一棵红黑树

为了更清晰地了解红黑树的插入操作，下面将会分具体的几种情况来介绍：

假设我们将要插入的节点用“新”表示，新插入节点的父节点用“父”表示，使用“叔”字表示“父”节点的兄弟节点，使用“祖”字表示“父”节点的父节点。

黑“父”

如下图所示，如果“新”节点的父节点为黑色，那么插入一个红节点，将不会影响红黑树的平衡，此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的概率相对AVL树来说会少一些。

红“父”

如下图所示。如果“新”节点的父节点为红色，若要新插入红色的“新”节点就违背了性质四：每条路径上不能有连续的两个红节点。由于”父”节点为红色，那么“祖”节点肯定为黑色。蓝色节点表示颜色未知。由于有可能需要根节点到“新”节点的路径上进行多次旋转操作，而每次进行不平衡判断的起始点都不一样，所以我们使用一个黑色箭头指向这个起始点，并称之为判定点。

红”叔”

当“叔”节点为红色时，如下图所示，无需进行旋转操作，只要将父和叔节点变为黑色，将”祖”节点变为红色即可。但由于祖父节点的父节点有可能为红色，从而违反红黑树性质。此时必须将祖父节点作为新的判定点继续向上进行平衡操作。

需要注意，无论“父”在”叔“的左边还是右边，无论“新”是”父”的左孩子还是右孩子，它们的操作都是完全一样的。

黑“叔”

情形1：

黑叔LL旋转

情形2：

黑叔LR旋转

情形3：

黑叔RR旋转

情形4：

黑叔RL旋转

可以观察到，当旋转完成后，新的旋转根全部为黑色，此时不需要再向上回溯进行平衡操作，插入操作完成。需要注意，上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

红黑树删除操作

相对于红黑树的查询和插入操作来说，删除操作相对会更复杂一些，也就是我们传说中所说的“请神容易送神难”！

那么如果我们删除一个节点，需要执行哪些操作呢？

首先，将红黑树当作一棵二叉查找树，将该节点从二叉查找树中删除；
然后，通过“旋转和着色”等一系列操作来修正该树，使之重新成为一棵红黑树。

下面分别解释一下这两步操作：

第一步：将红黑树当作一棵二叉查找树，将节点删除。

这和“删除常规二叉查找树中删除节点的方法是一样的”，分三种情况：

被删除节点为叶子节点，那么直接删除该节点就OK了；
被删除节点只有一个孩子节点，那么直接删除该节点，利用该节点的孩子节点直接顶替它的位置；
被删除节点有两个儿子，真正的删除点应该是所要删除节点的中序遍历前驱。

第二步：通过“旋转和着色”等一系列操作来修正该树，使之重新成为一棵红黑树。

因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树。

红黑树删除节点示意图

由上图和第一步可以推断出，在进行删除操作时，真正的删除点必定是只有一个孩子或没有孩子的结点。而根据红黑树的性质可以得出以下两个结论：

1、删除操作中真正被删除的必定是只有一个红色孩子或没有孩子的结点。
2、如果真正的删除点是一个红色结点，那么它必定是一个叶子结点。

完整参考代码

红黑树数据结构

package datastructure;
/**
 *
 * 红黑树的数据结构
 *
 * @param <T>
 */
public class RBTree<T extends Comparable<T>> {
	private RBTNode<T> mRoot;// 根节点
	private static final boolean RED = false;
	private static final boolean BLACK = true;
	public class RBTNode<T extends Comparable<T>> {
		boolean color;// 颜色
		T key;// 关键字（键值）
		RBTNode<T> left;// 左孩子
		RBTNode<T> right;// 右孩子
		RBTNode<T> parent;// 父节点
		public RBTNode(boolean color, T key, RBTNode<T> left, RBTNode<T> right, RBTNode<T> parent) {
			super();
			this.color = color;
			this.key = key;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}
		public T getkey() {
			return key;
		}
		public String toString() {
			return "" + key + (this.color == RED ? "(R)" : "B");
		}
	}
	public RBTree() {
		mRoot = null;
	}
	private RBTNode<T> parentOf(RBTNode<T> node) {
		return node != null ? node.parent : null;
	}
	private boolean colorOf(RBTNode<T> node) {
		return node != null ? node.color : BLACK;
	}
	private boolean isRed(RBTNode<T> node) {
		return ((node != null) && (node.color == RED)) ? true : false;
	}
	private boolean isBlack(RBTNode<T> node) {
		return isRed(node);
	}
	private void setRed(RBTNode<T> node) {
		if (node != null) {
			node.color = RED;
		}
	}
	private void setBlack(RBTNode<T> node) {
		if (node != null) {
			node.color = BLACK;
		}
	}
	private void setParent(RBTNode<T> node, RBTNode<T> parent) {
		if (node != null) {
			node.parent = parent;
		}
	}
	private void setColor(RBTNode<T> node, boolean color) {
		if (node != null) {
			node.color = color;
		}
	}
	/**
	 * 前序遍历红黑树
	 *
	 * @param tree
	 */
	private void preOrder(RBTNode<T> tree) {
		if (tree != null) {
			System.out.print(tree.key + " ");
			preOrder(tree.left);
			preOrder(tree.right);
		}
	}
	public void preOrder() {
		preOrder(mRoot);
	}
	/**
	 * 中序遍历红黑树
	 *
	 * @param tree
	 */
	private void inOrder(RBTNode<T> tree) {
		if (tree != null) {
			inOrder(tree.left);
			System.out.print(tree.key + " ");
			inOrder(tree.right);
		}
	}
	public void inOrder() {
		inOrder(mRoot);
	}
	/**
	 * 后序遍历红黑树
	 *
	 * @param tree
	 */
	private void postOrder(RBTNode<T> tree) {
		if (tree != null) {
			postOrder(tree.left);
			postOrder(tree.right);
			System.out.print(tree.key + " ");
		}
	}
	public void postOrder() {
		postOrder(mRoot);
	}
	/**
	 * (递归实现)查找"红黑树x"中键值为key的节点
	 *
	 * @param x
	 * @param key
	 * @return
	 */
	private RBTNode<T> search(RBTNode<T> x, T key) {
		if (x == null) {
			return x;
		}
		int cmp = key.compareTo(x.key);
		if (cmp < 0) {
			return search(x.left, key);
		} else if (cmp > 0) {
			return search(x.right, key);
		} else {
			return x;
		}
	}
	public RBTNode<T> search(T key) {
		return search(mRoot, key);
	}
	/**
	 * (非递归实现)查找"红黑树x"中键值为key的节点
	 *
	 * @param x
	 * @param key
	 * @return
	 */
	private RBTNode<T> iterativeSearch(RBTNode<T> x, T key) {
		while (x != null) {
			int cmp = key.compareTo(x.key);
			if (cmp < 0) {
				x = x.left;
			} else if (cmp > 0) {
				x = x.right;
			} else {
				return x;
			}
		}
		return x;
	}
	public RBTNode<T> iterativeSearch(T key) {
		return iterativeSearch(key);
	}
	/**
	 * 查找最小结点：返回tree为根结点的红黑树的最小结点。
	 *
	 * @param tree
	 * @return
	 */
	private RBTNode<T> minimum(RBTNode<T> tree) {
		if (tree == null) {
			return null;
		}
		while (tree.left != null) {
			tree = tree.left;
		}
		return tree;
	}
	public T minimum() {
		RBTNode<T> p = minimum(mRoot);
		if (p != null) {
			return p.key;
		}
		return null;
	}
	/**
	 * 查找最大结点：返回tree为根结点的红黑树的最大结点。
	 *
	 * @param tree
	 * @return
	 */
	private RBTNode<T> maximum(RBTNode<T> tree) {
		if (tree == null) {
			return null;
		}
		while (tree.right != null) {
			tree = tree.right;
		}
		return tree;
	}
	public T maximum() {
		RBTNode<T> p = maximum(mRoot);
		if (p != null) {
			return p.key;
		}
		return null;
	}
	/**
	 * 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
	 *
	 * @param x
	 * @return
	 */
	public RBTNode<T> successor(RBTNode<T> x) {
		// 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
		if (x.right != null) {
			return minimum(x.right);
		}
		// 如果x没有右孩子。则x有以下两种可能：
		// (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
		// (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
		RBTNode<T> y = x.parent;
		while ((y != null) && (x == y.right)) {
			x = y;
			y = y.parent;
		}
		return y;
	}
	/**
	 * 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
	 *
	 * @param x
	 * @return
	 */
	public RBTNode<T> predecessor(RBTNode<T> x) {
		// 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
		if (x.left != null)
			return maximum(x.left);
		// 如果x没有左孩子。则x有以下两种可能：
		// (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
		// (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
		RBTNode<T> y = x.parent;
		while ((y != null) && (x == y.left)) {
			x = y;
			y = y.parent;
		}
		return y;
	}
 /* 对红黑树的节点(x)进行左旋转
  *
  * 左旋示意图(对节点x进行左旋)：
  *      px                              px
  *     /                               /
  *    x                               y                
  *   /  \      --(左旋)-.            / \                #
  *  lx   y                          x  ry     
  *     /   \                       /  \
  *    ly   ry                     lx  ly  
  *
  *
  */
	private void leftRotate(RBTNode<T> x) {
		// 设置x的右孩子为y
		RBTNode<T> y = x.right;
		// 将 “y的左孩子” 设为 “x的右孩子”；
		// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
		x.right = y.left;
		if (y.left != null)
			y.left.parent = x;
		// 将 “x的父亲” 设为 “y的父亲”
		y.parent = x.parent;
		if (x.parent == null) {
			this.mRoot = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
		} else {
			if (x.parent.left == x)
				x.parent.left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
			else
				x.parent.right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
		}
		// 将 “x” 设为 “y的左孩子”
		y.left = x;
		// 将 “x的父节点” 设为 “y”
		x.parent = y;
	}
	/*       
     * 对红黑树的节点(y)进行右旋转
     *
     * 右旋示意图(对节点y进行左旋)：
     *            py                               py
     *           /                                /
     *          y                                x                  
     *         /  \      --(右旋)-.             /  \                     #
     *        x   ry                           lx   y  
     *       / \                                   / \                   #
     *      lx  rx                                rx  ry
     *
     */
	private void rightRotate(RBTNode<T> y) {
		// 设置x是当前节点的左孩子。
		RBTNode<T> x = y.left;
		// 将 “x的右孩子” 设为 “y的左孩子”；
		// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
		y.left = x.right;
		if (x.right != null)
			x.right.parent = y;
		// 将 “y的父亲” 设为 “x的父亲”
		x.parent = y.parent;
		if (y.parent == null) {
			this.mRoot = x; // 如果 “y的父亲” 是空节点，则将x设为根节点
		} else {
			if (y == y.parent.right)
				y.parent.right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
			else
				y.parent.left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
		}
		// 将 “y” 设为 “x的右孩子”
		x.right = y;
		// 将 “y的父节点” 设为 “x”
		y.parent = x;
	}
	private void insertFixUp(RBTNode<T> node) {
		RBTNode<T> parent, gparent;
		// 若“父节点存在，并且父节点的颜色是红色”
		while (((parent = parentOf(node)) != null) && isRed(parent)) {
			gparent = parentOf(parent);
			// 若“父节点”是“祖父节点的左孩子”
			if (parent == gparent.left) {
				// Case 1条件：叔叔节点是红色
				RBTNode<T> uncle = gparent.right;
				if ((uncle != null) && isRed(uncle)) {
					setBlack(uncle);
					setBlack(parent);
					setRed(gparent);
					node = gparent;
					continue;
				} // Case 2条件：叔叔是黑色，且当前节点是右孩子
				if (parent.right == node) {
					RBTNode<T> tmp;
					leftRotate(parent);
					tmp = parent;
					parent = node;
					node = tmp;
				}
				// Case 3条件：叔叔是黑色，且当前节点是左孩子。
				setBlack(parent);
				setRed(gparent);
				rightRotate(gparent);
			} else { // 若“z的父节点”是“z的祖父节点的右孩子”
				// Case 1条件：叔叔节点是红色
				RBTNode<T> uncle = gparent.left;
				if ((uncle != null) && isRed(uncle)) {
					setBlack(uncle);
					setBlack(parent);
					setRed(gparent);
					node = gparent;
					continue;
				}
				// Case 2条件：叔叔是黑色，且当前节点是左孩子
				if (parent.left == node) {
					RBTNode<T> tmp;
					rightRotate(parent);
					tmp = parent;
					parent = node;
					node = tmp;
				}
				// Case 3条件：叔叔是黑色，且当前节点是右孩子。
				setBlack(parent);
				setRed(gparent);
				leftRotate(gparent);
			}
		}
		// 将根节点设为黑色
		setBlack(this.mRoot);
	}
	/*
	 * 将结点插入到红黑树中
	 *
	 * 参数说明： node 插入的结点 // 对应《算法导论》中的node
	 */
	private void insert(RBTNode<T> node) {
		int cmp;
		RBTNode<T> y = null;
		RBTNode<T> x = this.mRoot;
		// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
		while (x != null) {
			y = x;
			cmp = node.key.compareTo(x.key);
			if (cmp < 0)
				x = x.left;
			else
				x = x.right;
		}
		node.parent = y;
		if (y != null) {
			cmp = node.key.compareTo(y.key);
			if (cmp < 0)
				y.left = node;
			else
				y.right = node;
		} else {
			this.mRoot = node;
		}
		// 2. 设置节点的颜色为红色
		node.color = RED;
		// 3. 将它重新修正为一颗二叉查找树
		insertFixUp(node);
	}
	/*
	 * 新建结点(key)，并将其插入到红黑树中
	 *
	 * 参数说明： key 插入结点的键值
	 */
	public void insert(T key) {
		RBTNode<T> node = new RBTNode<T>(BLACK, key, null, null, null);
		// 如果新建结点失败，则返回。
		if (node != null)
			insert(node);
	}
	/*
	 * 红黑树删除修正函数
	 *
	 * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数； 目的是将它重新塑造成一颗红黑树。
	 *
	 * 参数说明： node 待修正的节点
	 */
	private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
		RBTNode<T> other;
		while ((node == null || isBlack(node)) && (node != this.mRoot)) {
			if (parent.left == node) {
				other = parent.right;
				if (isRed(other)) {
					// Case 1: x的兄弟w是红色的
					setBlack(other);
					setRed(parent);
					leftRotate(parent);
					other = parent.right;
				}
				if ((other.left == null || isBlack(other.left)) && (other.right == null || isBlack(other.right))) {
					// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
					setRed(other);
					node = parent;
					parent = parentOf(node);
				} else {
					if (other.right == null || isBlack(other.right)) {
						// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
						setBlack(other.left);
						setRed(other);
						rightRotate(other);
						other = parent.right;
					}
					// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
					setColor(other, colorOf(parent));
					setBlack(parent);
					setBlack(other.right);
					leftRotate(parent);
					node = this.mRoot;
					break;
				}
			} else {
				other = parent.left;
				if (isRed(other)) {
					// Case 1: x的兄弟w是红色的
					setBlack(other);
					setRed(parent);
					rightRotate(parent);
					other = parent.left;
				}
				if ((other.left == null || isBlack(other.left)) && (other.right == null || isBlack(other.right))) {
					// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
					setRed(other);
					node = parent;
					parent = parentOf(node);
				} else {
					if (other.left == null || isBlack(other.left)) {
						// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
						setBlack(other.right);
						setRed(other);
						leftRotate(other);
						other = parent.left;
					}
					// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
					setColor(other, colorOf(parent));
					setBlack(parent);
					setBlack(other.left);
					rightRotate(parent);
					node = this.mRoot;
					break;
				}
			}
		}
		if (node != null)
			setBlack(node);
	}
	/*
	 * 删除结点(node)，并返回被删除的结点
	 *
	 * 参数说明： node 删除的结点
	 */
	private void remove(RBTNode<T> node) {
		RBTNode<T> child, parent;
		boolean color;
		// 被删除节点的"左右孩子都不为空"的情况。
		if ((node.left != null) && (node.right != null)) {
			// 被删节点的后继节点。(称为"取代节点")
			// 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
			RBTNode<T> replace = node;
			// 获取后继节点
			replace = replace.right;
			while (replace.left != null)
				replace = replace.left;
			// "node节点"不是根节点(只有根节点不存在父节点)
			if (parentOf(node) != null) {
				if (parentOf(node).left == node)
					parentOf(node).left = replace;
				else
					parentOf(node).right = replace;
			} else {
				// "node节点"是根节点，更新根节点。
				this.mRoot = replace;
			}
			// child是"取代节点"的右孩子，也是需要"调整的节点"。
			// "取代节点"肯定不存在左孩子！因为它是一个后继节点。
			child = replace.right;
			parent = parentOf(replace);
			// 保存"取代节点"的颜色
			color = colorOf(replace);
			// "被删除节点"是"它的后继节点的父节点"
			if (parent == node) {
				parent = replace;
			} else {
				// child不为空
				if (child != null)
					setParent(child, parent);
				parent.left = child;
				replace.right = node.right;
				setParent(node.right, replace);
			}
			replace.parent = node.parent;
			replace.color = node.color;
			replace.left = node.left;
			node.left.parent = replace;
			if (color == BLACK)
				removeFixUp(child, parent);
			node = null;
			return;
		}
		if (node.left != null) {
			child = node.left;
		} else {
			child = node.right;
		}
		parent = node.parent;
		// 保存"取代节点"的颜色
		color = node.color;
		if (child != null)
			child.parent = parent;
		// "node节点"不是根节点
		if (parent != null) {
			if (parent.left == node)
				parent.left = child;
			else
				parent.right = child;
		} else {
			this.mRoot = child;
		}
		if (color == BLACK)
			removeFixUp(child, parent);
		node = null;
	}
	/*
	 * 删除结点(z)，并返回被删除的结点
	 *
	 * 参数说明： tree 红黑树的根结点 z 删除的结点
	 */
	public void remove(T key) {
		RBTNode<T> node;
		if ((node = search(mRoot, key)) != null)
			remove(node);
	}
	/*
	 * 销毁红黑树
	 */
	private void destroy(RBTNode<T> tree) {
		if (tree == null)
			return;
		if (tree.left != null)
			destroy(tree.left);
		if (tree.right != null)
			destroy(tree.right);
		tree = null;
	}
	public void clear() {
		destroy(mRoot);
		mRoot = null;
	}
	/*
	 * 打印"红黑树"
	 *
	 * key -- 节点的键值 direction -- 0，表示该节点是根节点; -1，表示该节点是它的父结点的左孩子;
	 * 1，表示该节点是它的父结点的右孩子。
	 */
	private void print(RBTNode<T> tree, T key, int direction) {
		if (tree != null) {
			if (direction == 0) // tree是根节点
				System.out.printf("%2d(B) is root\n", tree.key);
			else // tree是分支节点
				System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree) ? "R" : "B", key,
						direction == 1 ? "right" : "left");
			print(tree.left, tree.key, -1);
			print(tree.right, tree.key, 1);
		}
	}
	public void print() {
		if (mRoot != null)
			print(mRoot, mRoot.key, 0);
	}
}

红黑树Demo测试

package com.akathink.tree;
import datastructure.RBTree;
/**
 *
 * 红黑树
 *
 */
public class RBTreeDemo {
	private static final int a[] = { 23, 16, 29, 12, 18, 26, 32, 13, 30,49 };
	private static final boolean mDebugInsert = false; // "插入"动作的检测开关(false，关闭；true，打开)
	private static final boolean mDebugDelete = false; // "删除"动作的检测开关(false，关闭；true，打开)
	public static void main(String[] args) {
		int i, ilen = a.length;
		RBTree<Integer> tree = new RBTree<Integer>();
		System.out.printf("== 原始数据: ");
		for (i = 0; i < ilen; i++)
			System.out.printf("%d ", a[i]);
		System.out.printf("\n");
		for (i = 0; i < ilen; i++) {
			tree.insert(a[i]);
			// 设置mDebugInsert=true,测试"添加函数"
			if (mDebugInsert) {
				System.out.printf("== 添加节点: %d\n", a[i]);
				System.out.printf("== 树的详细信息: \n");
				tree.print();
				System.out.printf("\n");
			}
		}
		System.out.printf("== 前序遍历: ");
		tree.preOrder();
		System.out.printf("\n== 中序遍历: ");
		tree.inOrder();
		System.out.printf("\n== 后序遍历: ");
		tree.postOrder();
		System.out.printf("\n");
		System.out.printf("== 最小值: %s\n", tree.minimum());
		System.out.printf("== 最大值: %s\n", tree.maximum());
		System.out.printf("== 树的详细信息: \n");
		tree.print();
		System.out.printf("\n");
		// 设置mDebugDelete=true,测试"删除函数"
		if (mDebugDelete) {
			for (i = 0; i < ilen; i++) {
				tree.remove(a[i]);
				System.out.printf("== 删除节点: %d\n", a[i]);
				System.out.printf("== 树的详细信息: \n");
				tree.print();
				System.out.printf("\n");
			}
		}
		// 销毁二叉树
		tree.clear();
	}
}

运行结果

== 原始数据: 23 16 29 12 18 26 32 13 30 49
== 前序遍历: 23 16 12 13 18 29 26 32 30 49
== 中序遍历: 12 13 16 18 23 26 29 30 32 49
== 后序遍历: 13 12 18 16 26 30 49 32 29 23
== 最小值: 12
== 最大值: 49
== 树的详细信息:
23(B) is root
16(R) is 23's   left child
12(B) is 16's   left child
13(R) is 12's  right child
18(B) is 16's  right child
29(R) is 23's  right child
26(B) is 29's   left child
32(B) is 29's  right child
30(R) is 32's   left child
49(R) is 32's  right child

参考资料

《大话数据结构》
http://www.tuicool.com/articles/J3iMf2R
http://blog.csdn.net/eric491179912/article/details/6179908
http://www.cnblogs.com/yangecnu/p/Introduce-2-3-Search-Tree.html
http://www.cnblogs.com/daoluanxiaozi/p/3340382.html
http://blog.csdn.net/loongshawn/article/details/50414608

AkaThink

彻底搞懂红黑树