红黑树的插入实现

红黑树的插入实现

package com.lkl;
import java.util.*;
public class RBTree {
private static final boolean RED=false;
private static final boolean BLACK=true;
static class Node{
int key;
Node left;
Node right;
Node parent;
boolean color;
//the default color of the new Node is Red
public Node（int k）{
this.key=k;
this.color=RED;
}
}
private Node root;
public RBTree（）{
root=null;
}
/** LEFT ROTATE
* X Y
* ------ ------------
* | Y X |
* a ----- -------- c
* | | | |
* b c a b
*
*/
public void leftRotate（RBTree T,Node x）{
Node y=x.right;
x.right=y.left;
if（y.left！=null）{
y.left.parent=x;
}
y.parent=x.parent;
if（x.parent==null）{
T.root=y;
}else if（x==x.parent.left）{
x.parent.left=y;
}else{
x.parent.right=y;
}
x.parent=y;
y.left=x;
}
/** X Y
* -------- -------
* Y c a X
* ----- ------
* a b b c
*
* @param t
* @param x
*/
public void rightRotate（RBTree t,Node x）{
Node y=x.left;
x.left=y.right;
if（y.right！=null）{
y.right.parent=x;
}
y.parent=x.parent;
if（x.parent==null）{ //x is the root
t.root=y;
}else if（x==x.parent.left）{
x.parent.left=y;
}else{
x.parent.right=y;
}
y.right=x;
x.parent=y;
}
public void insert（RBTree t,Node z）{
Node y=null;
Node x=t.root;
while（x！=null）{ //find the right location
y=x;
if（z.key<x.key）{
x=x.left;
}else{
x=x.right;
}
}
z.parent=y; //insert node z
if（y==null）{ //the RBTRee is empty
t.root=z; //the root must be z
}else if（z.key<y.key）{
y.left=z;
}else{
y.right=z;
}
insertFixup（t,z）; //insert the node may break the rule 4
}
//when we insert a Node ,we can classify the cases into 6 type
//case2,3,5,6 （when the uncle Node is bleak or uncle don"t exist）
private void insertFixup（RBTree t, Node z） {
while（（z.parent！=null）&&（z.parent.color==RED））{ //this break the rule 4,there have 6 cases
Node uncle;
if（z.parent==z.parent.parent.left） { //case 1-3
uncle=z.parent.parent.right; //find the uncle
if（（uncle！=null）&&（uncle.color==RED））{ //case 1
z.parent.color=BLACK;
uncle.color=BLACK;
z.parent.parent.color=RED;
z=z.parent.parent;
}else {
if（z==z.parent.right）{ //judge uncle.color==black is wrong, case 2
z=z.parent; //when only 2 nodes in the tree,the uncle don"t exist
t.leftRotate（t, z）; //change case 2 to case 3
}
z.parent.color=BLACK; //case 3
z.parent.parent.color=RED; //case 3
t.rightRotate（t, z.parent.parent）;
}
}else{
uncle=z.parent.parent.left;
if（（uncle！=null）&&（uncle.color==RED））{ //case 4
z.parent.color=BLACK;
uncle.color=BLACK;
z.parent.parent.color=RED;
z=z.parent.parent;
}else {
if（z==z.parent.left）{ //case 5
z=z.parent;
t.rightRotate（t,z）; //change case5 to case6
}
z.parent.color=BLACK;
z.parent.parent.color=RED;
t.leftRotate（t, z.parent.parent）;
}
}
}
t.root.color=BLACK;
}
public static void main（String[] args）{
RBTree t=new RBTree（）;
int MAX=1000000;
Node x[]=new Node[MAX];
Random r=new Random（）;
long startTime=System.currentTimeMillis（）;
for（int i=0;i<MAX;i++）{
x[i]=new Node（（int）（Math.random（）*100））;
t.insert（t, x[i]）;
}
long endTime=System.currentTimeMillis（）;
System.out.println（" process runtime :"+（endTime-startTime）+"ms"）;
// Node a=new Node（41）;
// Node b=new Node（38）;
// Node c=new Node（31）;
// Node d=new Node（12）;
// Node e=new Node（19）;
// Node f=new Node（8）;
// // x[10]=new Node（3）;
// t.insert（t, a）;
// t.insert（t, b）;
// t.insert（t, c）;
// t.insert（t, d）;
// t.insert（t, e）;
// t.insert（t, f）;
System.out.println（t.root.color）;
System.out.println（x[10].color）;
}
}