紅黑樹的插入實現

紅黑樹的插入實現

1. package com.lkl;  
2. import java.util.*;  
3. public class RBTree {  
4.     private static final boolean RED=false;  
5.     private static final boolean BLACK=true;  
6.     static  class Node{  
7.         int key;  
8.         Node left;  
9.         Node right;  
10.         Node parent;  
11.         boolean color;  
12.   
13.         //the default color of the new Node is Red   
14.         public Node(int k){  
15.             this.key=k;  
16.             this.color=RED;  
17.         }  
18.   
19.     }  
20.     private Node root;  
21.     public RBTree(){  
22.         root=null;  
23.   
24.     }  
25.     /**  LEFT ROTATE 
26.      *         X                                Y 
27.      *      ------                        ------------ 
28.      *      |     Y                        X          | 
29.      *      a   -----                 --------        c 
30.      *          |    |                |      | 
31.      *         b      c               a       b 
32.      * 
33.      */  
34.     public void leftRotate(RBTree T,Node x){  
35.      Node y=x.right;  
36.      x.right=y.left;  
37.      if(y.left!=null){  
38.          y.left.parent=x;  
39.      }  
40.      y.parent=x.parent;  
41.      if(x.parent==null){  
42.          T.root=y;  
43.      }else if(x==x.parent.left){  
44.          x.parent.left=y;  
45.      }else{  
46.          x.parent.right=y;  
47.      }  
48.   
49.      x.parent=y;  
50.      y.left=x;  
51.   
52.     }  
53.     /**        X                         Y 
54.      *     --------                   ------- 
55.      *     Y       c                 a      X 
56.      *   -----                           ------ 
57.      *   a   b                          b      c 
58.      * 
59.      * @param t 
60.      * @param x 
61.      */  
62.   
63.     public void rightRotate(RBTree t,Node x){  
64.         Node y=x.left;  
65.         x.left=y.right;  
66.         if(y.right!=null){  
67.             y.right.parent=x;  
68.         }  
69.         y.parent=x.parent;  
70.         if(x.parent==null){  //x is the root   
71.             t.root=y;  
72.         }else if(x==x.parent.left){  
73.             x.parent.left=y;  
74.         }else{  
75.             x.parent.right=y;  
76.         }  
77.   
78.         y.right=x;  
79.         x.parent=y;  
80.   
81.     }  
82.   
83.     public void insert(RBTree t,Node z){  
84.         Node y=null;  
85.         Node x=t.root;  
86.         while(x!=null){  //find the right location   
87.             y=x;  
88.             if(z.key<x.key){  
89.                 x=x.left;  
90.             }else{  
91.                 x=x.right;  
92.             }  
93.         }  
94.         z.parent=y;    //insert node z   
95.         if(y==null){   //the RBTRee is empty   
96.             t.root=z;  //the root must be z   
97.         }else if(z.key<y.key){  
98.             y.left=z;  
99.         }else{  
100.             y.right=z;  
101.         }  
102.         insertFixup(t,z); //insert the node may break the rule 4   
103.     }  
104.   
105.   
106.     //when we insert a Node ,we can classify the cases into 6 type   
107.   
108.     //case2,3,5,6 (when the uncle Node is bleak or uncle don't exist)   
109.   
110.     private void insertFixup(RBTree t, Node z) {  
111.   
112.         while((z.parent!=null)&&(z.parent.color==RED)){    //this break the rule 4,there have 6 cases   
113.             Node uncle;  
114.             if(z.parent==z.parent.parent.left) {    //case 1-3   
115.                uncle=z.parent.parent.right;  //find the uncle   
116.                     if((uncle!=null)&&(uncle.color==RED)){   //case 1   
117.                         z.parent.color=BLACK;  
118.                         uncle.color=BLACK;  
119.                         z.parent.parent.color=RED;  
120.                         z=z.parent.parent;  
121.                     }else {  
122.                     if(z==z.parent.right){  //judge uncle.color==black is wrong, case 2   
123.                             z=z.parent;           //when only 2 nodes in the tree,the uncle don't exist   
124.                             t.leftRotate(t, z);    //change case 2 to case 3   
125.                     }  
126.                     z.parent.color=BLACK;           //case 3   
127.                     z.parent.parent.color=RED;      //case 3   
128.                     t.rightRotate(t, z.parent.parent);  
129.   
130.                     }  
131.             }else{  
132.                 uncle=z.parent.parent.left;  
133.                 if((uncle!=null)&&(uncle.color==RED)){          //case 4   
134.                     z.parent.color=BLACK;  
135.                     uncle.color=BLACK;  
136.                     z.parent.parent.color=RED;  
137.                     z=z.parent.parent;  
138.   
139.                 }else {  
140.                     if(z==z.parent.left){    //case 5   
141.   
142.                     z=z.parent;  
143.                     t.rightRotate(t,z);         //change case5 to case6   
144.                     }  
145.                     z.parent.color=BLACK;  
146.                     z.parent.parent.color=RED;  
147.                     t.leftRotate(t, z.parent.parent);  
148.                 }  
149.   
150.             }  
151.         }  
152.         t.root.color=BLACK;  
153.     }  
154.   
155.   
156.   
157.   
158.     public static void main(String[] args){  
159.         RBTree t=new RBTree();  
160.         int MAX=1000000;  
161.         Node x[]=new Node[MAX];  
162.         Random r=new Random();  
163.         long startTime=System.currentTimeMillis();  
164.         for(int i=0;i<MAX;i++){  
165.             x[i]=new Node((int) (Math.random()*100));  
166.             t.insert(t, x[i]);  
167.         }  
168.         long endTime=System.currentTimeMillis();  
169.         System.out.println(" process runtime :"+(endTime-startTime)+"ms");  
170. //      Node a=new Node(41);   
171. //        Node b=new Node(38);   
172. //      Node c=new Node(31);   
173. //      Node d=new Node(12);   
174. //      Node e=new Node(19);   
175. //      Node f=new Node(8);   
176. //  //  x[10]=new Node(3);   
177. //        t.insert(t, a);   
178. //        t.insert(t, b);   
179. //        t.insert(t, c);   
180. //        t.insert(t, d);   
181. //        t.insert(t, e);   
182. //        t.insert(t, f);   
183.          System.out.println(t.root.color);  
184.          System.out.println(x[10].color);  
185.   
186.     }  
187.   
188. }