1 /*
2  * Copyright (c) 2008, 2019, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
23 
24 package jit.graph;
25 
26 // This class defines the tree object.
27 public class RBTree {
28     public final static int maxNodes = 70;      // maximum nodes allowed.
29     public final static int INSERT = 0;         // constants indicating
30     public final static int DELETE = 1;         // the current operation
31     public final static int NOP = 2;
32     public final static Node treeNull = new Node(); // the tree NULL node.
33 
34     private Node root;
35     private int num_of_nodes;
36     private int height;           // The tree height, it is updated
37     // in each operation.
38 
39     // since the algorithm is executed in stages I have to remember data
40     // on the state.
41     private Node node;  // The current operation is being done on it.
42     private int action; // The operation being performed (insert / delete)
43     private int stage;  // The current stage of execution
44 
45     // the constructor initializes the object fields.
RBTree()46     public RBTree() {
47         root = treeNull;
48         node = treeNull;
49         num_of_nodes = 0;
50         height = 0;
51         action = NOP;
52         stage = 0;
53     }
54 
55     // This method returns the root of the tree.
getRoot()56     public Node getRoot() {
57         return root;
58     }
59 
60     // This method returns the number of nodes in the tree.
getNodes()61     public int getNodes() {
62         return num_of_nodes;
63     }
64 
65     // This method returns the height of the tree.
getHeight()66     public int getHeight() {
67         return height;
68     }
69 
70 
71     // This method inserts k into the Red Black Tree
RBInsert(int k)72     public boolean RBInsert(int k) {
73         // checking similar to the RB_Insert method
74         if (action != NOP) {
75             System.out.println("Only one operation can be done at a time.");
76             return false;
77         }
78 
79         if (num_of_nodes == maxNodes) {
80             System.out.println("The maximum nodes allowed is already reached.");
81             return false;
82         }
83 
84         // Check if there is already node with key k.
85         if (Search(k) == treeNull) {
86             action = INSERT;
87             node = new Node(k);
88             node.setNode(Node.Left_son, treeNull);
89             node.setNode(Node.Right_son, treeNull);
90             node.setNode(Node.Parent, treeNull);
91             stage = 1;
92             // This is the loop that perform all the operation steps.
93             while (stage != 0) {
94                 // perform one step
95                 InsertStep();
96                 // update the tree height
97                 updateHeight();
98             }
99             // set the action to NoOPretion.
100             action = NOP;
101             return true;
102         } else
103             System.out.println("Insertion failed. This key already exist.");
104         return false;
105     }
106 
107 
108     // This method deletes the element k from the Red Black tree
RBDelete(int k)109     public boolean RBDelete(int k) {
110         // checking like in RB_Delete method
111         if (action != NOP) {
112             System.out.println("Only one operation can be done at a time.");
113             return false;
114         }
115         node = Search(k);
116         // Check if there is a node with key k.
117         if (node != treeNull) {
118             action = DELETE;
119             stage = 1;
120             // this loop perform all the operation steps.
121             while (stage != 0) {
122                 // perform one step
123                 DeleteStep();
124                 // update the tree height
125                 updateHeight();
126             }
127             action = NOP;
128             return true;
129         } else
130             System.out.println("Deletion failed. This key doesn't exist.");
131         return false;
132     }
133 
134     // This method performs one step in the insertion operation.
135     // It performs a step according to the stage variable.
136     // I will not explain exactly what each stage do, just that they
137     // divided to 4 categories:
138     // 1. inserting a node to the tree.
139     // 2. marking nodes that will be recolored.
140     // 3. recoloring nodes.
141     // 4. rotating right or left.
InsertStep()142     private void InsertStep() {
143         // Pr is parent, GrPr is grandparent and Un is uncle.
144         Node Pr, GrPr, Un;
145         switch (stage) {
146             // Inserting a node to the tree
147             case 1:
148                 Tree_Insert();
149                 break;
150             // mid stage that moves the algorithm to the proper next stage
151             case 2:
152                 Pr = node.getNode(Node.Parent);
153                 GrPr = Pr.getNode(Node.Parent);
154                 if (Pr == GrPr.getNode(Node.Left_son)) {
155                     Un = GrPr.getNode(Node.Right_son);
156                     if (Un.getColor() == Node.Red) {
157                         stage = 3;
158                     } else if (node == Pr.getNode(Node.Right_son)) {
159                         node = Pr;
160                         stage = 5;
161                     } else {
162                         stage = 6;
163                     }
164                 } else {
165                     Un = GrPr.getNode(Node.Left_son);
166                     if (Un.getColor() == Node.Red) {
167                         stage = 3;
168                     } else if (node == Pr.getNode(Node.Left_son)) {
169                         node = Pr;
170                         stage = 5;
171                     } else {
172                         stage = 6;
173                     }
174                 }
175                 break;
176             // This stage marks node that will be recolored
177             case 3:
178                 Pr = node.getNode(Node.Parent);
179                 GrPr = Pr.getNode(Node.Parent);
180                 if (Pr == GrPr.getNode(Node.Left_son)) {
181                     Un = GrPr.getNode(Node.Right_son);
182                 } else {
183                     Un = GrPr.getNode(Node.Left_son);
184                 }
185                 node = GrPr;
186                 stage = 4;
187                 break;
188             // This stage recolors marked nodes.
189             case 4:
190                 node.setColor(Node.Red);
191                 node.getNode(Node.Left_son).setColor(Node.Black);
192                 node.getNode(Node.Right_son).setColor(Node.Black);
193 
194                 if ((node == root) ||
195                         (node.getNode(Node.Parent).getColor() == Node.Black)) {
196                     if (root.getColor() == Node.Red) {
197                         stage = 9;
198                     } else
199                         stage = 0;
200                 } else {
201                     stage = 2;
202                     InsertStep();
203                 }
204                 break;
205             // This stage performs rotation operation
206             case 5:
207                 Pr = node.getNode(Node.Parent);
208                 if (node == Pr.getNode(Node.Left_son)) {
209                     Left_Rotate(node);
210                 } else {
211                     Right_Rotate(node);
212                 }
213                 stage = 6;
214                 break;
215             // This stage marks nodes that will be recolor.
216             case 6:
217                 Pr = node.getNode(Node.Parent);
218                 GrPr = Pr.getNode(Node.Parent);
219 
220                 stage = 7;
221                 break;
222             // This stage recolors marked nodes.
223             case 7:
224                 Pr = node.getNode(Node.Parent);
225                 Pr.setColor(Node.Black);
226                 GrPr = Pr.getNode(Node.Parent);
227                 GrPr.setColor(Node.Red);
228 
229                 stage = 8;
230                 break;
231             // This stage performs rotation operation
232             case 8:
233                 Pr = node.getNode(Node.Parent);
234                 GrPr = Pr.getNode(Node.Parent);
235                 if (Pr == GrPr.getNode(Node.Left_son)) {
236                     Right_Rotate(GrPr);
237                 } else {
238                     Left_Rotate(GrPr);
239                 }
240                 if (root.getColor() == Node.Red) {
241                     stage = 9;
242                 } else
243                     stage = 0;
244                 break;
245             // this stage marks the root.
246             case 9:
247                 stage = 10;
248                 break;
249             // This stage recolors the root.
250             case 10:
251                 root.setColor(Node.Black);
252                 stage = 0;
253                 break;
254         }
255     }
256 
257     // This method performs one step in the deletion operation.
258     // It perform sa step according to the stage variable.
259     // I will explain exactly what each stage do, just that they
260     // divided to 4 categories:
261     // 1. deleting a node from the tree.
262     // 2. marking nodes that will be recolored.
263     // 3. recoloring nodes.
264     // 4. rotating right or left.
DeleteStep()265     public void DeleteStep() {
266         // Pr is Parent, Br is Brother
267         Node Pr, Br;
268         switch (stage) {
269             // This stage delete a node from the tree.
270             case 1:
271                 Tree_Delete();
272                 break;
273             // This stage marks a nodes that will be recolored or perform other stage.
274             case 2:
275                 Pr = node.getNode(Node.Parent);
276                 if (node == Pr.getNode(Node.Left_son)) {
277                     Br = Pr.getNode(Node.Right_son);
278                 } else {
279                     Br = Pr.getNode(Node.Left_son);
280                 }
281                 if (Br.getColor() == Node.Red) {
282                     stage = 3;
283                 } else if ((Br.getNode(Node.Right_son).getColor() == Node.Black)
284                         && (Br.getNode(Node.Left_son).getColor() == Node.Black)) {
285                     stage = 5;
286                     DeleteStep();
287                 } else {
288                     stage = 7;
289                     DeleteStep();
290                 }
291                 break;
292             // This stage recolors marked nodes.
293             case 3:
294                 Pr = node.getNode(Node.Parent);
295                 if (node == Pr.getNode(Node.Left_son)) {
296                     Br = Pr.getNode(Node.Right_son);
297                 } else {
298                     Br = Pr.getNode(Node.Left_son);
299                 }
300                 Br.setColor(Node.Black);
301                 Pr.setColor(Node.Red);
302 
303                 stage = 4;
304                 break;
305             // This stage performs rotation operation
306             case 4:
307                 Pr = node.getNode(Node.Parent);
308                 if (node == Pr.getNode(Node.Left_son)) {
309                     Left_Rotate(Pr);
310                     Br = Pr.getNode(Node.Right_son);
311                 } else {
312                     Right_Rotate(Pr);
313                     Br = Pr.getNode(Node.Left_son);
314                 }
315                 if ((Br.getNode(Node.Right_son).getColor() == Node.Black)
316                         && (Br.getNode(Node.Left_son).getColor() == Node.Black)) {
317                     stage = 5;
318                 } else {
319                     stage = 7;
320                 }
321 
322                 break;
323             // This stage marks nodes that will be recolor.
324             case 5:
325                 Pr = node.getNode(Node.Parent);
326                 if (node == Pr.getNode(Node.Left_son)) {
327                     Br = Pr.getNode(Node.Right_son);
328                 } else {
329                     Br = Pr.getNode(Node.Left_son);
330                 }
331                 stage = 6;
332                 break;
333             // This stage recolors marked nodes.
334             case 6:
335                 Pr = node.getNode(Node.Parent);
336                 if (node == Pr.getNode(Node.Left_son)) {
337                     Br = Pr.getNode(Node.Right_son);
338                 } else {
339                     Br = Pr.getNode(Node.Left_son);
340                 }
341                 Br.setColor(Node.Red);
342                 node = Pr;
343 
344                 if ((node != root) && (node.getColor() == Node.Black)) {
345                     stage = 2;
346                 } else if (node.getColor() == Node.Red) {
347                     stage = 13;
348                 } else
349                     stage = 0;
350                 break;
351             // This stage marks nodes that will be recolor or perform other stage.
352             case 7:
353                 Pr = node.getNode(Node.Parent);
354                 if (node == Pr.getNode(Node.Left_son)) {
355                     Br = Pr.getNode(Node.Right_son);
356                     if ((Br.getNode(Node.Right_son)).getColor() == Node.Black) {
357                         stage = 8;
358                     } else {
359                         stage = 10;
360                         DeleteStep();
361                     }
362                 } else {
363                     Br = Pr.getNode(Node.Left_son);
364                     if ((Br.getNode(Node.Left_son)).getColor() == Node.Black) {
365                         stage = 8;
366                     } else {
367                         stage = 10;
368                         DeleteStep();
369                     }
370                 }
371                 break;
372             // This stage recolors marked nodes.
373             case 8:
374                 Pr = node.getNode(Node.Parent);
375                 if (node == Pr.getNode(Node.Left_son)) {
376                     Br = Pr.getNode(Node.Right_son);
377                     Br.getNode(Node.Left_son).setColor(Node.Black);
378                 } else {
379                     Br = Pr.getNode(Node.Left_son);
380                     Br.getNode(Node.Right_son).setColor(Node.Black);
381                 }
382                 Br.setColor(Node.Red);
383                 stage = 9;
384                 break;
385             // This stage performs rotation operation
386             case 9:
387                 Pr = node.getNode(Node.Parent);
388                 if (node == Pr.getNode(Node.Left_son)) {
389                     Br = Pr.getNode(Node.Right_son);
390                     Right_Rotate(Br);
391                 } else {
392                     Br = Pr.getNode(Node.Left_son);
393                     Left_Rotate(Br);
394                 }
395 
396                 stage = 10;
397                 break;
398             // This stage marks node that will be recolor.
399             case 10:
400                 Pr = node.getNode(Node.Parent);
401                 if (node == Pr.getNode(Node.Left_son)) {
402                     Br = Pr.getNode(Node.Right_son);
403                 } else {
404                     Br = Pr.getNode(Node.Left_son);
405                 }
406 
407                 stage = 11;
408                 break;
409             // This stage recolors marked nodes.
410             case 11:
411                 Pr = node.getNode(Node.Parent);
412                 if (node == Pr.getNode(Node.Left_son)) {
413                     Br = Pr.getNode(Node.Right_son);
414                     Br.getNode(Node.Right_son).setColor(Node.Black);
415                 } else {
416                     Br = Pr.getNode(Node.Left_son);
417                     Br.getNode(Node.Left_son).setColor(Node.Black);
418 
419                 }
420                 if (Br.getColor() != Pr.getColor()) {
421                     Br.setColor(Pr.getColor());
422                 }
423                 if (Pr.getColor() != Node.Black) {
424                     Pr.setColor(Node.Black);
425                 }
426 
427                 stage = 12;
428                 break;
429             // This stage performs rotation operation.
430             case 12:
431                 Pr = node.getNode(Node.Parent);
432                 if (node == Pr.getNode(Node.Left_son)) {
433                     Left_Rotate(Pr);
434                 } else {
435                     Right_Rotate(Pr);
436                 }
437                 node = root;
438                 if (node.getColor() == Node.Red) {
439                     stage = 13;
440                 } else {
441                     stage = 0;
442                 }
443                 break;
444             // This stage marks a node that will be recolored
445             case 13:
446                 stage = 14;
447                 break;
448             // This stage recolors marked node.
449             case 14:
450                 node.setColor(Node.Black);
451                 stage = 0;
452                 break;
453         }
454     }
455 
456     // This method inserts the node 'node' to the tree.
457     // it called from the first stage in the InsertStep method.
458     // we 'dive' from the root to a leaf according to the node key
459     // and insert the node in the proper place.
Tree_Insert()460     private void Tree_Insert() {
461         Node n1, n2;
462         n1 = root;
463         n2 = treeNull;
464         while (n1 != treeNull) {
465             n2 = n1;
466             if (node.getKey() < n1.getKey()) {
467                 n1 = n1.getNode(Node.Left_son);
468             } else {
469                 n1 = n1.getNode(Node.Right_son);
470             }
471         }
472         node.setNode(Node.Parent, n2);
473         if (n2 == treeNull) {
474             root = node;
475         }
476         else {
477             if (node.getKey() < n2.getKey()) {
478                 n2.setNode(Node.Left_son, node);
479             } else {
480                 n2.setNode(Node.Right_son, node);
481             }
482         }
483         // updating the insertion stage.
484         if ((node == root) ||
485                 (node.getNode(Node.Parent).getColor() == Node.Black)) {
486             if (root.getColor() == Node.Red) {
487                 stage = 9;
488             } else {
489                 stage = 0;
490             }
491         } else {
492             stage = 2;
493             InsertStep();
494         }
495         num_of_nodes++;   // increasing the number of nodes
496     }
497 
498     // This method deletes the node 'node' from the tree.
499     // it called from the first stage in the DeleteStep method.
500     // if node has at most one son we just remove it and connect
501     // his son and parent. If it has 2 sons we delete his successor
502     // that has at most one son and replace him with the successor.
Tree_Delete()503     private void Tree_Delete() {
504         Node n1, n2, n3;
505         if ((node.getNode(Node.Left_son) == treeNull) ||
506                 (node.getNode(Node.Right_son) == treeNull)) {
507             n1 = node;
508         } else {
509             n1 = Tree_Successor(node);
510         }
511 
512         if (n1.getNode(Node.Left_son) != treeNull) {
513             n2 = n1.getNode(Node.Left_son);
514         } else {
515             n2 = n1.getNode(Node.Right_son);
516         }
517 
518         n3 = n1.getNode(Node.Parent);
519         n2.setNode(Node.Parent, n3);
520         if (n3 == treeNull) {
521             root = n2;
522         } else if (n1 == n3.getNode(Node.Left_son)) {
523             n3.setNode(Node.Left_son, n2);
524         } else {
525             n3.setNode(Node.Right_son, n2);
526         }
527 
528         if (n1 != node) {
529             node.setKey(n1.getKey());
530         }
531 
532         node = n2;
533         if (n1.getColor() == Node.Black) {
534             if ((node != root) && (node.getColor() == Node.Black)) {
535                 stage = 2;
536             } else if (node.getColor() == Node.Red) {
537                 stage = 13;
538             } else {
539                 stage = 0;
540             }
541         } else {
542             stage = 0;
543         }
544         // decrease the number of nodes.
545         num_of_nodes--;
546     }
547 
548     // This method returns the successor of the node n in the tree.
Tree_Successor(Node n)549     private Node Tree_Successor(Node n) {
550         Node n1;
551         if (n.getNode(Node.Right_son) != treeNull) {
552             n = n.getNode(Node.Right_son);
553             while (n.getNode(Node.Left_son) != treeNull) {
554                 n = n.getNode(Node.Left_son);
555             }
556             return n;
557         }
558         n1 = n.getNode(Node.Parent);
559         while ((n1 != treeNull) && (n == n1.getNode(Node.Right_son))) {
560             n = n1;
561             n1 = n1.getNode(Node.Parent);
562         }
563         return n1;
564     }
565 
566     // This method performs Left Rotation with n1.
Left_Rotate(Node n1)567     private void Left_Rotate(Node n1) {
568         Node n2;
569 
570         n2 = n1.getNode(Node.Right_son);
571         n1.setNode(Node.Right_son, n2.getNode(Node.Left_son));
572         if (n2.getNode(Node.Left_son) != treeNull) {
573             n2.getNode(Node.Left_son).setNode(Node.Parent, n1);
574         }
575         n2.setNode(Node.Parent, n1.getNode(Node.Parent));
576         if (n1.getNode(Node.Parent) == treeNull) {
577             root = n2;
578         } else if (n1 == n1.getNode(Node.Parent).getNode(Node.Left_son)) {
579             n1.getNode(Node.Parent).setNode(Node.Left_son, n2);
580         } else {
581             n1.getNode(Node.Parent).setNode(Node.Right_son, n2);
582         }
583         n2.setNode(Node.Left_son, n1);
584         n1.setNode(Node.Parent, n2);
585     }
586 
587     // This method performs Right Rotation with n1.
Right_Rotate(Node n1)588     private void Right_Rotate(Node n1) {
589         Node n2;
590 
591         n2 = n1.getNode(Node.Left_son);
592         n1.setNode(Node.Left_son, n2.getNode(Node.Right_son));
593         if (n2.getNode(Node.Right_son) != treeNull) {
594             n2.getNode(Node.Right_son).setNode(Node.Parent, n1);
595         }
596         n2.setNode(Node.Parent, n1.getNode(Node.Parent));
597         if (n1.getNode(Node.Parent) == treeNull) {
598             root = n2;
599         } else if (n1 == (n1.getNode(Node.Parent)).getNode(Node.Left_son)) {
600             n1.getNode(Node.Parent).setNode(Node.Left_son, n2);
601         } else {
602             n1.getNode(Node.Parent).setNode(Node.Right_son, n2);
603         }
604         n2.setNode(Node.Right_son, n1);
605         n1.setNode(Node.Parent, n2);
606     }
607 
608     // This method searches the tree for a node with key 'key', and
609     // returns the node on success otherwise treeNull.
Search(int key)610     public Node Search(int key) {
611         Node node;
612         node = root;
613         while ((node != treeNull) && (key != node.getKey())) {
614             if (key < node.getKey()) {
615                 node = node.getNode(Node.Left_son);
616             } else {
617                 node = node.getNode(Node.Right_son);
618             }
619         }
620         return node;
621     }
622 
623     // This method updates the tree height. it uses a recursive method
624     // findHeight.
updateHeight()625     private void updateHeight() {
626         height = 0;
627         if (root != treeNull) {
628             findHeight(root, 1);
629         }
630     }
631 
632     // This is a recursive method that find a node height.
findHeight(Node n, int curr)633     private void findHeight(Node n, int curr) {
634         if (height < curr) {
635             height = curr;
636         }
637         if (n.getNode(Node.Left_son) != treeNull) {
638             findHeight(n.getNode(Node.Left_son), curr + 1);
639         }
640         if (n.getNode(Node.Right_son) != treeNull) {
641             findHeight(n.getNode(Node.Right_son), curr + 1);
642         }
643     }
644 
645 }
646