Tree

AVL Tree Implementation

Pinterest LinkedIn Tumblr

Data structure Description

An AVL tree is another self-balanced binary search tree. The heights of the two child subtrees of any node differ by at most one; otherwise, rebalancing is done to restore this property. The AVL tree maintains an extra attribute in each node to balance the height.

The heights of two child subtree (left subtree and right subtree) of any node differ by at most one. If the property is not there, the AVL tree self-balance.

Write a program to implement AVL tree?

Algorithm Explanation

The height of an AVL tree is always O(Log n) where n is the number of nodes in the tree.
AVL tree supports the search, insert and delete operations.
Search operation searches the item from the AVL tree. Traversal operation traverses all the items from AVL tree and display the values.
The insert operation takes the input node and root node. The new node inserts into the root node and maintains the property of AVL tree.
Deletion the item form the AVL tree and self-balance the remaining tree nodes.

Source Code

package com.dsacode.DataStructre.avltree;
 
import java.util.Arrays;
 
class TreeNodeAVL {   
    TreeNodeAVL left, right;
    int data;
    int height;
 
    public TreeNodeAVL(){
        left = null;
        right = null;
        data = 0;
        height = 0;
    }
     
    public TreeNodeAVL(int n){
        left = null;
        right = null;
        data = n;
        height = 0;
    }    
}
 
public class AVLTreeImpl {
    private TreeNodeAVL root;    
      
    public AVLTreeImpl()  {
        root = null;
    }
     
    public boolean isEmpty() {
        return root == null;
    }
     
    public void makeEmpty()  {
        root = null;
    }
     
     
    public void insert(int data)  {
        root = insert(data, root);
    }
     
    private int height(TreeNodeAVL t )  {
        return t == null ? -1 : t.height;
    }
     
     
    private int max(int lhs, int rhs) {
        return lhs > rhs ? lhs : rhs;
    }
     
     
    private TreeNodeAVL insert(int x, TreeNodeAVL t) {
        if (t == null)
            t = new TreeNodeAVL(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
          ; 
        t.height = max( height( t.left ), height( t.right ) ) + 1;
        return t;
    }
     
          
    private TreeNodeAVL rotateWithLeftChild(TreeNodeAVL k2) {
        TreeNodeAVL 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;
    }
 
 
    private TreeNodeAVL rotateWithRightChild(TreeNodeAVL k1) {
        TreeNodeAVL 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;
    }
     
     private TreeNodeAVL doubleWithLeftChild(TreeNodeAVL k3){
        k3.left = rotateWithRightChild( k3.left );
        return rotateWithLeftChild( k3 );
    }
      
    private TreeNodeAVL doubleWithRightChild(TreeNodeAVL k1) {
        k1.right = rotateWithLeftChild( k1.right );
        return rotateWithRightChild( k1 );
    }   
     
     
    public int countNodes() {
        return countNodes(root);
    }
     
    private int countNodes(TreeNodeAVL r){
        if (r == null)
            return 0;
        else{
            int l = 1;
            l += countNodes(r.left);
            l += countNodes(r.right);
            return l;
        }
    }
     
 
    public boolean search(int val)  {
        return search(root, val);
    }
     
    private boolean search(TreeNodeAVL 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;
    }
 
    public void inorder() {
        inorder(root);
    }
     
    private void inorder(TreeNodeAVL r){
        if (r != null)
        {
            inorder(r.left);
            System.out.print(r.data +" ");
            inorder(r.right);
        }
    }
     
 
    public static void main(String[] args)
   {           
        int[] array={45,67,34,56,78,34,11,9};
         
       AVLTreeImpl avlt = new AVLTreeImpl();
 
       System.out.println("List of items from Array: " + Arrays.toString(array));
       for(int i : array)
           avlt.insert(i);
        
       System.out.print("List of Nodes from AVL tree: " + avlt.countNodes());
       avlt.inorder();
       System.out.println();
        
       System.out.println("Count Nodes from AVL tree: " + avlt.countNodes());
      
            
       System.out.println("search '78' from AVL tree: " + avlt.search(78));
             
   }
 
}

Output

List of items from Array: [45, 67, 34, 56, 78, 34, 11, 9]
List of Nodes from AVL tree: 79 11 34 45 56 67 78
Count Nodes from AVL tree: 7
search '78' from AVL tree: true

Source Explanation

Insert operation inserts element into the binary search tree.
The current node must be one of the ancestors of the newly inserted node. Update the height of the current node.
Get the balance about the current node. If balance factor is greater than 1, then the current node is unbalanced and the AVL tree are either in Left case or left the Right case.
If balance factor is less than -1, then the current node is unbalanced and we are either in the Right case or Right Left case.

Complexity

OperationsBest CaseAverage Caseworst Case
SearchO(log(n))O(log(n))
InsertionO(log n)O(log(n))
DeletionO(log n)O(log(n))

Real Applications

  1. Applications of set<>, TreeSet<>
  2. Used in dictionaries for effective searching

Reference

  1. http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c6347/A-Demo-of-an-AVL-Tree.htm
  2. https://en.wikipedia.org/wiki/AVL_tree
  3. http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html
  4. https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
  5. http://cs-study.blogspot.com/2012/11/avl-tree.html

Write A Comment