public void RightRotate(Node wez) {
    			Node y=wez.getLeft();
    			wez.setLeft(y.getRight());
    			if(y.getRight()!=null) {
    				y.getRight().setParent(wez);
    			}
    			y.setParent(wez.getParent());
    			if(wez.getParent()==null) {
    				root=y;
    			}
    			else {
    				if(wez==wez.getParent().getRight()) {
    					wez.getParent().setRight(y);
    				}
    				else {
    					wez.getParent().setLeft(y);
    				}
    			}
    			y.setRight(wez);
    			wez.setParent(y);
    		}
     public void LeftRotate(Node wez) {
    		Node y=wez.getRight();
    		wez.setRight(y.getLeft());
    		if(y.getLeft()!=null) {
    			y.getLeft().setParent(wez);
    		}
    		y.setParent(wez.getParent());
    		if(wez.getParent()==null) {
    			root=y;
    		}
    		else {
    			if(wez==wez.getParent().getLeft()) {
    				wez.getParent().setLeft(y);
    			}
    			else {
    				wez.getParent().setRight(y);
    			}
    		}
    		y.setLeft(wez);
    		wez.setParent(y);


     }
     public void insert2(int key)throws DuplicateElementException{


    	 insert(key);



    	 Node x=find(key);
    	 while(x!=root&&x.getParent().getColor()=="R") {
    		 if(x.getParent()==x.getParent().getParent().getLeft()) {
    			 Node y=x.getParent().getParent();
    			 if(y.getColor()=="R") {
    				 x.getParent().setColor("B");
    				 y.setColor("B");
    				 x.getParent().getParent().setColor("R");
    				 x=x.getParent().getParent();
    			 }
    			 else{
    				 if(x==x.getParent().getRight()) {
    					 x=x.getParent();
    					 LeftRotate(x);
    				 }
    				 x.getParent().setColor("B");
    				 x.getParent().getParent().setColor("R");
    				 RightRotate(x.getParent().getParent());

    			 }
    		 }
    		 else {
    			 Node y=x.getParent().getParent();
    			 if(y.getColor()=="R") {
    				 x.getParent().setColor("B");
    				 y.setColor("B");
    				 x.getParent().getParent().setColor("R");
    				 x=x.getParent().getParent();
    			 }
    			 else{
    				 if(x==x.getParent().getLeft()) {
    					 x=x.getParent();
    					 RightRotate(x);
    				 }
    				 x.getParent().setColor("B");
    				 x.getParent().getParent().setColor("R");
    				 LeftRotate(x.getParent().getParent());
    			 }

    		 }
    	 }

    	 root.setColor("B");
     }
     public void rec(Node n) {
    	 if(n!=null) {
    		 if(n!=root&&n.getParent().getColor()=="R") {
    			 n.setColor("B");
    		 }
    		 rec(n.getLeft());
    		 rec(n.getRight());
    	 }
     }
     public void insert(int key)throws DuplicateElementException{

  	   root=insert(root,key);
  	   nodes++;
  	   }

     private Node insert(Node root, int key)throws DuplicateElementException {

  	   if(root==null)  {
  		   root=new Node(key);

  	        }
  	   else{
  		   if (key < root.getKey()) {


  	          Node lchild = insert(root.getLeft(), key);
  	          root.setLeft(lchild);
  	          lchild.setParent(root);




  	            }
  	        else if (key > root.getKey()) {
  	        	Node rchild = insert(root.getRight(), key);
    	          root.setRight(rchild);
    	          rchild.setParent(root);

  	        	}
  		   else

  			   throw new DuplicateElementException();
  		   }

  	   return root;
  	   }