/*

     *  Java Program to Implement AVL Tree

     */

     

     import java.util.Scanner;

     

     /* Class AVLNode */

     class AVLNode

     {    

         AVLNode left, right;

         int data;

         int height;

     

         /* Constructor */

         public AVLNode()

         {

             left = null;

             right = null;

             data = 0;

             height = 0;

         }

         /* Constructor */

         public AVLNode(int n)

         {

             left = null;

             right = null;

             data = n;

             height = 0;

         }     

     }

     

     /* Class AVLTree */

     class AVLTree

     {

         private AVLNode root;     

     

         /* Constructor */

         public AVLTree()

         {

             root = null;

         }

         /* Function to check if tree is empty */

         public boolean isEmpty()

         {

             return root == null;

         }

         /* Make the tree logically empty */

         public void makeEmpty()

         {

             root = null;

         }

         /* Function to insert data */

         public void insert(int data)

         {

             root = insert(data, root);

         }

         /* Function to get height of node */

         private int height(AVLNode t )

         {

             return t == null ? -1 : t.height;

         }

         /* Function to max of left/right node */

         private int max(int lhs, int rhs)

         {

             return lhs > rhs ? lhs : rhs;

         }

         /* Function to insert data recursively */

         private AVLNode insert(int x, AVLNode t)

         {

             if (t == null)

                 t = new AVLNode(x);

             else if (x < t.data)

             {

                 t.left = insert( x, t.left );

                 if( height( t.left ) - height( t.right ) == 2 )

                     if( x < t.left.data )

                         t = rotateWithLeftChild( t );

                     else

                         t = doubleWithLeftChild( t );

             }

             else if( x > t.data )

             {

                 t.right = insert( x, t.right );

                 if( height( t.right ) - height( t.left ) == 2 )

                     if( x > t.right.data)

                         t = rotateWithRightChild( t );

                     else

                         t = doubleWithRightChild( t );

             }

             else

               ;  // Duplicate; do nothing

             t.height = max( height( t.left ), height( t.right ) ) + 1;

             return t;

         }

         /* Rotate binary tree node with left child */     

         private AVLNode rotateWithLeftChild(AVLNode k2)

         {

             AVLNode k1 = k2.left;

             k2.left = k1.right;

             k1.right = k2;

             k2.height = max( height( k2.left ), height( k2.right ) ) + 1;

             k1.height = max( height( k1.left ), k2.height ) + 1;

             return k1;

         }

     

         /* Rotate binary tree node with right child */

         private AVLNode rotateWithRightChild(AVLNode k1)

         {

             AVLNode k2 = k1.right;

             k1.right = k2.left;

             k2.left = k1;

             k1.height = max( height( k1.left ), height( k1.right ) ) + 1;

             k2.height = max( height( k2.right ), k1.height ) + 1;

             return k2;

         }

         /**

          * Double rotate binary tree node: first left child

          * with its right child; then node k3 with new left child */

         private AVLNode doubleWithLeftChild(AVLNode k3)

         {

             k3.left = rotateWithRightChild( k3.left );

             return rotateWithLeftChild( k3 );

         }

         /**

          * Double rotate binary tree node: first right child

          * with its left child; then node k1 with new right child */      

         private AVLNode doubleWithRightChild(AVLNode k1)

         {

             k1.right = rotateWithLeftChild( k1.right );

             return rotateWithRightChild( k1 );

         }    

         /* Functions to count number of nodes */

         public int countNodes()

         {

             return countNodes(root);

         }

         private int countNodes(AVLNode r)

         {

             if (r == null)

                 return 0;

             else

             {

                 int l = 1;

                 l += countNodes(r.left);

                 l += countNodes(r.right);

                 return l;

             }

         }

         /* Functions to search for an element */

         public boolean search(int val)

         {

             return search(root, val);

         }

         private boolean search(AVLNode r, int val)

         {

             boolean found = false;

             while ((r != null) && !found)

             {

                 int rval = r.data;

                 if (val < rval)

                     r = r.left;

                 else if (val > rval)

                     r = r.right;

                 else

                 {

                     found = true;

                     break;

                 }

                 found = search(r, val);

             }

             return found;

         }

         /* Function for inorder traversal */

         public void inorder()

         {

             inorder(root);

         }

         private void inorder(AVLNode r)

         {

             if (r != null)

             {

                 inorder(r.left);

                 System.out.print(r.data +" ");

                 inorder(r.right);

             }

         }

         /* Function for preorder traversal */

         public void preorder()

         {

             preorder(root);

         }

         private void preorder(AVLNode r)

         {

             if (r != null)

             {

                 System.out.print(r.data +" ");

                 preorder(r.left);             

                 preorder(r.right);

             }

         }

         /* Function for postorder traversal */

         public void postorder()

         {

             postorder(root);

         }

         private void postorder(AVLNode r)

         {

             if (r != null)

             {

                 postorder(r.left);             

                 postorder(r.right);

                 System.out.print(r.data +" ");

             }

         }     

     }

     

     /* Class AVL Tree Test */

     public class AVLTreeTest

     {

         public static void main(String[] args)

        {            

            Scanner scan = new Scanner(System.in);

            /* Creating object of AVLTree */

            AVLTree avlt = new AVLTree(); 

     

            System.out.println("AVLTree Tree Test\n");          

            char ch;

            /*  Perform tree operations  */

            do    

            {

                System.out.println("\nAVLTree Operations\n");

                System.out.println("1. insert ");

                System.out.println("2. search");

                System.out.println("3. count nodes");

                System.out.println("4. check empty");

                System.out.println("5. clear tree");

     

                int choice = scan.nextInt();            

                switch (choice)

                {

                case 1 : 

                    System.out.println("Enter integer element to insert");

                    avlt.insert( scan.nextInt() );                     

                    break;                          

                case 2 : 

                    System.out.println("Enter integer element to search");

                    System.out.println("Search result : "+ avlt.search( scan.nextInt() ));

                    break;                                          

                case 3 : 

                    System.out.println("Nodes = "+ avlt.countNodes());

                    break;     

                case 4 : 

                    System.out.println("Empty status = "+ avlt.isEmpty());

                    break;     

                case 5 : 

                    System.out.println("\nTree Cleared");

                    avlt.makeEmpty();

                    break;         

                default : 

                    System.out.println("Wrong Entry \n ");

                    break;   

                }

                /*  Display tree  */ 

                //System.out.print("\nPost order : ");

                //avlt.postorder();

                //System.out.print("\nPre order : ");

                //avlt.preorder();

                //System.out.print("\nIn order : ");

                //avlt.inorder();

     

                System.out.println("\nDo you want to continue (Type y or n) \n");

                ch = scan.next().charAt(0);                        

            } while (ch == 'Y'|| ch == 'y');               

        }

     }
     
     /*
     
     AVLTree Tree Test
     
     
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     4
     Empty status = true
      
     Post order :
     Pre order :
     In order :
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     10
      
     Post order : 10
     Pre order : 10
     In order : 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     9
      
     Post order : 9 10
     Pre order : 10 9
     In order : 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     8
      
     Post order : 8 10 9
     Pre order : 9 8 10
     In order : 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     7
      
     Post order : 7 8 10 9
     Pre order : 9 8 7 10
     In order : 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     6
      
     Post order : 6 8 7 10 9
     Pre order : 9 7 6 8 10
     In order : 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     5
      
     Post order : 5 6 8 10 9 7
     Pre order : 7 6 5 9 8 10
     In order : 5 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     4
      
     Post order : 4 6 5 8 10 9 7
     Pre order : 7 5 4 6 9 8 10
     In order : 4 5 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     3
      
     Post order : 3 4 6 5 8 10 9 7
     Pre order : 7 5 4 3 6 9 8 10
     In order : 3 4 5 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     2
      
     Post order : 2 4 3 6 5 8 10 9 7
     Pre order : 7 5 3 2 4 6 9 8 10
     In order : 2 3 4 5 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     1
      
     Post order : 1 2 4 6 5 3 8 10 9 7
     Pre order : 7 3 2 1 5 4 6 9 8 10
     In order : 1 2 3 4 5 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     1
     Enter integer element to insert
     0
      
     Post order : 0 2 1 4 6 5 3 8 10 9 7
     Pre order : 7 3 1 0 2 5 4 6 9 8 10
     In order : 0 1 2 3 4 5 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     3
     Nodes = 11
      
     Post order : 0 2 1 4 6 5 3 8 10 9 7
     Pre order : 7 3 1 0 2 5 4 6 9 8 10
     In order : 0 1 2 3 4 5 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     2
     Enter integer element to search
     12
     Search result : false
      
     Post order : 0 2 1 4 6 5 3 8 10 9 7
     Pre order : 7 3 1 0 2 5 4 6 9 8 10
     In order : 0 1 2 3 4 5 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     2
     Enter integer element to search
     4
     Search result : true
      
     Post order : 0 2 1 4 6 5 3 8 10 9 7
     Pre order : 7 3 1 0 2 5 4 6 9 8 10
     In order : 0 1 2 3 4 5 6 7 8 9 10
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     5
      
     Tree Cleared
      
     Post order :
     Pre order :
     In order :
     Do you want to continue (Type y or n)
      
     y
      
     AVLTree Operations
      
     1. insert
     2. search
     3. count nodes
     4. check empty
     5. clear tree
     4
     Empty status = true
      
     Post order :
     Pre order :
     In order :
     Do you want to continue (Type y or n)
      
     n
     */