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