红黑树的插入实现

红黑树的插入实现

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);          }      }