import java.io.*;
import javax.*.*;
class node
{
int data;
node LC;
node RC;
int height;
}
class avltree
{
node root;node temp;
InputStreamReader x= new InputStreamReader(System.in);
BufferedReader buff=new BufferedReader(x);
public void insert()
{
try{
System.out.println("Enter element");
String element1= buff.readLine();
int element= Integer.parseInt(element1);
node temp=new node();
temp.data=element;
temp.RC=temp.LC=null;
if(root==null)
{
root=temp;
}
else
{
root=insertdata(root,element);
}
}
catch (IOException e)
{
System.exit(0);
}
}
public void print()
{
if(root==null)
System.out.println("Avl Tree is empty");
else
System.out.println("elements are");
display(root);
}
public void display(node t)
{
if (t!=null)
{
display(t.LC);
System.out.println("Data " +t.data + " " + "height" +t.height);
display(t.RC);
}
}
public node insertdata(node current,int element)
{
node temp1=new node();
temp1.data=element;
temp1.height=0;
temp1.LC=null;temp1.RC=null;
if (current==null)
current=temp1;
if(current.data>element)
{
current.LC=insertdata(current.LC,element);
if( (height(current.LC))- (height(current.RC))==2)
{
if(element<current.LC.data)
current=SL(current);
else
current=DRL(current);
}
}
else if (current.data<element)
{
current.RC=insertdata(current.RC,element);
if( (height(current.RC))- (height(current.LC))==2)
{
if(element>current.RC.data)
current=SR(current);
else
current=DRR(current);
}
}
current.height=Math.max(height(current.LC),height(current.RC))+1;
return current;
}
public void remove(int key)
{
root=delete(root,key);
}
public node delete(node t, int key)
{
if(t==null)
System.out.println("No elements present");
else if (key < t.data)
t.LC=delete(t.LC,key);
else if(key > t.data)
t.RC=delete(t.RC,key);
else if(t.LC!=null &&t.RC!=null)
{
node temp=findmin(t.RC);
t.data=temp.data;
t.RC=delete(t.RC,t.data);
//System.out.println("t value is "+t.data);//+","+t.height);
return t;
}
else if(t.LC ==null)
t=t.RC;
else if(t.RC ==null)
t=t.LC;
////System.out.println("t value is "+t.data+","+t.height);
if(t==null)
return t;
t.height=Math.max(height(t.LC),height(t.RC))+1;
int balance= height(t.LC)- height(t.RC);
//System.out.println("t value after return is "+t.data +","+t.height);
//System.out.println("balance is "+balance);
//System.out.println("After balancing");
//display(root);
if(balance== -2)
{
node temp1;
temp1=t.RC;
if(temp1.RC!=null)
{
t=SR(t);
}
else
t=DRR(t);
}
if(balance==2)
{
//System.out.println("In balance > 0");
node temp1;
temp1=t.LC;
if(temp1.LC!=null)
t=SL(t);
else
t=DRL(t);
}
return t;
}
public node findmin( node t)
{
if (t==null)
return t;
while(t.LC!=null)
{
t=t.LC;
}
return t;
}
public int height(node t)
{
if (t==null)
return -1;
else
return t.height;
}
public node SL(node k2)
{
node k1;
k1=k2.LC;
k2.LC=k1.RC;
k1.RC=k2;
k2.height=Math.max(height(k2.LC),height(k2.RC))+1;
k1.height=Math.max(height(k1.LC),k2.height)+1;
return k1;
}
public node SR(node k2)
{
node k1;
k1=k2.RC;
k2.RC=k1.LC;
k1.LC=k2;
k2.height=Math.max(height(k2.LC),height(k2.RC))+1;
k1.height=Math.max(height(k1.RC),k2.height)+1;
return k1;
}
public node DRL(node k2)
{
k2.LC=SR(k2.LC);
return(SL(k2));
}
public node DRR(node k2)
{
k2.RC=SL(k2.RC);
return(SR(k2));
}
}
public class avl
{
public static void main(String[] args)throws Exception
{
InputStreamReader x= new InputStreamReader(System.in);
BufferedReader buff=new BufferedReader(x);
avltree sa=new avltree();
int ans=1;
try{
while(ans==1)
{
System.out.println("1. INSERT 2. DELETE 3. PRINT 4.EXIT");
String option1= buff.readLine();
int option= Integer.parseInt(option1);
if(option==1)
{
sa.insert();
}
if(option==2)
{
System.out.println("Enter the element to be deleted");
String key1=buff.readLine();
int key=Integer.parseInt(key1);
sa.remove(key);
System.out.println("After Deletion");
sa.print();
}
if(option==3)
{
sa.print();
}
if(option==4)
{
System.exit(0);
}
}}catch (IOException e)
{
System.exit(0);
}
}
}