Please ignore the OOP aspects of the code for a moment and concentrate on the efficiency of code. I would be obliged if someone could suggest a way to shorten my AVL tree implementation, such as using fewer variables, data structures and functions and at the same time improving upon the elegance of the code.
import java.util.*;
class Avl
{
private static Queue<Node> st=new LinkedList<Node>();
private static Node root=null;
public static Node insert(Node x,int k)
{
if(x==null)
{
x=new Node(k,0);
return x;
}
else if(k>x.key)
{
x.right=insert(x.right,k);
st.add(x);
return x;
}
else
{
x.left=insert(x.left,k);
st.add(x);
return x;
}
}
public static void adjust_height()
{
while(!st.isEmpty())
{
Node x=st.poll();
int lh=get_height(x.left);
int rh=get_height(x.right);
if(Math.abs(lh-rh)<=1)
x.height=Math.max(lh,rh)+1;
else
{
if(rh>lh)
{
int l=get_height(x.right.left);
int r=get_height(x.right.right);
if(r>=l)//x is right heavy and right child is right heavy or balanced
rotate_left(x);
else//x is right heavy and its right child is left heavy
{
rotate_right(x.right);
rotate_left(x);
}
}
else
{
int l=get_height(x.left.left);
int r=get_height(x.left.right);
if(l>=r)//x is left heavy and its left child is left heavy or balanced
rotate_right(x);
else//x is left heavy and its left child is right heavy
{
rotate_left(x.left);
rotate_right(x);
}
}
}
}
}
public static void rotate_left(Node x)
{
Node parent=null;
Node n_p=x.right;
Node n_r_c=x.right.left;
x.right=n_r_c;
n_p.left=x;
x.height=Math.max(get_height(x.right),get_height(x.left))+1;
n_p.height=Math.max(get_height(n_p.right),get_height(n_p.left))+1;
if(st.isEmpty())
root=n_p;
else
{
parent=st.peek();
if(parent.right==x)
parent.right=n_p;
else parent.left=n_p;
}
}
public static void rotate_right(Node x)
{
Node parent=null;
Node n_p=x.left;
Node n_l_c=x.left.right;
n_p.right=x;
x.left=n_l_c;
x.height=Math.max(get_height(x.right),get_height(x.left))+1;
n_p.height=Math.max(get_height(n_p.right),get_height(n_p.left))+1;
if(st.isEmpty())
root=n_p;
else
{
parent=st.peek();
if(parent.right==x)
parent.right=n_p;
else parent.left=n_p;
}
}
public static int get_height(Node x)
{
if(x==null)
return -1;
else return x.height;
}
public static void iot(Node x)
{
if(x==null)
return;
iot(x.left);
System.out.println(x.key+" "+x.height);
iot(x.right);
}
public static void main(String []args)
{
root=insert(root,2);
adjust_height();st.clear();
root=insert(root,4);
adjust_height();st.clear();
root=insert(root,6);
adjust_height();st.clear();
root=insert(root,8);
adjust_height();st.clear();
root=insert(root,10);
adjust_height();st.clear();
iot(root);
}
}
class Node
{
int key;
int height;
Node left;
Node right;
Node(int key,int height)
{
this.key=key;
this.height=height;
this.left=null;
this.right=null;
}
}