红黑树

  1 import java.util.Random;
  2 
  3 
  4 public class RBTree 
  5 {
  6     
  7     private Node root;
  8     
  9     
 10     public RBTree(int[] array)
 11     {
 12         for (int i : array) insert(i);
 13     }
 14     
 15     private Node search(int key, Node node)
 16     {
 17         if (node == null) return null;
 18         int compare = compare(key, node.key);
 19         
 20         if (compare == 0) return node;
 21         if (compare > 0) 
 22             return search(key, node.right);
 23         else 
 24             return search (key, node.left);
 25     }
 26     
 27     /*
 28      * 插入节点
 29      */
 30     public boolean insert(int key)
 31     {
 32         Node node = new Node(key);
 33         node.color = 'R';
 34         
 35         Node parent = null, current = root;
 36         int compare = 0;
 37         
 38         /*
 39          * 寻找插入节点的父节点
 40          */
 41         while (current != null) {
 42             parent = current;
 43             compare = compare(key, current.key);
 44                 
 45             if (compare == 0) return false;
 46             
 47             if (compare == 1)
 48                 current = current.right;
 49             else
 50                 current = current.left;
 51         }
 52 
 53         // 添加新节点
 54         if (parent == null) {
 55             root = node;
 56         }
 57         else {
 58             node.parent = parent;
 59             if (compare == 1) {
 60                 parent.right = node;
 61             }
 62             else { 
 63                 parent.left = node;
 64             }
 65         }
 66         
 67         insertFixup(node);
 68         return true;
 69     }
 70     
 71     private void insertFixup(Node node)
 72     {
 73         while (node != root && node.parent.color == 'R') {
 74             // 父节点为祖父节点的左节点
 75             if (node.parent == node.parent.parent.left) {
 76                 Node uncle = node.parent.parent.right;
 77                 /*
 78                  * 父节点与叔叔节点都是红色
 79                  * 将父节点与叔叔节点变成黑色
 80                  * 将祖父节点变成红色
 81                  * 当前节点指向组父节点 
 82                  */
 83                 if (uncle != null && uncle.color == 'R') {
 84                     node.parent.color = 'B';
 85                     uncle.color = 'B';
 86                     uncle.parent.color = 'R';
 87                     node = node.parent.parent;
 88                 }
 89                 else {
 90                     /*
 91                      * 叔叔节点是黑色且node为右孩子
 92                      * 当前结点指向父节点
 93                      * 以当前结点为中心左旋
 94                      */
 95                     if (node == node.parent.right) {
 96                         node = node.parent;
 97                         leftRotate(node);
 98                     }
 99                     
100                     /*
101                      * 叔叔节点是黑色且node为左孩子
102                      * 父节点变为黑色，组父节点变为红色
103                      * 以祖父节点为中心右旋
104                      */
105                     node.parent.color = 'B';
106                     node.parent.parent.color = 'R';
107                     rightRotate(node.parent.parent);
108                 }
109             }
110             else {
111             // 父节点为祖父节点的右节点
112                 Node uncle = node.parent.parent.left;
113                 
114                 // 操作与上面相反
115                 if (uncle != null && uncle.color == 'R') {
116                     node.parent.color = 'B';
117                     uncle.color = 'B';
118                     uncle.parent.color = 'R';
119                     node = node.parent.parent;
120                 }
121                 else {
122                     if (node == node.parent.left) {
123                         node = node.parent;
124                         rightRotate(node);
125                     }
126                     node.parent.color = 'B';
127                     node.parent.parent.color = 'R';
128                     leftRotate(node.parent.parent);
129                 }
130             }
131         }
132         root.color = 'B';
133     }
134     
135     private void deleteFixup(Node node)
136     {
137         if (node == null) return;
138         
139         while (node != root && node.color == 'B') {
140             // node为父节点的左子节点
141             if (node == node.parent.left) {
142                 Node sibling = node.parent.right;
143                 
144                 /*
145                  * 当前结点为黑色且兄弟节点为红色
146                  * 将父节点染成红色,兄弟节点染成黑色
147                  * 针对父节点最一次左旋
148                  */
149                 if (sibling.color == 'R') {
150                     sibling.color = 'B';
151                     sibling.parent.color = 'R';
152                     leftRotate(node.parent);
153                     sibling = node.parent.right;
154                 }
155                 
156                 /*
157                  * 当前结点和兄弟节点为黑色,兄弟节点的子节点都为黑色
158                  * 将当前节点和兄弟节点抽出一重黑色加到父节点上
159                  * 把父节点当成新的节点继续计算
160                  */
161                 if (sibling.left.color == 'B' 
162                     && sibling.right.color == 'B') 
163                 {
164                     sibling.color = 'R';
165                     node = node.parent;
166                 }
167                 else {
168                     /*
169                      * 当前节点和兄弟节点为黑色,兄弟的左子节点为红色
170                      * 把兄弟节点染红,兄弟左子节点染黑
171                      * 以兄弟节点位置点右旋
172                      */
173                     if (sibling.right.color == 'B') {
174                         sibling.left.color = 'B';
175                         sibling.color = 'R';
176                         rightRotate(sibling);
177                         sibling = node.parent.right;
178                     }
179                     
180                     /*
181                      * 当前结点和兄弟节点为黑色,兄弟右子节点为红色
182                      * 把兄弟节点染成当前结点的父节点的颜色
183                      * 将当前节点的父节点染成黑色
184                      * 兄弟节点有子节点染成黑色
185                      * 以当前节点的父节点为支点左旋
186                      */
187                     sibling.color = node.parent.color;
188                     node.parent.color = 'B';
189                     sibling.right.color = 'B';
190                     leftRotate(node.parent);
191                     node = root;
192                 }
193             }
194             // node为父节点的右子节点
195             else {
196                 Node sibling = node.parent.left;
197                 
198                 /*
199                  * 当前结点为黑色，兄弟节点为红色
200                  * 将兄弟节点染成黑色
201                  * 当前结点的父节点染成红色
202                  * 以当前节点的父节点进行右旋
203                  */
204                 if (sibling.color == 'R') {
205                     sibling.color = 'B';
206                     sibling.parent.color = 'R';
207                     rightRotate(node.parent);
208                     sibling = node.parent.left;
209                 }
210                 
211                 /*
212                  * 当前结点和兄弟节点为黑色
213                  * 把当前结点和兄弟节点抽取一重黑色到父节点上
214                  * 把当前节点当作新的节点重新计算
215                  */
216                 if (sibling.left.color == 'B' && sibling.right.color == 'B') {
217                     sibling.color = 'R';
218                     sibling.parent.color = 'B';
219                     node = node.parent;
220                 }
221                 else {
222                     /*
223                      * 当前结点和兄弟节点为黑色,兄弟的右子节点为红色
224                      * 把兄弟节点染红,兄弟的左子节点染黑
225                      * 以兄弟节点为支点左旋
226                      */
227                     if (sibling.left.color == 'B') {
228                         sibling.color = 'R';
229                         sibling.right.color = 'B';
230                         leftRotate(sibling);
231                         sibling = node.parent.left;
232                     }
233                     
234                     /*
235                      * 当前结点和兄弟节点为黑色,兄弟的右子节点为黑色
236                      * 将兄弟节点染成当前结点的父节点的颜色
237                      * 当前节点的父节点染黑
238                      * 以当前结点的父节点为支点进行右旋
239                      */
240                     sibling.color = node.parent.color;
241                     node.parent.color = 'B';
242                     sibling.left.color = 'B';
243                     rightRotate(node.parent);
244                     node = root;
245                 }
246             }
247         }
248         node.color = 'B';
249     }
250     
251     /*
252      * 删除节点
253      * 只会在只有一个子节点的节点上进行
254      */
255     public void delete(int key)
256     {
257         Node node = search(key, root);
258         if (node == null) return;
259         
260         Node delete, child = null;
261         
262         // 如果有两个子节点则删除是其节点后继节点
263         if (node.left == null || node.right == null) {
264             delete = node;
265         }
266         else {
267             delete = interval(node);
268         }
269         
270         // 如国有子节点则判断是那个子节点
271         if (delete.left != null || delete.right != null) {
272             if (delete.left != null)
273                 child = delete.left;
274             else
275                 child = delete.right;
276             
277             child.parent = delete.parent;
278         }
279         
280         // 清除删除节点的引用
281         if (delete.parent == null) {
282             root = child;
283         }
284         else {
285             if (delete == delete.parent.left)
286                 delete.parent.left = child;
287             else
288                 delete.parent.right = child;
289         }
290         
291         // 如果删除的是后继节点则将当前其值赋给当前结点
292         if (delete != node) {
293             node.key = delete.key;
294         }
295         
296         // 调整红黑树平衡
297         if (delete.color == 'B')
298             deleteFixup(child);
299     }
300     
301     private void leftRotate(Node node)
302     {
303         /*
304          * 左旋
305          *        P                  P
306          *       / \                / \
307          *      @   d              y   d
308          *     / \       -->      / \
309          *    a   y              @   c
310          *       / \            / \
311          *      b   c          a   b
312          */
313         
314         Node right = node.right;
315         node.right = right.left;
316         
317         if (node.right != null) {
318             node.right.parent = node;
319         }
320         
321         right.parent = node.parent;
322         if (right.parent == null) {
323             root = right;
324         }
325         else {
326             if (node == node.parent.left)
327                 node.parent.left = right;
328             else
329                 node.parent.right = right;
330         }
331         
332         right.left = node;
333         node.parent = right;
334     }    
335     
336     private void rightRotate(Node node)
337     {
338         /*
339          * 右旋
340          *        P                P
341          *       / \              / \
342          *      d   @            d   y
343          *         / \    -->       / \
344          *        y   a            b   @        
345          *       / \                  / \
346          *      b   c                c   a
347          */
348         
349         Node left = node.left;
350         node.left = left.right;
351         
352         if (node.left != null) {
353             node.left.parent = node;
354         }
355         
356         left.parent = node.parent;
357         if (left.parent == null) {
358             root = left;
359         }
360         else {
361             if (node == node.parent.left) 
362                 node.parent.left = left;
363             else 
364                 node.parent.right = left;
365         }
366         
367         left.right = node;
368         node.parent = left;
369     }
370 
371     /*
372      * 最小值想做遍历寻找
373      */
374     private Node min(Node node)
375     {
376         while (node.left != null) {
377             node = node.left;
378         }
379         return node;
380     }
381     
382     /*
383      * 最大值向右遍历寻找
384      */
385     private Node max(Node node)
386     {
387         while (node.right != null) {
388             node = node.right;
389         }
390         return node;
391     }
392     
393     /*
394      * 查找直接后继节点
395      */
396     private Node interval(Node node)
397     {
398         /*
399          * 如果有右子节点则在右子节点中寻找
400          * 否则查找父节点为左子节点的节点作为后继节点
401          */
402         if (node.right != null)
403             return min(node.right);
404         else {
405             Node parent = node.parent;
406             while (parent != null && node == parent.right) {
407                 node = parent;
408                 parent = node.parent;
409             }
410             return parent;
411         }
412     }
413     
414     /*
415      * 比较大小
416      */
417     private int compare(int a, int b)
418     {
419         return a > b ? 1 : a < b ? -1 : 0;
420     }
421 
422     /*
423      * 前序遍历
424      */
425     public void preOrder()
426     {
427         preOrder(root);
428     }
429     
430     private void preOrder(Node node)
431     {
432         if (node == null) return;
433         
434         System.out.println(node.key + " " + node.color);
435         preOrder(node.left);
436         preOrder(node.right);
437     }
438     
439     /*
440      * 后续遍历
441      */
442     public void postOrder()
443     {
444         postOrder(root);
445     }
446     
447     private void postOrder(Node node)
448     {
449         if (node == null) return;
450         
451         postOrder(node.left);
452         postOrder(node.right);
453         System.out.println(node.key + " " + node.color);
454     }
455     
456     /*
457      * 中序遍历
458      */
459     public void inOrder()
460     {
461         inOrder(root);
462     }
463     
464     private void inOrder(Node node)
465     {
466         if (node == null) return;
467         
468         inOrder(node.left);
469         System.out.println(node.key + " " + node.color);
470         inOrder(node.right);
471     }
472     
473     static class Node
474     {
475         Node parent;
476         Node left;
477         Node right;
478         char color = 'B';
479         int key;
480         
481         public Node(int key)
482         {
483             this.key = key;
484         }
485         
486         public Node(char color)
487         {
488             this.color = color;
489             this.key = -Integer.MIN_VALUE;
490         }
491     }
492     
493     public static void main(String[] args)
494     {
495         int[] array = new int[20];
496         
497         Random rond = new Random();
498         for (int i = 0; i < array.length; i++) {
499             array[i] = Math.abs(rond.nextInt()) % 40;
500         }
501         
502         RBTree tree = new RBTree(array);
503         //tree.preOrder();
504         tree.inOrder();
505         
506         System.out.println();
507         System.out.println("delete " + array[6]);
508         System.out.println();
509         
510         tree.delete(array[6]);
511         //tree.preOrder();
512         tree.inOrder();
513     }
514 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/rilley/p/2586810.html