package org.santhoshkumar;

public class AVLTree {

    public static void main(String[] args) {
	// write your code here
    }

    //          z                    z
    //        /  \                  / \
    //      T4   [y]       =      T4  [x]
    //           /  \                /  \
    //          T3  [x]            [y]  T2
    //              / \           /  \
    //             T1 T2         T3  T1
    public void leftRotation(Node y){
        Node x = y.right;
        Node T1 = x.left;

        //Rotation
        x.left = y;
        y.right = T1;

    }

    //          z
    //        /  \
    //      [y]    T4
    //     /  \
    //   [x]    T3
    //   / \
    //  T1 T2
    public void rightRotation(Node y){
        Node x = y.left;
        Node T2 = x.right;

        //Rotation
        x.right = y;
        y.left = T2;

        //Update height
    }

    public void insert(int data){

    }

}

class Node{
    Node left;
    Node right;
    int data;
    int height;
    Node(int data){
        this.data = data;
    }
    Node(int data, int height){
        this.data = data;
        this.height = height;
    }
}
@@ -45,16 +45,32 @@
 Tree %7B%0A%0A
+    Node root;%0A%0A
     publ
@@ -130,32 +130,73 @@
 ode here%0A    %7D%0A%0A
+    /*%0A    //                Rotate Left%0A
     //          
@@ -224,34 +224,34 @@
 z%0A    //        
-/
  
+/
  %5C              
@@ -274,13 +274,13 @@
     
+ 
 T4  
- 
 %5By%5D 
@@ -284,18 +284,18 @@
 y%5D      
- =
+-%3E
       T4
@@ -383,17 +383,17 @@
   %5By%5D  T
-2
+1
 %0A    // 
@@ -444,20 +444,20 @@
        T
-1 T2
+2 T1
         
@@ -462,17 +462,32 @@
    T3  T
-1
+2%0A    //%0A    */%0A
 %0A    pub
@@ -490,20 +490,20 @@
  public 
-void
+Node
  leftRot
@@ -557,17 +557,17 @@
   Node T
-1
+2
  = x.lef
@@ -632,139 +632,527 @@
  = T
-1;%0A%0A    %7D%0A%0A    //          z%0A    //        /  %5C%0A    //      %5By%5D    T4%0A    //     /  %5C%0A    //   %5Bx%5D    T3%0A    //   / %5C%0A    //  T1 T2
+2;%0A%0A        //Update height%0A        x.height = 1+Math.max(getHeight(x.left),getHeight(x.right));%0A        y.height = 1+Math.max(getHeight(y.left),getHeight(y.right));%0A%0A        return x;%0A    %7D%0A%0A    /*%0A    //               Rotate Right%0A    //          z                   z%0A    //        /  %5C                 / %5C%0A    //      %5By%5D   T4     -%3E      %5Bx%5D  T4%0A    //     /  %5C                /  %5C%0A    //   %5Bx%5D    T3            T1   %5By%5D%0A    //   / %5C                      /  %5C%0A    //  T1 T2                    T2  T3%0A    //%0A    */%0A
 %0A   
@@ -1159,20 +1159,20 @@
  public 
-void
+Node
  rightRo
@@ -1334,45 +1334,434 @@
     
-%7D%0A%0A    public void insert(int data)%7B%0A
+    x.height = 1+Math.max(getHeight(x.left),getHeight(x.right));%0A        y.height = 1+Math.max(getHeight(y.left),getHeight(y.right));%0A%0A        return x;%0A    %7D%0A%0A    public int getHeight(Node node)%7B%0A        if(node == null)%7B%0A            return 0;%0A        %7D%0A        return node.height;%0A    %7D%0A%0A    public Node insert(Node node, int data)%7B%0A        if(node == null)%7B%0A            return new Node(data);%0A        %7D%0A        return null;
 %0A   
@@ -1882,24 +1882,49 @@
 ata = data;%0A
+        this.height = 1;%0A
     %7D%0A    No

implement insert