算法之红黑树

1. packagecom.eshore.sweetop.dataframe;
3. importcom.eshore.sweetop.data.KeyData;
4. importcom.eshore.sweetop.data.Node;
5. importcom.eshore.sweetop.data.RBNode;
7. publicclassRBTree{
8. privateRBNoderoot;
9. privatestaticfinalRBNodeNIL=RBNode.getRBNode();
11. publicRBTree(){
12. root=NIL;
13. }
15. publicvoidinsert(RBNodenode){
16. RBNodey=NIL;
17. RBNodex=root;
18. while(x!=NIL){
19. y=x;
20. if(node.getData().getKey()<x.getData().getKey()){
21. x=x.getLeft();
22. }else{
23. x=x.getRight();
24. }
25. }
26. node.setParent(y);
27. if(y==NIL){
28. root=node;
29. }elseif(node.getData().getKey()<y.getData().getKey()){
30. y.setLeft(node);
31. }else{
32. y.setRight(node);
33. }
34. node.setLeft(NIL);
35. node.setRight(NIL);
36. node.setColor(RBNode.RED);
37. insertFixup(node);
38. }
40. publicvoiddelete(RBNodenode){
41. RBNodetempy=NIL,tempx=NIL;
42. if(node.getLeft()==NIL||node.getRight()==NIL){
43. tempy=node;
44. }else{
45. tempy=successor(node);
46. }
47. if(tempy.getLeft()!=NIL){
48. tempx=tempy.getLeft();
49. }else{
50. tempx=tempy.getRight();
51. }
53. tempx.setParent(tempy.getParent());
55. if(tempy.getParent()==NIL){
56. root=tempx;
57. }elseif(tempy==tempy.getParent().getLeft()){
58. tempy.getParent().setLeft(tempx);
59. }else{
60. tempy.getParent().setRight(tempx);
61. }
62. if(tempy!=node){
63. node.setData(tempy.getData());
64. }
65. if(tempy.getColor()==RBNode.BLACK){
66. deleteFixup(tempx);
67. }
68. }
70. privatevoiddeleteFixup(RBNodenode){
72. RBNode tempw=NIL;
73. while(node!=root && node.getColor()==RBNode.BLACK){
74. if(node==node.getParent().getLeft()){
75. tempw=node.getParent().getRight();
76. if(tempw.getColor()==RBNode.RED){
77. tempw.setColor(RBNode.BLACK);
78. node.getParent().setColor(RBNode.RED);
79. leftRotate(node.getParent());
80. tempw=node.getParent().getRight();
81. }
82. if(tempw.getLeft().getColor()==RBNode.BLACK && tempw.getRight().getColor()==RBNode.BLACK){
83. tempw.setColor(RBNode.RED);
84. node=node.getParent();
85. }else{
86. if(tempw.getRight().getColor()==RBNode.BLACK){
87. tempw.getLeft().setColor(RBNode.BLACK);
88. tempw.setColor(RBNode.RED);
89. rightRotate(tempw);
90. }
91. tempw.setColor(node.getParent().getColor());
92. node.getParent().setColor(RBNode.BLACK);
93. tempw.getRight().setColor(RBNode.BLACK);
94. leftRotate(node.getParent());
95. break;
96. }
97. }else{
98. tempw=node.getParent().getLeft();
99. if(tempw.getColor()==RBNode.RED){
100. System.out.println("222");
101. tempw.setColor(RBNode.BLACK);
102. node.getParent().setColor(RBNode.RED);
103. rightRotate(node.getParent());
104. tempw=node.getParent().getLeft();
105. }
106. if(tempw.getLeft().getColor()==RBNode.BLACK && tempw.getRight().getColor()==RBNode.BLACK){
107. tempw.setColor(RBNode.RED);
108. node=node.getParent();
109. }else{
110. if(tempw.getLeft().getColor()==RBNode.BLACK){
111. tempw.getRight().setColor(RBNode.BLACK);
112. tempw.setColor(RBNode.RED);
113. leftRotate(tempw);
114. }
115. tempw.setColor(node.getParent().getColor());
116. node.getParent().setColor(RBNode.BLACK);
117. tempw.getLeft().setColor(RBNode.BLACK);
118. rightRotate(node.getParent());
119. break;
120. }
121. }
122. }
123. node.setColor(RBNode.BLACK);
124. }
126. privatevoidleftRotate(RBNodenode){
127. RBNodey=node.getRight();
128. node.setRight(y.getLeft());
129. if(y.getLeft()!=NIL){
130. y.getLeft().setParent(node);
131. }
132. y.setParent(node.getParent());
133. if(node.getParent()==NIL){
134. root=y;
135. }elseif(node==node.getParent().getLeft()){
136. node.getParent().setLeft(y);
137. }else{
138. node.getParent().setRight(y);
139. }
140. y.setLeft(node);
141. node.setParent(y);
142. }
144. privatevoidrightRotate(RBNodenode){
145. RBNodex=node.getLeft();
146. node.setLeft(x.getRight());
147. if(x.getRight()!=NIL){
148. x.getRight().setParent(node);
149. }
150. x.setParent(node.getParent());
151. if(node.getParent()==NIL){
152. root=x;
153. }elseif(node==node.getParent().getLeft()){
154. node.getParent().setLeft(x);
155. }else{
156. node.getParent().setRight(x);
157. }
158. x.setRight(node);
159. node.setParent(x);
160. }
162. publicvoidinsertFixup(RBNodenode){
163. RBNodey=NIL;
164. while(node.getParent().getColor()==RBNode.RED){
165. if(node.getParent()==node.getParent().getParent().getLeft()){
166. y=node.getParent().getParent().getRight();
167. if(y.getColor()==RBNode.RED){
168. node.getParent().setColor(RBNode.BLACK);
169. y.setColor(RBNode.BLACK);
170. node.getParent().getParent().setColor(RBNode.RED);
171. node=node.getParent().getParent();
172. }else{
173. if(node==node.getParent().getRight()){
174. node=node.getParent();
175. leftRotate(node);
176. }
177. node.getParent().setColor(RBNode.BLACK);
178. node.getParent().getParent().setColor(RBNode.RED);
179. rightRotate(node.getParent().getParent());
180. }
181. }else{
182. y=node.getParent().getParent().getLeft();
183. if(y.getColor()==RBNode.RED){
184. node.getParent().setColor(RBNode.BLACK);
185. y.setColor(RBNode.BLACK);
186. node.getParent().getParent().setColor(RBNode.RED);
187. node=node.getParent().getParent();
188. }else{
189. if(node==node.getParent().getLeft()){
190. node=node.getParent();
191. rightRotate(node);
192. }
193. node.getParent().setColor(RBNode.BLACK);
194. node.getParent().getParent().setColor(RBNode.RED);
195. leftRotate(node.getParent().getParent());
196. }
197. }
198. }
199. root.setColor(RBNode.BLACK);
200. }
202. publicvoidwalk(){
203. walk(root);
204. }
206. privatevoidwalk(RBNodenode){
207. if(node!=NIL){
208. walk(node.getLeft());
209. System.out.println(node.getData()+":"+node.getColor());
210. walk(node.getRight());
211. }
212. }
214. publicRBNodesearch(intk){
215. RBNodenode=root;
216. while(node!=NIL&&k!=node.getData().getKey()){
217. if(k<node.getData().getKey()){
218. node=node.getLeft();
219. }else{
220. node=node.getRight();
221. }
222. }
223. returnnode;
224. }
226. publicRBNodemin(RBNodenode){
227. while(node.getLeft()!=NIL){
228. node=node.getLeft();
229. }
230. returnnode;
231. }
233. publicRBNodemin(){
234. returnmin(root);
235. }
237. publicRBNodesuccessor(RBNodenode){
238. if(node.getRight()!=NIL){
239. returnmin(node.getRight());
240. }
241. RBNodey=node.getParent();
242. while(y!=NIL&&node==y.getRight()){
243. node=y;
244. y=y.getParent();
245. }
246. returny;
247. }
249. publicRBNodemax(RBNodenode){
250. while(node.getRight()!=NIL){
251. node=node.getRight();
252. }
253. returnnode;
254. }
256. publicRBNodemax(){
257. returnmax(root);
258. }
260. publicstaticvoidmain(String[]args){
261. RBTreebt=newRBTree();
262. int[]id={1,2,14,8,15,6,3};
263. RBNodenode=null;
264. for(inti=0;i<id.length;i++){
265. node=newRBNode();
266. node.setData(newKeyData(id[i]));
267. bt.insert(node);
268. }
269. bt.walk();
271. System.out.println("=====================");
272. System.out.println("Root"+bt.root.getData());
274. System.out.println("Max:"+bt.max().getData());
275. System.out.println("Min:"+bt.min().getData());
276. System.out.println(bt.search(8).getData());
277. System.out.println(bt.successor(bt.search(8)).getData());
278. bt.delete(bt.search(2));
279. System.out.println("Root"+bt.root.getData());
280. bt.walk();
281. }
282. }