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;
 }
}
share|improve this question
2  
You cannot reasonably improve efficiency by simply "using less variables and data structures,less functions". The performance hit of reducing the number of variables used is often negligible and methods can potentially be inlined, anyway (so more isn't necessarily a bad thing, performance-wise). As a result, that's often a micro-optimization. If anything, the typical first step to improving performance would be to profile the code to identify slow areas. – Kat Sep 3 '15 at 15:57
    
@Mike All i want is optimization in any way if possible. – Sumeet Singh Sep 3 '15 at 16:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.