紅黑樹的插入實現

紅黑樹的插入實現

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;
13. //the default color of the new Node is Red
14. public Node(int k){
15. this.key=k;
16. this.color=RED;
17. }
19. }
20. private Node root;
21. public RBTree(){
22. root=null;
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. }
49. x.parent=y;
50. y.left=x;
52. }
53. /** X Y
54. * -------- -------
55. * Y c a X
56. * ----- ------
57. * a b b c
58. *
59. * @param t
60. * @param x
61. */
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. }
78. y.right=x;
79. x.parent=y;
81. }
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. }
106. //when we insert a Node ,we can classify the cases into 6 type
108. //case2,3,5,6 (when the uncle Node is bleak or uncle don't exist)
110. private void insertFixup(RBTree t, Node z) {
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);
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;
139. }else {
140. if(z==z.parent.left){ //case 5
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. }
150. }
151. }
152. t.root.color=BLACK;
153. }
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);
186. }
188. }