1 /* 2 * Copyright (c) 2008, 2018, 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 package jit.graph; 24 25 import nsk.share.TestFailure; 26 27 //import Node; 28 29 // This class defines the tree object. 30 31 public class RBTree 32 { 33 public final static int maxNodes = 70; // maximum nodes allowed. 34 public final static int INSERT = 0; // constants indicating 35 public final static int DELETE = 1; // the current operation 36 public final static int NOP = 2; 37 public final static Node treeNull = new Node(); // the tree NULL node. 38 39 private Node root; 40 private int num_of_nodes; 41 private int height; // The tree heigth ,it is updated 42 // in each operation. 43 44 // since the algorithem is executed in stages I have to remember data 45 // on the state. 46 private Node node; // The current operation is being done on it. 47 private int action;// The operation being performed (insert / delete) 48 private int stage; // The current stage of execution 49 50 // the constructor initialize the object fields. 51 RBTree()52 public RBTree() 53 { 54 root = treeNull; 55 node = treeNull; 56 num_of_nodes = 0; 57 height = 0; 58 action = NOP; 59 stage = 0; 60 } 61 62 // This method return the root of the tree. 63 getRoot()64 public Node getRoot() 65 { 66 return root; 67 } 68 69 // This method return the number of nodes in the tree. 70 getNodes()71 public int getNodes() 72 { 73 return num_of_nodes; 74 } 75 76 // This method return the heigth of the tree. 77 getHeight()78 public int getHeight() 79 { 80 return height; 81 } 82 83 84 85 // This method inserts k into the Red Black Tree 86 RBInsert(int k)87 public boolean RBInsert(int k) 88 { 89 90 Thread Pause = new Thread(); // this thread is used for delay 91 // between the stages. 92 if (action != NOP) // checking similar to the RB_Insert method 93 { 94 System.out.println 95 ("Only one operation can be done at a time."); 96 return false; 97 } 98 if (num_of_nodes == maxNodes) 99 { 100 System.out.println 101 ("The maximum nodes allowed is already reached."); 102 return false; 103 } 104 if (Search(k) == treeNull) // Check if there is already node with key k. 105 { 106 action = INSERT; 107 node = new Node(k); 108 node.setNode(Node.Left_son,treeNull); 109 node.setNode(Node.Right_son,treeNull); 110 node.setNode(Node.Parent,treeNull); 111 stage = 1; 112 while (stage != 0) // This is the loop that perform all the 113 { // operation steps. 114 InsertStep(); // perform one step 115 updateHeight(); // update the tree height 116 } 117 action = NOP; // set the action to NoOPretion. 118 return true; 119 } 120 else 121 System.out.println 122 ("Insertion failed. This key already exist."); 123 return false; 124 } 125 126 127 // This method deletes the element k from the Red Black tree 128 RBDelete(int k)129 public boolean RBDelete(int k) 130 { 131 Thread Pause = new Thread(); // this thread is used for delay 132 // between the stages. 133 if (action != NOP) 134 { // checking like in RB_Delete method 135 System.out.println 136 ("Only one operation can be done at a time."); 137 return false; 138 } 139 node = Search(k); 140 if (node != treeNull) // Check if there is a node with key k. 141 { 142 action = DELETE; 143 stage = 1; 144 while (stage != 0) // this loop perform all the operation 145 { // steps. 146 DeleteStep(); // perform one step 147 updateHeight(); // update the tree height 148 149 } 150 action = NOP; 151 return true; 152 } 153 else 154 System.out.println 155 ("Deletion failed. This key doesn't exist."); 156 return false; 157 } 158 159 // This method perform one step in the insertion operation. 160 // If perform a step acording to the stage variable. 161 // I will not explain exactly what each stage do, just that they 162 // divided to 4 categories: 163 // 1. inserting a node to the tree. 164 // 2. marking nodes that will be recolored. 165 // 3. recoloring nodes. 166 // 4. rotating right or left. 167 InsertStep()168 private void InsertStep() 169 { 170 Node Pr,GrPr,Un; // Pr is parent, GrPr is grandparent 171 // and Un is uncle. 172 switch (stage) 173 { 174 case 1: // Inserting a node to the tree 175 /* 176 System.out.println // send a message to the screen 177 (new String("Inserting ") 178 .concat(Integer.toString(node.getKey()))); 179 */ 180 Tree_Insert(); // inserting an element to the tree 181 break; 182 case 2: // mid stage that move to algorithem to the 183 // proper next stage, and send proper message 184 // to the screen 185 Pr = node.getNode(Node.Parent); 186 GrPr = Pr.getNode(Node.Parent); 187 if (Pr == GrPr.getNode(Node.Left_son)) 188 { 189 Un = GrPr.getNode(Node.Right_son); 190 if (Un.getColor() == Node.Red) 191 { 192 stage = 3; 193 } 194 else 195 if (node == Pr.getNode(Node.Right_son)) 196 { 197 node = Pr; 198 stage = 5; 199 } 200 else 201 { 202 stage = 6; 203 } 204 } 205 else 206 { 207 Un = GrPr.getNode(Node.Left_son); 208 if (Un.getColor() == Node.Red) 209 { 210 stage = 3; 211 } 212 else 213 if (node == Pr.getNode(Node.Left_son)) 214 { 215 node = Pr; 216 stage = 5; 217 } 218 else 219 { 220 stage = 6; 221 } 222 } 223 break; 224 case 3: // This stage marks node that will be recolored 225 Pr = node.getNode(Node.Parent); 226 GrPr = Pr.getNode(Node.Parent); 227 if (Pr == GrPr.getNode(Node.Left_son)) 228 Un = GrPr.getNode(Node.Right_son); 229 else 230 Un = GrPr.getNode(Node.Left_son); 231 232 node = GrPr; 233 stage = 4; 234 break; 235 case 4: // this stage recolor marked nodes. 236 node.setColor(Node.Red); 237 (node.getNode(Node.Left_son)).setColor(Node.Black); 238 (node.getNode(Node.Right_son)).setColor(Node.Black); 239 240 if ((node == root) || 241 ((node.getNode(Node.Parent)).getColor() == Node.Black)) 242 if (root.getColor() == Node.Red) 243 { 244 stage = 9; 245 } 246 else 247 stage = 0; 248 else 249 { 250 stage = 2; 251 InsertStep(); 252 } 253 break; 254 case 5: // This stage perform rotation operation 255 Pr = node.getNode(Node.Parent); 256 if (node == Pr.getNode(Node.Left_son)) 257 Left_Rotate(node); 258 else 259 Right_Rotate(node); 260 261 stage = 6; 262 break; 263 case 6: // This stage marks nodes that will be recolor. 264 Pr = node.getNode(Node.Parent); 265 GrPr = Pr.getNode(Node.Parent); 266 267 stage = 7; 268 break; 269 case 7: // This stage recolor marked nodes. 270 Pr = node.getNode(Node.Parent); 271 Pr.setColor(Node.Black); 272 GrPr = Pr.getNode(Node.Parent); 273 GrPr.setColor(Node.Red); 274 275 stage = 8; 276 break; 277 case 8: // This stage perform rotation operation 278 Pr = node.getNode(Node.Parent); 279 GrPr = Pr.getNode(Node.Parent); 280 if (Pr == GrPr.getNode(Node.Left_son)) 281 Right_Rotate(GrPr); 282 else 283 Left_Rotate(GrPr); 284 if (root.getColor() == Node.Red) 285 { 286 stage = 9; 287 } 288 else 289 stage = 0; 290 break; 291 case 9: // this stage mark the root. 292 stage = 10; 293 break; 294 case 10: // This stage recolor the root. 295 root.setColor(Node.Black); 296 stage = 0; 297 break; 298 } 299 } 300 301 // This method perform one step in the deletion operation. 302 // If perform a step acording to the stage variable. 303 // I will explain exactly what each stage do, just that they 304 // divided to 4 categories: 305 // 1. deleting a node from the tree. 306 // 2. marking nodes that will be recolored. 307 // 3. recoloring nodes. 308 // 4. rotating right or left. 309 DeleteStep()310 public void DeleteStep() 311 { 312 Node Pr,Br; // Pr is Parent ,Br is Brother 313 switch (stage) 314 { 315 case 1: // This stage delete a node from the tree. 316 /* 317 System.out.println 318 (new String("Deleting ") 319 .concat(Integer.toString(node.getKey()))); 320 */ 321 Tree_Delete(); 322 break; 323 case 2: // This stage marks a nodes that will be recolored 324 // or perform other stage. 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 if (Br.getColor() == Node.Red) 331 { 332 stage = 3; 333 } 334 else 335 if (((Br.getNode(Node.Right_son)).getColor() == Node.Black) 336 && ((Br.getNode(Node.Left_son)).getColor() == Node.Black)) 337 { 338 stage = 5; 339 DeleteStep(); 340 } 341 else 342 { 343 stage = 7; 344 DeleteStep(); 345 } 346 break; 347 case 3: // this stage recolor marked nodes. 348 Pr = node.getNode(Node.Parent); 349 if (node == Pr.getNode(Node.Left_son)) 350 { 351 Br = Pr.getNode(Node.Right_son); 352 353 } 354 else 355 { 356 Br = Pr.getNode(Node.Left_son); 357 } 358 Br.setColor(Node.Black); 359 Pr.setColor(Node.Red); 360 361 stage = 4; 362 break; 363 case 4: // this stage perform rotation operation 364 Pr = node.getNode(Node.Parent); 365 if (node == Pr.getNode(Node.Left_son)) 366 { 367 Left_Rotate(Pr); 368 Br = Pr.getNode(Node.Right_son); 369 } 370 else 371 { 372 Right_Rotate(Pr); 373 Br = Pr.getNode(Node.Left_son); 374 } 375 if (((Br.getNode(Node.Right_son)).getColor() == Node.Black) 376 && ((Br.getNode(Node.Left_son)).getColor() == Node.Black)) 377 stage = 5; 378 else 379 stage = 7; 380 381 break; 382 case 5: // this stage marks nodes that will be recolor. 383 Pr = node.getNode(Node.Parent); 384 if (node == Pr.getNode(Node.Left_son)) 385 Br = Pr.getNode(Node.Right_son); 386 else 387 Br = Pr.getNode(Node.Left_son); 388 389 stage = 6; 390 break; 391 case 6: // This stage recolor marked nodes. 392 Pr = node.getNode(Node.Parent); 393 if (node == Pr.getNode(Node.Left_son)) 394 Br = Pr.getNode(Node.Right_son); 395 else 396 Br = Pr.getNode(Node.Left_son); 397 Br.setColor(Node.Red); 398 node = Pr; 399 400 if ((node != root) && (node.getColor() == Node.Black)) 401 stage = 2; 402 else 403 if (node.getColor() == Node.Red) 404 { 405 stage = 13; 406 } 407 else 408 stage = 0; 409 break; 410 case 7: // this stage marks nodes that will be recolor 411 // or perform other stage. 412 Pr = node.getNode(Node.Parent); 413 if (node == Pr.getNode(Node.Left_son)) 414 { 415 Br = Pr.getNode(Node.Right_son); 416 if ((Br.getNode(Node.Right_son)).getColor() == Node.Black) 417 { 418 stage = 8; 419 } 420 else 421 { 422 stage = 10; 423 DeleteStep(); 424 } 425 } 426 else 427 { 428 Br = Pr.getNode(Node.Left_son); 429 if ((Br.getNode(Node.Left_son)).getColor() == Node.Black) 430 { 431 stage = 8; 432 } 433 else 434 { 435 stage = 10; 436 DeleteStep(); 437 } 438 } 439 break; 440 case 8: // this stage recolor marked nodes. 441 Pr = node.getNode(Node.Parent); 442 if (node == Pr.getNode(Node.Left_son)) 443 { 444 Br = Pr.getNode(Node.Right_son); 445 (Br.getNode(Node.Left_son)).setColor(Node.Black); 446 447 } 448 else 449 { 450 Br = Pr.getNode(Node.Left_son); 451 (Br.getNode(Node.Right_son)).setColor(Node.Black); 452 453 } 454 Br.setColor(Node.Red); 455 stage = 9; 456 break; 457 case 9: // this stage perform rotation operation 458 Pr = node.getNode(Node.Parent); 459 if (node == Pr.getNode(Node.Left_son)) 460 { 461 Br = Pr.getNode(Node.Right_son); 462 Right_Rotate(Br); 463 } 464 else 465 { 466 Br = Pr.getNode(Node.Left_son); 467 Left_Rotate(Br); 468 } 469 470 stage = 10; 471 break; 472 case 10: // This stage marks node that will be recolor. 473 474 Pr = node.getNode(Node.Parent); 475 if (node == Pr.getNode(Node.Left_son)) 476 { 477 Br = Pr.getNode(Node.Right_son); 478 } 479 else 480 { 481 Br = Pr.getNode(Node.Left_son); 482 } 483 484 stage = 11; 485 break; 486 case 11: // this stage recolor marked nodes. 487 Pr = node.getNode(Node.Parent); 488 if (node == Pr.getNode(Node.Left_son)) 489 { 490 Br = Pr.getNode(Node.Right_son); 491 (Br.getNode(Node.Right_son)).setColor(Node.Black); 492 } 493 else 494 { 495 Br = Pr.getNode(Node.Left_son); 496 (Br.getNode(Node.Left_son)).setColor(Node.Black); 497 498 } 499 if (Br.getColor() != Pr.getColor()) 500 Br.setColor(Pr.getColor()); 501 if (Pr.getColor() != Node.Black) 502 Pr.setColor(Node.Black); 503 504 stage = 12; 505 break; 506 case 12: // this stage perform rotation operation. 507 Pr = node.getNode(Node.Parent); 508 if (node == Pr.getNode(Node.Left_son)) 509 Left_Rotate(Pr); 510 else 511 Right_Rotate(Pr); 512 node = root; 513 if (node.getColor() == Node.Red) 514 { 515 stage = 13; 516 } 517 else 518 stage = 0; 519 break; 520 case 13: // this stage marks a node that will be recolor 521 stage = 14; 522 break; 523 case 14: // this stage recolor marked node. 524 node.setColor(Node.Black); 525 stage = 0; 526 break; 527 } 528 } 529 530 // This method insert the node 'node' to the tree. 531 // it called from the first stage in the InsertStep method. 532 // we 'dive' from the root to a leaf acording to the node key 533 // and insert the node in the proper place. 534 Tree_Insert()535 private void Tree_Insert() 536 { 537 Node n1,n2; 538 n1 = root; 539 n2 = treeNull; 540 while (n1 != treeNull) 541 { 542 n2 = n1; 543 if (node.getKey() < n1.getKey()) 544 n1 = n1.getNode(Node.Left_son); 545 else 546 n1 = n1.getNode(Node.Right_son); 547 } 548 node.setNode(Node.Parent,n2); 549 if (n2 == treeNull) 550 root = node; 551 else 552 { 553 if (node.getKey() < n2.getKey()) 554 n2.setNode(Node.Left_son,node); 555 else 556 n2.setNode(Node.Right_son,node); 557 } 558 //Parent.display.drawTree(); 559 // updating the insertion stage. 560 if ((node == root) || 561 ((node.getNode(Node.Parent)).getColor() == Node.Black)) 562 if (root.getColor() == Node.Red) 563 { 564 stage = 9; 565 } 566 else 567 stage = 0; 568 else 569 { 570 stage = 2; 571 InsertStep(); 572 } 573 num_of_nodes++; // increasing the number of nodes 574 } 575 576 // This method delete the node 'node' from the tree. 577 // it called from the first stage in the DeleteStep method. 578 // if node has at most one son we just remove it and connect 579 // his son and parent. If it has 2 sons we delete his successor 580 // that has at most one son and replace him with the successor. 581 Tree_Delete()582 private void Tree_Delete() 583 { 584 Node n1,n2,n3; 585 if ((node.getNode(Node.Left_son) == treeNull) || 586 (node.getNode(Node.Right_son) == treeNull)) 587 n1 = node; 588 else 589 n1 = Tree_Successor(node); 590 if (n1.getNode(node.Left_son) != treeNull) 591 n2 = n1.getNode(Node.Left_son); 592 else 593 n2 = n1.getNode(Node.Right_son); 594 595 n3 = n1.getNode(Node.Parent); 596 n2.setNode(Node.Parent,n3); 597 if (n3 == treeNull) 598 root = n2; 599 else 600 if (n1 == n3.getNode(Node.Left_son)) 601 n3.setNode(Node.Left_son,n2); 602 else 603 n3.setNode(Node.Right_son,n2); 604 605 if (n1 != node) 606 { 607 node.setKey(n1.getKey()); 608 } 609 610 611 node = n2; 612 if (n1.getColor() == Node.Black) 613 if ((node != root) && (node.getColor() == Node.Black)) 614 stage = 2; 615 else 616 if (node.getColor() == Node.Red) 617 stage = 13; 618 else 619 stage = 0; 620 else 621 stage = 0; 622 num_of_nodes--; // decrease the number of nodes. 623 } 624 625 // This method return the successor of the node n in the tree. 626 Tree_Successor(Node n)627 private Node Tree_Successor(Node n) 628 { 629 Node n1; 630 if (n.getNode(Node.Right_son) != treeNull) 631 { 632 n = n.getNode(Node.Right_son); 633 while (n.getNode(Node.Left_son) != treeNull) 634 n = n.getNode(Node.Left_son); 635 return n; 636 } 637 n1 = n.getNode(Node.Parent); 638 while ((n1 != treeNull) && (n == n1.getNode(Node.Right_son))) 639 { 640 n = n1; 641 n1 = n1.getNode(Node.Parent); 642 } 643 return n1; 644 } 645 646 // This method perform Left Rotation with n1. 647 Left_Rotate(Node n1)648 private void Left_Rotate(Node n1) 649 { 650 Node n2; 651 652 n2 = n1.getNode(Node.Right_son); 653 n1.setNode(Node.Right_son,n2.getNode(Node.Left_son)); 654 if (n2.getNode(Node.Left_son) != treeNull) 655 (n2.getNode(Node.Left_son)).setNode(Node.Parent,n1); 656 n2.setNode(Node.Parent,n1.getNode(Node.Parent)); 657 if (n1.getNode(Node.Parent) == treeNull) 658 root = n2; 659 else 660 if (n1 == (n1.getNode(Node.Parent)).getNode(Node.Left_son)) 661 (n1.getNode(Node.Parent)).setNode(Node.Left_son,n2); 662 else 663 (n1.getNode(Node.Parent)).setNode(Node.Right_son,n2); 664 n2.setNode(Node.Left_son,n1); 665 n1.setNode(Node.Parent,n2); 666 } 667 668 // This method perform Right Rotation with n1. 669 Right_Rotate(Node n1)670 private void Right_Rotate(Node n1) 671 { 672 Node n2; 673 674 n2 = n1.getNode(Node.Left_son); 675 n1.setNode(Node.Left_son,n2.getNode(Node.Right_son)); 676 if (n2.getNode(Node.Right_son) != treeNull) 677 (n2.getNode(Node.Right_son)).setNode(Node.Parent,n1); 678 n2.setNode(Node.Parent,n1.getNode(Node.Parent)); 679 if (n1.getNode(Node.Parent) == treeNull) 680 root = n2; 681 else 682 if (n1 == (n1.getNode(Node.Parent)).getNode(Node.Left_son)) 683 (n1.getNode(Node.Parent)).setNode(Node.Left_son,n2); 684 else 685 (n1.getNode(Node.Parent)).setNode(Node.Right_son,n2); 686 n2.setNode(Node.Right_son,n1); 687 n1.setNode(Node.Parent,n2); 688 } 689 690 // This method search the tree for a node with key 'key', and 691 // return the node on success otherwise treeNull. 692 Search(int key)693 public Node Search(int key) 694 { 695 Node node; 696 node = root; 697 while ((node != treeNull) && (key != node.getKey())) 698 if (key < node.getKey()) 699 node = node.getNode(Node.Left_son); 700 else 701 node = node.getNode(Node.Right_son); 702 return node; 703 } 704 705 // This method update the tree height it uses a recursive method 706 // findheight. 707 updateHeight()708 private void updateHeight() 709 { 710 height = 0; 711 if (root != treeNull) 712 findHeight(root,1); 713 } 714 715 // This is a recursive method that find a node height. 716 findHeight(Node n,int curr)717 private void findHeight(Node n,int curr) 718 { 719 if (height < curr) 720 height = curr; 721 if (n.getNode(Node.Left_son) != treeNull) 722 findHeight(n.getNode(Node.Left_son),curr+1); 723 if (n.getNode(Node.Right_son) != treeNull) 724 findHeight(n.getNode(Node.Right_son),curr+1); 725 } 726 727 } 728