红黑树的Java实现

红黑树可能是要考虑情况最多的BST树了，它有自己的规则（见代码的注释），通过这些规则可以保证花费较小的代价来达到相对平衡。
注意，红黑树仍然不是平衡树，但是统计性能要好于AVL树。
要保持红黑树的规则，主要通过两类操作，一类是换色，一类还是旋转。
红黑树插入主要要解决红-红冲突，而删除主要则解决“双黑”

同样，红黑树的删除节点实现是最复杂的，不过，复杂也就在于考虑的情况多，掌握了这几种情况实现还是不困难。
其实，红黑树其实是一颗扩充的二叉树，所以也是满二叉树，其空节点可以看做是扩充的叶节点。但是红黑树的扩充叶节点是有特殊意义的。


下面是代码：

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->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;
}

}