轉(zhuǎn)自：http://www.aygfsteel.com/javacap/archive/2007/12/20/169120.html
紅黑樹可能是要考慮情況最多的BST樹了，它有自己的規(guī)則（見代碼的注釋），通過這些規(guī)則可以保證花費(fèi)較小的代價(jià)來達(dá)到相對(duì)平衡。
注意，紅黑樹仍然不是平衡樹，但是統(tǒng)計(jì)性能要好于AVL樹。
要保持紅黑樹的規(guī)則，主要通過兩類操作，一類是換色，一類還是旋轉(zhuǎn)。
紅黑樹插入主要要解決紅-紅沖突，而刪除主要?jiǎng)t解決“雙黑”
同樣，紅黑樹的刪除節(jié)點(diǎn)實(shí)現(xiàn)是最復(fù)雜的，不過，復(fù)雜也就在于考慮的情況多，掌握了這幾種情況實(shí)現(xiàn)還是不困難。
其實(shí)，紅黑樹其實(shí)是一顆擴(kuò)充的二叉樹，所以也是滿二叉樹，其空節(jié)點(diǎn)可以看做是擴(kuò)充的葉節(jié)點(diǎn)。但是紅黑樹的擴(kuò)充葉節(jié)點(diǎn)是有特殊意義的。
下面是代碼：
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> g=p.parent;
RBNode<E> cur=(RBNode<E>)p.left;
p.left=cur.right;
if(cur.right!=null)((RBNode<E>)cur.right).parent=p;
cur.right=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> _insert(RBNode<E> cur,E ele)
{
RBNode<E> parent=null;
int cmp;
boolean left=false;
while(!cur.isNull()&&(cmp=ele.compareTo(cur.key))!=0)
{
parent=cur;
if(cmp<0)
{
cur=(RBNode<E>)cur.left;
left=true;
}
else {cur=(RBNode<E>)cur.right;left=false;}
}
if(!cur.isNull())throw new IllegalArgumentException("can't insert duplicate key!");
cur=newNormalNode(parent,ele,RBNode.RED);
if(left)parent.left=cur;
else parent.right=cur;
return cur;
}
/**
*
*/
public RBTree() {
root=null;
}
}