| /* |
| * Copyright (c) 2008, 2018, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| package jit.graph; |
| |
| import nsk.share.TestFailure; |
| |
| //import Node; |
| |
| // This class defines the tree object. |
| |
| public class RBTree |
| { |
| public final static int maxNodes = 70; // maximum nodes allowed. |
| public final static int INSERT = 0; // constants indicating |
| public final static int DELETE = 1; // the current operation |
| public final static int NOP = 2; |
| public final static Node treeNull = new Node(); // the tree NULL node. |
| |
| private Node root; |
| private int num_of_nodes; |
| private int height; // The tree heigth ,it is updated |
| // in each operation. |
| |
| // since the algorithem is executed in stages I have to remember data |
| // on the state. |
| private Node node; // The current operation is being done on it. |
| private int action;// The operation being performed (insert / delete) |
| private int stage; // The current stage of execution |
| |
| // the constructor initialize the object fields. |
| |
| public RBTree() |
| { |
| root = treeNull; |
| node = treeNull; |
| num_of_nodes = 0; |
| height = 0; |
| action = NOP; |
| stage = 0; |
| } |
| |
| // This method return the root of the tree. |
| |
| public Node getRoot() |
| { |
| return root; |
| } |
| |
| // This method return the number of nodes in the tree. |
| |
| public int getNodes() |
| { |
| return num_of_nodes; |
| } |
| |
| // This method return the heigth of the tree. |
| |
| public int getHeight() |
| { |
| return height; |
| } |
| |
| |
| |
| // This method inserts k into the Red Black Tree |
| |
| public boolean RBInsert(int k) |
| { |
| |
| Thread Pause = new Thread(); // this thread is used for delay |
| // between the stages. |
| if (action != NOP) // checking similar to the RB_Insert method |
| { |
| System.out.println |
| ("Only one operation can be done at a time."); |
| return false; |
| } |
| if (num_of_nodes == maxNodes) |
| { |
| System.out.println |
| ("The maximum nodes allowed is already reached."); |
| return false; |
| } |
| if (Search(k) == treeNull) // Check if there is already node with key k. |
| { |
| action = INSERT; |
| node = new Node(k); |
| node.setNode(Node.Left_son,treeNull); |
| node.setNode(Node.Right_son,treeNull); |
| node.setNode(Node.Parent,treeNull); |
| stage = 1; |
| while (stage != 0) // This is the loop that perform all the |
| { // operation steps. |
| InsertStep(); // perform one step |
| updateHeight(); // update the tree height |
| } |
| action = NOP; // set the action to NoOPretion. |
| return true; |
| } |
| else |
| System.out.println |
| ("Insertion failed. This key already exist."); |
| return false; |
| } |
| |
| |
| // This method deletes the element k from the Red Black tree |
| |
| public boolean RBDelete(int k) |
| { |
| Thread Pause = new Thread(); // this thread is used for delay |
| // between the stages. |
| if (action != NOP) |
| { // checking like in RB_Delete method |
| System.out.println |
| ("Only one operation can be done at a time."); |
| return false; |
| } |
| node = Search(k); |
| if (node != treeNull) // Check if there is a node with key k. |
| { |
| action = DELETE; |
| stage = 1; |
| while (stage != 0) // this loop perform all the operation |
| { // steps. |
| DeleteStep(); // perform one step |
| updateHeight(); // update the tree height |
| |
| } |
| action = NOP; |
| return true; |
| } |
| else |
| System.out.println |
| ("Deletion failed. This key doesn't exist."); |
| return false; |
| } |
| |
| // This method perform one step in the insertion operation. |
| // If perform a step acording to the stage variable. |
| // I will not explain exactly what each stage do, just that they |
| // divided to 4 categories: |
| // 1. inserting a node to the tree. |
| // 2. marking nodes that will be recolored. |
| // 3. recoloring nodes. |
| // 4. rotating right or left. |
| |
| private void InsertStep() |
| { |
| Node Pr,GrPr,Un; // Pr is parent, GrPr is grandparent |
| // and Un is uncle. |
| switch (stage) |
| { |
| case 1: // Inserting a node to the tree |
| /* |
| System.out.println // send a message to the screen |
| (new String("Inserting ") |
| .concat(Integer.toString(node.getKey()))); |
| */ |
| Tree_Insert(); // inserting an element to the tree |
| break; |
| case 2: // mid stage that move to algorithem to the |
| // proper next stage, and send proper message |
| // to the screen |
| Pr = node.getNode(Node.Parent); |
| GrPr = Pr.getNode(Node.Parent); |
| if (Pr == GrPr.getNode(Node.Left_son)) |
| { |
| Un = GrPr.getNode(Node.Right_son); |
| if (Un.getColor() == Node.Red) |
| { |
| stage = 3; |
| } |
| else |
| if (node == Pr.getNode(Node.Right_son)) |
| { |
| node = Pr; |
| stage = 5; |
| } |
| else |
| { |
| stage = 6; |
| } |
| } |
| else |
| { |
| Un = GrPr.getNode(Node.Left_son); |
| if (Un.getColor() == Node.Red) |
| { |
| stage = 3; |
| } |
| else |
| if (node == Pr.getNode(Node.Left_son)) |
| { |
| node = Pr; |
| stage = 5; |
| } |
| else |
| { |
| stage = 6; |
| } |
| } |
| break; |
| case 3: // This stage marks node that will be recolored |
| Pr = node.getNode(Node.Parent); |
| GrPr = Pr.getNode(Node.Parent); |
| if (Pr == GrPr.getNode(Node.Left_son)) |
| Un = GrPr.getNode(Node.Right_son); |
| else |
| Un = GrPr.getNode(Node.Left_son); |
| |
| node = GrPr; |
| stage = 4; |
| break; |
| case 4: // this stage recolor marked nodes. |
| node.setColor(Node.Red); |
| (node.getNode(Node.Left_son)).setColor(Node.Black); |
| (node.getNode(Node.Right_son)).setColor(Node.Black); |
| |
| if ((node == root) || |
| ((node.getNode(Node.Parent)).getColor() == Node.Black)) |
| if (root.getColor() == Node.Red) |
| { |
| stage = 9; |
| } |
| else |
| stage = 0; |
| else |
| { |
| stage = 2; |
| InsertStep(); |
| } |
| break; |
| case 5: // This stage perform rotation operation |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| Left_Rotate(node); |
| else |
| Right_Rotate(node); |
| |
| stage = 6; |
| break; |
| case 6: // This stage marks nodes that will be recolor. |
| Pr = node.getNode(Node.Parent); |
| GrPr = Pr.getNode(Node.Parent); |
| |
| stage = 7; |
| break; |
| case 7: // This stage recolor marked nodes. |
| Pr = node.getNode(Node.Parent); |
| Pr.setColor(Node.Black); |
| GrPr = Pr.getNode(Node.Parent); |
| GrPr.setColor(Node.Red); |
| |
| stage = 8; |
| break; |
| case 8: // This stage perform rotation operation |
| Pr = node.getNode(Node.Parent); |
| GrPr = Pr.getNode(Node.Parent); |
| if (Pr == GrPr.getNode(Node.Left_son)) |
| Right_Rotate(GrPr); |
| else |
| Left_Rotate(GrPr); |
| if (root.getColor() == Node.Red) |
| { |
| stage = 9; |
| } |
| else |
| stage = 0; |
| break; |
| case 9: // this stage mark the root. |
| stage = 10; |
| break; |
| case 10: // This stage recolor the root. |
| root.setColor(Node.Black); |
| stage = 0; |
| break; |
| } |
| } |
| |
| // This method perform one step in the deletion operation. |
| // If perform a step acording to the stage variable. |
| // I will explain exactly what each stage do, just that they |
| // divided to 4 categories: |
| // 1. deleting a node from the tree. |
| // 2. marking nodes that will be recolored. |
| // 3. recoloring nodes. |
| // 4. rotating right or left. |
| |
| public void DeleteStep() |
| { |
| Node Pr,Br; // Pr is Parent ,Br is Brother |
| switch (stage) |
| { |
| case 1: // This stage delete a node from the tree. |
| /* |
| System.out.println |
| (new String("Deleting ") |
| .concat(Integer.toString(node.getKey()))); |
| */ |
| Tree_Delete(); |
| break; |
| case 2: // This stage marks a nodes that will be recolored |
| // or perform other stage. |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| Br = Pr.getNode(Node.Right_son); |
| else |
| Br = Pr.getNode(Node.Left_son); |
| if (Br.getColor() == Node.Red) |
| { |
| stage = 3; |
| } |
| else |
| if (((Br.getNode(Node.Right_son)).getColor() == Node.Black) |
| && ((Br.getNode(Node.Left_son)).getColor() == Node.Black)) |
| { |
| stage = 5; |
| DeleteStep(); |
| } |
| else |
| { |
| stage = 7; |
| DeleteStep(); |
| } |
| break; |
| case 3: // this stage recolor marked nodes. |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| { |
| Br = Pr.getNode(Node.Right_son); |
| |
| } |
| else |
| { |
| Br = Pr.getNode(Node.Left_son); |
| } |
| Br.setColor(Node.Black); |
| Pr.setColor(Node.Red); |
| |
| stage = 4; |
| break; |
| case 4: // this stage perform rotation operation |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| { |
| Left_Rotate(Pr); |
| Br = Pr.getNode(Node.Right_son); |
| } |
| else |
| { |
| Right_Rotate(Pr); |
| Br = Pr.getNode(Node.Left_son); |
| } |
| if (((Br.getNode(Node.Right_son)).getColor() == Node.Black) |
| && ((Br.getNode(Node.Left_son)).getColor() == Node.Black)) |
| stage = 5; |
| else |
| stage = 7; |
| |
| break; |
| case 5: // this stage marks nodes that will be recolor. |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| Br = Pr.getNode(Node.Right_son); |
| else |
| Br = Pr.getNode(Node.Left_son); |
| |
| stage = 6; |
| break; |
| case 6: // This stage recolor marked nodes. |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| Br = Pr.getNode(Node.Right_son); |
| else |
| Br = Pr.getNode(Node.Left_son); |
| Br.setColor(Node.Red); |
| node = Pr; |
| |
| if ((node != root) && (node.getColor() == Node.Black)) |
| stage = 2; |
| else |
| if (node.getColor() == Node.Red) |
| { |
| stage = 13; |
| } |
| else |
| stage = 0; |
| break; |
| case 7: // this stage marks nodes that will be recolor |
| // or perform other stage. |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| { |
| Br = Pr.getNode(Node.Right_son); |
| if ((Br.getNode(Node.Right_son)).getColor() == Node.Black) |
| { |
| stage = 8; |
| } |
| else |
| { |
| stage = 10; |
| DeleteStep(); |
| } |
| } |
| else |
| { |
| Br = Pr.getNode(Node.Left_son); |
| if ((Br.getNode(Node.Left_son)).getColor() == Node.Black) |
| { |
| stage = 8; |
| } |
| else |
| { |
| stage = 10; |
| DeleteStep(); |
| } |
| } |
| break; |
| case 8: // this stage recolor marked nodes. |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| { |
| Br = Pr.getNode(Node.Right_son); |
| (Br.getNode(Node.Left_son)).setColor(Node.Black); |
| |
| } |
| else |
| { |
| Br = Pr.getNode(Node.Left_son); |
| (Br.getNode(Node.Right_son)).setColor(Node.Black); |
| |
| } |
| Br.setColor(Node.Red); |
| stage = 9; |
| break; |
| case 9: // this stage perform rotation operation |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| { |
| Br = Pr.getNode(Node.Right_son); |
| Right_Rotate(Br); |
| } |
| else |
| { |
| Br = Pr.getNode(Node.Left_son); |
| Left_Rotate(Br); |
| } |
| |
| stage = 10; |
| break; |
| case 10: // This stage marks node that will be recolor. |
| |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| { |
| Br = Pr.getNode(Node.Right_son); |
| } |
| else |
| { |
| Br = Pr.getNode(Node.Left_son); |
| } |
| |
| stage = 11; |
| break; |
| case 11: // this stage recolor marked nodes. |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| { |
| Br = Pr.getNode(Node.Right_son); |
| (Br.getNode(Node.Right_son)).setColor(Node.Black); |
| } |
| else |
| { |
| Br = Pr.getNode(Node.Left_son); |
| (Br.getNode(Node.Left_son)).setColor(Node.Black); |
| |
| } |
| if (Br.getColor() != Pr.getColor()) |
| Br.setColor(Pr.getColor()); |
| if (Pr.getColor() != Node.Black) |
| Pr.setColor(Node.Black); |
| |
| stage = 12; |
| break; |
| case 12: // this stage perform rotation operation. |
| Pr = node.getNode(Node.Parent); |
| if (node == Pr.getNode(Node.Left_son)) |
| Left_Rotate(Pr); |
| else |
| Right_Rotate(Pr); |
| node = root; |
| if (node.getColor() == Node.Red) |
| { |
| stage = 13; |
| } |
| else |
| stage = 0; |
| break; |
| case 13: // this stage marks a node that will be recolor |
| stage = 14; |
| break; |
| case 14: // this stage recolor marked node. |
| node.setColor(Node.Black); |
| stage = 0; |
| break; |
| } |
| } |
| |
| // This method insert the node 'node' to the tree. |
| // it called from the first stage in the InsertStep method. |
| // we 'dive' from the root to a leaf acording to the node key |
| // and insert the node in the proper place. |
| |
| private void Tree_Insert() |
| { |
| Node n1,n2; |
| n1 = root; |
| n2 = treeNull; |
| while (n1 != treeNull) |
| { |
| n2 = n1; |
| if (node.getKey() < n1.getKey()) |
| n1 = n1.getNode(Node.Left_son); |
| else |
| n1 = n1.getNode(Node.Right_son); |
| } |
| node.setNode(Node.Parent,n2); |
| if (n2 == treeNull) |
| root = node; |
| else |
| { |
| if (node.getKey() < n2.getKey()) |
| n2.setNode(Node.Left_son,node); |
| else |
| n2.setNode(Node.Right_son,node); |
| } |
| //Parent.display.drawTree(); |
| // updating the insertion stage. |
| if ((node == root) || |
| ((node.getNode(Node.Parent)).getColor() == Node.Black)) |
| if (root.getColor() == Node.Red) |
| { |
| stage = 9; |
| } |
| else |
| stage = 0; |
| else |
| { |
| stage = 2; |
| InsertStep(); |
| } |
| num_of_nodes++; // increasing the number of nodes |
| } |
| |
| // This method delete the node 'node' from the tree. |
| // it called from the first stage in the DeleteStep method. |
| // if node has at most one son we just remove it and connect |
| // his son and parent. If it has 2 sons we delete his successor |
| // that has at most one son and replace him with the successor. |
| |
| private void Tree_Delete() |
| { |
| Node n1,n2,n3; |
| if ((node.getNode(Node.Left_son) == treeNull) || |
| (node.getNode(Node.Right_son) == treeNull)) |
| n1 = node; |
| else |
| n1 = Tree_Successor(node); |
| if (n1.getNode(node.Left_son) != treeNull) |
| n2 = n1.getNode(Node.Left_son); |
| else |
| n2 = n1.getNode(Node.Right_son); |
| |
| n3 = n1.getNode(Node.Parent); |
| n2.setNode(Node.Parent,n3); |
| if (n3 == treeNull) |
| root = n2; |
| else |
| if (n1 == n3.getNode(Node.Left_son)) |
| n3.setNode(Node.Left_son,n2); |
| else |
| n3.setNode(Node.Right_son,n2); |
| |
| if (n1 != node) |
| { |
| node.setKey(n1.getKey()); |
| } |
| |
| |
| node = n2; |
| if (n1.getColor() == Node.Black) |
| if ((node != root) && (node.getColor() == Node.Black)) |
| stage = 2; |
| else |
| if (node.getColor() == Node.Red) |
| stage = 13; |
| else |
| stage = 0; |
| else |
| stage = 0; |
| num_of_nodes--; // decrease the number of nodes. |
| } |
| |
| // This method return the successor of the node n in the tree. |
| |
| private Node Tree_Successor(Node n) |
| { |
| Node n1; |
| if (n.getNode(Node.Right_son) != treeNull) |
| { |
| n = n.getNode(Node.Right_son); |
| while (n.getNode(Node.Left_son) != treeNull) |
| n = n.getNode(Node.Left_son); |
| return n; |
| } |
| n1 = n.getNode(Node.Parent); |
| while ((n1 != treeNull) && (n == n1.getNode(Node.Right_son))) |
| { |
| n = n1; |
| n1 = n1.getNode(Node.Parent); |
| } |
| return n1; |
| } |
| |
| // This method perform Left Rotation with n1. |
| |
| private void Left_Rotate(Node n1) |
| { |
| Node n2; |
| |
| n2 = n1.getNode(Node.Right_son); |
| n1.setNode(Node.Right_son,n2.getNode(Node.Left_son)); |
| if (n2.getNode(Node.Left_son) != treeNull) |
| (n2.getNode(Node.Left_son)).setNode(Node.Parent,n1); |
| n2.setNode(Node.Parent,n1.getNode(Node.Parent)); |
| if (n1.getNode(Node.Parent) == treeNull) |
| root = n2; |
| else |
| if (n1 == (n1.getNode(Node.Parent)).getNode(Node.Left_son)) |
| (n1.getNode(Node.Parent)).setNode(Node.Left_son,n2); |
| else |
| (n1.getNode(Node.Parent)).setNode(Node.Right_son,n2); |
| n2.setNode(Node.Left_son,n1); |
| n1.setNode(Node.Parent,n2); |
| } |
| |
| // This method perform Right Rotation with n1. |
| |
| private void Right_Rotate(Node n1) |
| { |
| Node n2; |
| |
| n2 = n1.getNode(Node.Left_son); |
| n1.setNode(Node.Left_son,n2.getNode(Node.Right_son)); |
| if (n2.getNode(Node.Right_son) != treeNull) |
| (n2.getNode(Node.Right_son)).setNode(Node.Parent,n1); |
| n2.setNode(Node.Parent,n1.getNode(Node.Parent)); |
| if (n1.getNode(Node.Parent) == treeNull) |
| root = n2; |
| else |
| if (n1 == (n1.getNode(Node.Parent)).getNode(Node.Left_son)) |
| (n1.getNode(Node.Parent)).setNode(Node.Left_son,n2); |
| else |
| (n1.getNode(Node.Parent)).setNode(Node.Right_son,n2); |
| n2.setNode(Node.Right_son,n1); |
| n1.setNode(Node.Parent,n2); |
| } |
| |
| // This method search the tree for a node with key 'key', and |
| // return the node on success otherwise treeNull. |
| |
| public Node Search(int key) |
| { |
| Node node; |
| node = root; |
| while ((node != treeNull) && (key != node.getKey())) |
| if (key < node.getKey()) |
| node = node.getNode(Node.Left_son); |
| else |
| node = node.getNode(Node.Right_son); |
| return node; |
| } |
| |
| // This method update the tree height it uses a recursive method |
| // findheight. |
| |
| private void updateHeight() |
| { |
| height = 0; |
| if (root != treeNull) |
| findHeight(root,1); |
| } |
| |
| // This is a recursive method that find a node height. |
| |
| private void findHeight(Node n,int curr) |
| { |
| if (height < curr) |
| height = curr; |
| if (n.getNode(Node.Left_son) != treeNull) |
| findHeight(n.getNode(Node.Left_son),curr+1); |
| if (n.getNode(Node.Right_son) != treeNull) |
| findHeight(n.getNode(Node.Right_son),curr+1); |
| } |
| |
| } |
