AVL Trees

Aim: - Implementation of AVL Tree for a given list of elements

An AVL tree is balanced binary search tree. Named after their inventors, Adelson, Velskii and Landis, they were the first dynamically balanced trees to be proposed.

The balance factor of a node is the height of its left subtree minus the height of its right subtree and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

There are four rotations to rebalance the AVL Tree based on the balance factor of a tree. These rotations come in two flavors

Single rotation 

 

 

Java program to implement AVL Tree

 

import java.io.*;

class BinarySTree{

    private Node root;

    private static class Node{

        Node left;

        Node right;

        int bal;

        int data;

         public Node(int cdata){

            left=null;

            right=null;

            data=cdata;

            bal=0;

         }

    }

    public BinarySTree()throws Exception {

            root=null;

    }

    public Node rotate(Node node) throws Exception {

         switch(node.bal)

        {

            case -2:

                 if(node.right.bal==-1){

                     System.out.println("  Left rotation    ");

                      return(rot_Left(node));

     }

                  System.out.println(" Right-Left rotation    ");

                  return(rot_RightLeft(node));

             case 2:

                if(node.left.bal==1){

                    System.out.println("  Right rotation    ");

                    return(rot_Right(node));

    }

                System.out.println("  Left-Right rotation    ");

                return(rot_LeftRight(node));

         }

         return node;

    }

    public Node rot_Left(Node node)  {

        Node temp=node.right;

        node.right=temp.left;

        temp.left=node;

        return temp;

    }

    public Node rot_Right(Node node)  {

        Node temp=node.left;

        node.left=temp.right;

        temp.right=node;

        return temp;

    }

 

    public Node rot_RightLeft(Node node)   {

        Node temp=node.right;

        node.right=temp.left.left;

        temp.left.left=node;

        return rot_Right(temp);

    }

    public Node rot_LeftRight(Node node)    {

        Node temp=node.left;

        node.left=temp.right.right;

        temp.right.right=node;

        return rot_Left(temp);

    }

    public Node findbal(Node node)throws Exception    {

        if(node!=null)

        {

          node.left=findbal(node.left);

          node.right=findbal(node.right);

          node.bal=height(node.left)-height(node.right);

          if(node.bal>1||node.bal<-1)

              node=rotate(node);

          return(node);

        }

        return node;

    }

    public void insert(int data)throws Exception    {

        root=insert(root,data);

        root=findbal(root);

    }

    public Node insert(Node node,int data){

    if(node==null)

                node=new Node(data);

    else

 if(data<=node.data)

                                node.left=insert(node.left, data);

    else

                node.right=insert(node.right, data);

    return(node);

    }

    public void Disp()throws Exception {

        if(root==null)

           System.out.println(" No Elements in the Tree ") ;

        else

        {

            System.out.println("\n Balanced Nodes in the AVL-Tree ") ;

            findbal(root);

            inorder(root);

            System.out.println("\n Height of the tree ===> "+height(root));

        }

    }

    public int height(Node node){

            if(node==null)

                  return(0);

             return max( height(node.left)+1, height(node.right)+1);

    }

 

    int max(int a,int b)   {

        return(a>b?a:b);

    }

  

 public void inorder(Node node){

        if(node!=null){

            inorder(node.left);

            System.out.println("   "+node.data+" bal("+node.bal+") ");

            inorder(node.right);

         }

    }

}

 

public class AVL {

    public static void main(String agrs[]) throws Exception  {

        BinarySTree B= new BinarySTree();

        int n, item,i=0;

        DataInputStream in= new DataInputStream(System.in);

        System.out.print("  Enter number of items to be inserted ");

        n=Integer.parseInt(in.readLine());

        while(i<n)

        {

             System.out.print("  Enter node "+(i+1)+":   ");

            item=Integer.parseInt(in.readLine());

            B.insert(item);

           i++;

        }

        B.Disp();

    }

}

 

 

OUTPUT:

Enter number of items to be inserted 7

  Enter node 1:  5

  Enter node 2:  6

  Enter node 3:  8

 Left rotation   

  Enter node 4:  3

  Enter node 5:  2

 Right rotation   

  Enter node 6:  4

 Left-Right rotation   

  Enter node 7:  7

 Right-Left rotation   

Balanced Nodes in the AVL-Tree

   2 bal(0)

   3 bal(0)

   4 bal(0)

   5 bal(0)

   6 bal(0)

   7 bal(0)

   8 bal(0)

Height of the tree ===> 3