红黑树可能是要考虑情况最多的BST树了，它有自己的规则（见代码的注释），通过这些规则可以保证花费较小的代价来达到相对平衡。 注意，红黑树仍然不是平衡树，但是统计性能要好于AVL树。 要保持红黑树的规则，主要通过两类操作，一类是换色，一类还是旋转。 红黑树插入主要要解决红-红冲突，而删除主要则解决“双黑” 同样，红黑树的删除节点实现是最复杂的，不过，复杂也就在于考虑的情况多，掌握了这几种情况实现还是不困难。 其实，红黑树其实是一颗扩充的二叉树，所以也是满二叉树，其空节点可以看做是扩充的叶节点。但是红黑树的扩充叶节点是有特殊意义的。 下面是代码：
package algorithms.tree; /** * R-B Tree has following four rules: * 1)every node is either red or black * 2)root and empty node (external leaf node) are always black. * 3)the red node's parent node must be black * 4)every simple path start from node X to its descendant contains same number of black node * * * @author yovn * */ public class RBTree < E extends Comparable < E >> extends DefaultBSTree < E > implements BSTree < E > { public static class RBPrinter < E extends Comparable < E >> implements DefaultBSTree.NodeVisitor < E > { @Override public void visit(E ele) { } @Override public void visitNode(algorithms.tree.DefaultBSTree.BSTNode < E > node) { RBNode < E > n = (RBNode < E > )node; if ( ! n.isNull()) System.out.print(n.key + " ( " + (n.color == RBNode.RED ? " RED " : " BLACK " ) + " ), " ); } } static class RBNode < E extends Comparable < E >> extends BSTNode < E > { static final boolean RED = false ; static final boolean BLACK = true ; RBNode < E > parent; boolean color; // red or black RBNode(RBNode < E > p,E key, boolean color) { super (key); this .color = color; this .parent = p; } final boolean isNull(){ return key == null ;} } @Override public final boolean delete(E ele) { RBNode < E > cur; int cmp; if (root == null ) return false ; cur = (RBNode < E > )root; while ( ! cur.isNull() && (cmp = ele.compareTo(cur.key)) != 0 ) { if (cmp < 0 )cur = (RBNode < E > )cur.left; else cur = (RBNode < E > )cur.right; } if (cur.isNull()) { // can't find specified key return false ; } if ( ! ((RBNode < E > )cur.left).isNull() &&! ((RBNode < E > )cur.right).isNull()) { RBNode < E > prev = (RBNode < E > )cur.left; while ( ! ((RBNode < E > )prev.right).isNull()) { prev = (RBNode < E > )prev.right; } cur.key = prev.key; cur = prev; } if ( ! ((RBNode < E > )cur.left).isNull()) { if (cur == root) { root = cur.left; ((RBNode < E > )root).color = RBNode.BLACK; return true ; } if (cur.parent.left == cur) { cur.parent.left = cur.left; ((RBNode < E > )cur.left).parent = cur.parent; } else { cur.parent.right = cur.left; ((RBNode < E > )cur.left).parent = cur.parent; } if (cur.color == RBNode.BLACK) { ((RBNode < E > )cur.left).color = RBNode.BLACK; } } else if ( ! ((RBNode < E > )cur.right).isNull()) { if (cur == root) { root = cur.right; ((RBNode < E > )root).color = RBNode.BLACK; return true ; } if (cur.parent.left == cur) { cur.parent.left = cur.right; ((RBNode < E > )cur.right).parent = cur.parent; } else { cur.parent.right = cur.right; ((RBNode < E > )cur.right).parent = cur.parent; } if (cur.color == RBNode.BLACK) { ((RBNode < E > )cur.right).color = RBNode.BLACK; } } else { if (cur == root) { root = null ; return true ; } RBNode < E > todo; if (cur.parent.left == cur) { todo = newNullNode(cur.parent); cur.parent.left = todo; } else { todo = newNullNode(cur.parent); cur.parent.right = todo; } if (cur.color == RBNode.BLACK) { // now todo is a double black node, we will eliminate the double black fixup_double_black(todo); } } return true ; } @Override public E findMax() { if (isEmpty()) return null ; BSTNode < E > node = root; while ( ! ((RBNode < E > )node.right).isNull()) { node = node.right; } return node.key; } @Override public E findMin() { if (isEmpty()) return null ; BSTNode < E > node = root; while ( ! ((RBNode < E > )node.left).isNull()) { node = node.left; } return node.key; } private final RBNode < E > newNullNode(RBNode < E > p) { return new RBNode < E > (p, null ,RBNode.BLACK); } private final RBNode < E > newNormalNode(RBNode < E > p,E key, boolean color) { RBNode < E > node = new RBNode < E > (p,key,color); node.left = newNullNode(node); node.right = newNullNode(node); return node; } private final void fixup_double_black(RBNode < E > cur) { RBNode < E > sibling; RBNode < E > p; while (cur != root) // until its parent,parent maybe double black { p = cur.parent; if (p.left == cur) { sibling = (RBNode < E > )p.right; if (sibling.color == RBNode.RED) { rotate_from_right(p); p.color = RBNode.RED; sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation // this case transformed to another case handled in other place } else { if (((RBNode < E > )sibling.right).color == RBNode.RED) { rotate_from_right(p); sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so. p.color = RBNode.BLACK; ((RBNode < E > )sibling.right).color = RBNode.BLACK; // ok done! return ; } else if (((RBNode < E > )sibling.left).color == RBNode.RED) { rotate_from_left(sibling); sibling.color = RBNode.RED; sibling.parent.color = RBNode.BLACK; // its parent was previously be its left child, remember we have done a left rotation from sibling // now transformed to previous case, double black 's sibling(black) have right child colored red } else // sibling's two children are both black { // re-coloring the sibling and parent sibling.color = RBNode.RED; if (p.color == RBNode.BLACK) { cur = p; // now the cur node was not double black node ,but p was a double black } else { p.color = RBNode.BLACK; // eliminated the double black node return ; } } } } else { sibling = (RBNode < E > )p.left; if (sibling.color == RBNode.RED) { rotate_from_left(p); p.color = RBNode.RED; sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation // this case transformed to another case handled in other place } else { if (((RBNode < E > )sibling.left).color == RBNode.RED) { rotate_from_left(p); sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so. p.color = RBNode.BLACK; ((RBNode < E > )sibling.left).color = RBNode.BLACK; // ok done! return ; } else if (((RBNode < E > )sibling.right).color == RBNode.RED) { rotate_from_right(sibling); sibling.color = RBNode.RED; sibling.parent.color = RBNode.BLACK; // its parent was previously be its right child, remember we have done a left rotation from sibling // now transformed to previous case, double black 's sibling(black) have right child colored red } else // sibling's two children are both black { // re-coloring the sibling and parent sibling.color = RBNode.RED; if (p.color == RBNode.BLACK) { cur = p; // now the cur node was not double black node ,but p was a double black } else { p.color = RBNode.BLACK; // eliminated the double black node return ; } } } } } } @Override public final void insert(E ele) { if (root == null ) { root = newNormalNode( null ,ele,RBNode.BLACK); // now root's black-height(bh) is 1 return ; } RBNode < E > ret = _insert((RBNode < E > )root,ele); // first insert it _insert_fixup(ret); // fix-up the R-B tree from node cur; } private final void _insert_fixup(RBNode < E > cur) { RBNode < E > p,g; // we should fix until it is black colored while (cur != root && cur.color == RBNode.RED) { p = cur.parent; if (p.color == RBNode.BLACK) { // that's fine, the insertion will not change any black height, and will not violate any rule. return ; } g = p.parent; // we can assume the p is not null now. if (p == g.left) { RBNode < E > uncle = (RBNode < E > )g.right; if (uncle.color == RBNode.RED) { // re-coloring g.color = RBNode.RED; uncle.color = p.color = RBNode.BLACK; // now the g maybe conflict with its parent; cur = g; } else { if (cur == p.right) { // this case we should do left rotation, and then it will transform to next case cur = rotate_from_right(p); cur = (RBNode < E > )cur.left; // transformed to next case } cur = rotate_from_left(g); cur.color = RBNode.BLACK; ((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED; } } else { RBNode < E > uncle = (RBNode < E > )g.left; if (uncle.color == RBNode.RED) { // re-coloring g.color = RBNode.RED; uncle.color = p.color = RBNode.BLACK; // now the g maybe conflict with its parent; cur = g; } else { if (cur == p.left) { // this case we should do right rotation, and then it will transform to next case cur = rotate_from_left(p); cur = (RBNode < E > )cur.right; // transformed to next case } cur = rotate_from_right(g); cur.color = RBNode.BLACK; ((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED; } } } ((RBNode < E > )root).color = RBNode.BLACK; } private final RBNode < E > rotate_from_right(RBNode < E > p) { RBNode < E > g = p.parent; RBNode < E > cur = (RBNode < E > )p.right; p.right = cur.left; if (cur.left != null )((RBNode < E > )cur.left).parent = p; cur.left = p; p.parent = cur; if (g != null ) { if (g.left == p)g.left = cur; else g.right = cur; } else root = cur; cur.parent = g; return cur; } private final RBNode < E > rotate_from_left(RBNode < E > p) { RBNode < E > 相关资源：红黑树的Java实现参考源码