import java.lang.Thread; import MainWin; import Display; import Node; // This class define the tree object. public class Tree { public final static int maxNodes = 60; // 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 MainWin Parent; 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 Tree(MainWin p) { Parent = p; 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 loads a predefined tree public void load(int k) { if (k==1) { loadInsert(20,Node.Black); loadInsert(10,Node.Black); loadInsert(40,Node.Black); loadInsert(5,Node.Black); loadInsert(15,Node.Black); loadInsert(30,Node.Red); loadInsert(50,Node.Black); loadInsert(25,Node.Black); loadInsert(35,Node.Black); loadInsert(45,Node.Red); loadInsert(55,Node.Red); } else if (k==2) { loadInsert(200,Node.Black); loadInsert(100,Node.Black); loadInsert(400,Node.Black); loadInsert(50,Node.Black); loadInsert(150,Node.Black); loadInsert(300,Node.Red); loadInsert(500,Node.Black); loadInsert(250,Node.Black); loadInsert(350,Node.Black); loadInsert(450,Node.Red); loadInsert(550,Node.Red); } else if (k==3) { Parent.infopanel.setMessage // send message to the screen. ("Loaded extended example from CSE 2320/bpw"); loadInsert(120,Node.Black); loadInsert(40, Node.Red); loadInsert(160,Node.Black); loadInsert(20, Node.Black); loadInsert(80, Node.Black); loadInsert(140,Node.Black); loadInsert(180,Node.Black); loadInsert(10, Node.Black); loadInsert(30, Node.Black); loadInsert(60, Node.Red); loadInsert(100,Node.Red); loadInsert(130,Node.Red); loadInsert(150,Node.Red); loadInsert(170,Node.Red); loadInsert(50, Node.Black); loadInsert(70, Node.Black); loadInsert(90, Node.Black); loadInsert(110,Node.Black); } updateHeight(); action = NOP; stage = 0; Parent.infopanel.drawBar(); Parent.display.drawTree(); } private void loadInsert(int key,int color) { Node node; Node n1,n2; if (Search(key)!=treeNull) return; node = new Node(key); node.setNode(Node.Left_son,treeNull); // create & initialize node.setNode(Node.Right_son,treeNull); // a new node. node.setNode(Node.Parent,treeNull); node.setColor(color); 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); } num_of_nodes++; // increasing the number of nodes } // This method start an insertion operation with key = k // all the details are in the method's body. public boolean RB_Insert(int k) { if (action != NOP) // check first if we are in the middle of other { // other operation. Parent.infopanel.setMessage // send message to the screen. ("Only one operation can be done at a time."); return false; } if (num_of_nodes == maxNodes) // check if we already reach the { // max nodes allowed. Parent.infopanel.setMessage // send message to the screen. ("The maximum nodes allowed is already reached."); return false; } if (Search(k) == treeNull) // Check if there is already node with key k. { Parent.infopanel.setMessage // send message to the screen. ("Insertion started. Press 'Next' to continue"); System.out.println("Insertion at " + String.valueOf(k)); action = INSERT; // set the action node = new Node(k); node.setNode(Node.Left_son,treeNull); // create & initialize node.setNode(Node.Right_son,treeNull); // a new node. node.setNode(Node.Parent,treeNull); stage = 1; // set the stage return true; } else Parent.infopanel.setMessage // if the key exist send message. ("Insertion failed. This key already exist."); return false; } // This method insert k to the tree it performs all the operation // steps i.e. this isn't interactive mode. public boolean fastRB_Insert(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 { Parent.infopanel.setMessage ("Only one operation can be done at a time."); return false; } if (num_of_nodes == maxNodes) { Parent.infopanel.setMessage ("The maximum nodes allowed is already reached."); return false; } if (Search(k) == treeNull) // Check if there is already node with key k. { Parent.infopanel.setMessage("Insertion started."); 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 Parent.infopanel.drawBar(); // draw the height bar. try { Pause.sleep(500); } catch(Exception e) {} } action = NOP; // set the action to NoOPretion. Parent.infopanel.setMessage(""); // clean the message area return true; } else Parent.infopanel.setMessage ("Insertion failed. This key already exist."); return false; } // This method start a deletion operation of node with key = k // all the details are in the method body. public boolean RB_Delete(int k) { if (action != NOP) // check first if we are in the middle of other { // other operation. Parent.infopanel.setMessage // send a message to the screen ("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. { Parent.infopanel.setMessage // send a message to the screen ("Deletion started. Press 'Next' to continue"); System.out.println("Deletion at " + String.valueOf(k)); action = DELETE; // setting the action and the stage. stage = 1; return true; } else Parent.infopanel.setMessage // send a message to the screen ("Deletion failed. This key doesn't exist."); return false; } // This method delete the element k from the tree it performs all the // operation steps i.e. this isn't interactive mode. public boolean fastRB_Delete(int k) { Thread Pause = new Thread(); // this thread is used for delay // between the stages. if (action != NOP) { // checking like in RB_Delete method Parent.infopanel.setMessage ("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. { Parent.infopanel.setMessage("Deletion started."); action = DELETE; stage = 1; while (stage != 0) // this loop perform all the operation { // steps. DeleteStep(); // perform one step updateHeight(); // update the tree height Parent.infopanel.drawBar(); // draw the height bar try { Pause.sleep(500); // delay } catch(Exception e) {} } action = NOP; Parent.infopanel.setMessage(""); // clean the message area return true; } else Parent.infopanel.setMessage ("Deletion failed. This key doesn't exist."); return false; } // This method is used in interactive mode, i.e when it called it // check what operation is performed and performs one step public void nextStep() { switch (action) { case INSERT: InsertStep(); // perform one step updateHeight(); Parent.infopanel.drawBar(); if (stage == 0) // if this was the last step { // updating the action and and the button state. action = NOP; Parent.ctrlpanel.next.disable(); Parent.ctrlpanel.insert.enable(); Parent.ctrlpanel.delete.enable(); Parent.ctrlpanel.clear.enable(); Parent.infopanel.setMessage(""); } break; case DELETE: DeleteStep(); // perform one step updateHeight(); Parent.infopanel.drawBar(); if (stage == 0) // if it is the last step { // updating the action and and the button state. action = NOP; Parent.ctrlpanel.next.disable(); Parent.ctrlpanel.insert.enable(); if (num_of_nodes == 0) { Parent.ctrlpanel.clear.disable(); Parent.ctrlpanel.demo.enable(); Parent.ctrlpanel.load.enable(); } else Parent.ctrlpanel.delete.enable(); Parent.infopanel.setMessage(""); } break; } } // 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 Parent.infopanel.setMessage // 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) { Parent.infopanel.setMessage ("Press 'Next' to continue."); System.out.println("Case 1 at node " + String.valueOf(node.getKey())); stage = 3; } else if (node == Pr.getNode(Node.Right_son)) { Parent.infopanel.setMessage (new String("Rotating Left with ") .concat(Integer.toString(Pr.getKey()))); System.out.println("Case 2 at node " + String.valueOf(node.getKey())); node = Pr; stage = 5; } else { Parent.infopanel.setMessage ("Press 'Next' to continue."); System.out.println("Case 3 at node " + String.valueOf(node.getKey())); stage = 6; } } else { Un = GrPr.getNode(Node.Left_son); if (Un.getColor() == Node.Red) { Parent.infopanel.setMessage ("Press 'Next' to continue."); System.out.println("Case ~1 at node " + String.valueOf(node.getKey())); stage = 3; } else if (node == Pr.getNode(Node.Left_son)) { Parent.infopanel.setMessage (new String("Rotating Left with "). concat(Integer.toString(Pr.getKey()))); System.out.println("Case ~2 at node " + String.valueOf(node.getKey())); node = Pr; stage = 5; } else { Parent.infopanel.setMessage ("Press 'Next' to continue."); System.out.println("Case ~3 at node " + String.valueOf(node.getKey())); 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); Parent.infopanel.setMessage("Recoloring the marked nodes."); Pr.setBold(Node.Bold); GrPr.setBold(Node.Bold); Un.setBold(Node.Bold); node = GrPr; Parent.display.drawTree(); 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); Parent.display.drawTree(); if ((node == root) || ((node.getNode(Node.Parent)).getColor() == Node.Black)) if (root.getColor() == Node.Red) { stage = 9; Parent.infopanel.setMessage ("Press 'Next' to continue."); } else stage = 0; else { System.out.println("Node " + String.valueOf( node.getKey()) + " & parent " + String.valueOf((node.getNode(Node.Parent)).getKey()) + " are red"); 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); System.out.println("Case 3 at node " + String.valueOf(node.getKey())); } else { Right_Rotate(node); System.out.println("Case ~3 at node " + String.valueOf(node.getKey())); } Parent.infopanel.setMessage("Press 'Next' to continue."); stage = 6; break; case 6: // This stage marks nodes that will be recolor. Pr = node.getNode(Node.Parent); GrPr = Pr.getNode(Node.Parent); Parent.infopanel.setMessage("Recoloring the marked nodes."); Pr.setBold(Node.Bold); GrPr.setBold(Node.Bold); Parent.display.drawTree(); 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); Parent.display.drawTree(); if (Pr == GrPr.getNode(Node.Left_son)) Parent.infopanel.setMessage (new String("Rotating Right with ") .concat(Integer.toString(GrPr.getKey()))); else Parent.infopanel.setMessage (new String("Rotating Left with ") .concat(Integer.toString(GrPr.getKey()))); 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; Parent.infopanel.setMessage("Press 'Next' to continue."); } else stage = 0; break; case 9: // this stage mark the root. Parent.infopanel.setMessage("Recoloring the marked nodes."); System.out.println("Root color change from red to black " + String.valueOf(root.getKey())); root.setBold(Node.Bold); Parent.display.drawTree(); stage = 10; break; case 10: // This stage recolor the root. root.setColor(Node.Black); Parent.display.drawTree(); 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. Parent.infopanel.setMessage (new String("Deleting ") .concat(Integer.toString(node.getKey()))); Tree_Delete(); Parent.infopanel.setMessage("Press 'Next' to continue."); 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) { Parent.infopanel.setMessage ("Recoloring the marked nodes."); if (node == Pr.getNode(Node.Left_son)) System.out.println("Case 1 at node " + String.valueOf(node.getKey())); else System.out.println("Case ~1 at node " + String.valueOf(node.getKey())); Br.setBold(Node.Bold); Pr.setBold(Node.Bold); Parent.display.drawTree(); 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); Parent.infopanel.setMessage (new String("Rotating Left with ") .concat(Integer.toString(node.getKey()))); } else { Br = Pr.getNode(Node.Left_son); Parent.infopanel.setMessage (new String("Rotating Right with ") .concat(Integer.toString(node.getKey()))); } Br.setColor(Node.Black); Pr.setColor(Node.Red); Parent.display.drawTree(); 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; Parent.infopanel.setMessage("Press 'Next' to continue."); break; case 5: // this stage marks nodes that will be recolor. Parent.infopanel.setMessage("Recoloring the marked nodes."); Pr = node.getNode(Node.Parent); if (node == Pr.getNode(Node.Left_son)) { Br = Pr.getNode(Node.Right_son); System.out.println("Case 2 at node " + String.valueOf(node.getKey())); } else { Br = Pr.getNode(Node.Left_son); System.out.println("Case ~2 at node " + String.valueOf(node.getKey())); } Br.setBold(Node.Bold); Parent.display.drawTree(); 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; Parent.display.drawTree(); if ((node != root) && (node.getColor() == Node.Black)) { stage = 2; System.out.println("CLR x node is " + String.valueOf(node.getKey())); } else if (node.getColor() == Node.Red) { stage = 13; Parent.infopanel.setMessage("Press 'Next' to continue."); } 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) { Parent.infopanel.setMessage("Recoloring the marked nodes."); System.out.println("Case 3 at node " + String.valueOf(node.getKey())); (Br.getNode(Node.Left_son)).setBold(Node.Bold); Br.setBold(Node.Bold); Parent.display.drawTree(); stage = 8; } else { stage = 10; DeleteStep(); } } else { Br = Pr.getNode(Node.Left_son); if ((Br.getNode(Node.Left_son)).getColor() == Node.Black) { Parent.infopanel.setMessage ("Recoloring the marked nodes."); System.out.println("Case ~3 at node " + String.valueOf(node.getKey())); (Br.getNode(Node.Right_son)).setBold(Node.Bold); Br.setBold(Node.Bold); Parent.display.drawTree(); 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); Parent.infopanel.setMessage (new String("Rotating Right with ") .concat(Integer.toString(Br.getKey()))); } else { Br = Pr.getNode(Node.Left_son); (Br.getNode(Node.Right_son)).setColor(Node.Black); Parent.infopanel.setMessage (new String("Rotating Left with ") .concat(Integer.toString(Br.getKey()))); } Br.setColor(Node.Red); Parent.display.drawTree(); 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); } Parent.display.drawTree(); stage = 10; Parent.infopanel.setMessage("Press 'Next' to continue."); break; case 10: // This stage marks node that will be recolor. Parent.infopanel.setMessage ("Recoloring the marked nodes."); Pr = node.getNode(Node.Parent); if (node == Pr.getNode(Node.Left_son)) { System.out.println("Case 4 at node " + String.valueOf(node.getKey())); Br = Pr.getNode(Node.Right_son); (Br.getNode(Node.Right_son)).setBold(Node.Bold); } else { System.out.println("Case ~4 at node " + String.valueOf(node.getKey())); Br = Pr.getNode(Node.Left_son); (Br.getNode(Node.Left_son)).setBold(Node.Bold); } if (Br.getColor() != Pr.getColor()) Br.setBold(Node.Bold); if (Pr.getColor() != Node.Black) Pr.setBold(Node.Bold); Parent.display.drawTree(); 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); Parent.infopanel.setMessage (new String("Rotating Left with ") .concat(Integer.toString(Pr.getKey()))); } else { Br = Pr.getNode(Node.Left_son); (Br.getNode(Node.Left_son)).setColor(Node.Black); Parent.infopanel.setMessage (new String("Rotating Right with ") .concat(Integer.toString(Pr.getKey()))); } if (Br.getColor() != Pr.getColor()) Br.setColor(Pr.getColor()); if (Pr.getColor() != Node.Black) Pr.setColor(Node.Black); Parent.display.drawTree(); 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; Parent.infopanel.setMessage("Press 'Next' to continue."); } else stage = 0; break; case 13: // this stage marks a node that will be recolor Parent.infopanel.setMessage ("Recoloring the marked nodes."); System.out.println("Node changes from red to black " + String.valueOf(node.getKey())); node.setBold(Node.Bold); Parent.display.drawTree(); stage = 14; break; case 14: // this stage recolor marked node. node.setColor(Node.Black); Parent.display.drawTree(); 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); if (n1 != treeNull) // here I call to the display method that show the path // on the tree. Parent.display.tokenMove(n2,n1); } 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) { Parent.infopanel.setMessage("Press 'Next' to continue."); 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); // here I call to the display method that show the deletion in // visual way. if (n1 != node) { Parent.display.nodeMove(n1,node,1); node.setKey(n1.getKey()); } if (n2 != treeNull) Parent.display.nodeMove(n2,n1,0); Parent.display.drawTree(); 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); Parent.display.drawTree(); } // 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); Parent.display.drawTree(); } // This method search the tree for a node with key 'key', and // return the node on success otherwise treeNull. private 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); } }