Page 1 of 1

Data Structures- AVL Tree Tutorial Rate Topic: -----

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,113
  • Joined: 27-December 08

Posted 20 June 2011 - 07:26 PM

AVL Tree Tutorial

This tutorial will cover designing an AVL Tree data structure. An AVL Tree is a self-balancing binary search tree. This means that the heights of a given node's children trees are either the same or they differ by one. This is accomplished by rotating the tree nodes. Because the AVL Tree is self-balancing, all of its operations (insertion, lookup, and removal) all operate in O(log(n)) time.

Let's start by taking a look at the AVLNode class. It is a standard binary tree node, with a height() method, which is used in calculating the balance factor between two subtrees of a parent AVLNode. Also since this is a binary search tree, all the elements must be mutually Comparable, as denoted by the generic parametrization <E extends Comparable<? super E>>.
/**
 * @author: Michael Levet
 * @date: 6/20/2011
 *
 * This class represents a Node in an AVLTree, which is a
 * balanced binary search tree. As such, all the AVLNodes must be
 * mutually Comparable to properly order the elements. Each AVLNode
 * also maintains the balance factor for its subtrees. A balance factor
 * less than 0 indicates more elements to the left of this AVLNode, and a
 * balance factor greater than 0 indicates more elements to the right of
 * this AVLNode.
 * */
public class AVLNode<E extends Comparable<? super E>> {

   private AVLNode<E> left, right;
   private E element;

   //the default constructor used to initialize
   //this AVLNode with a null element
   public AVLNode(){
        this(null);
    }

   /**
    * @param element: The element this AVLNode is encapsulating
    *
    * The left and right children are initialized as empty.
    ***/
   public AVLNode(E element){
        this.element = element;
        left = right = null;
   }

   public E getElement(){ return element; }
   public void setElement(E element){ this.element = element; }
   
   public AVLNode<E> getLeft(){ return left; }
   public AVLNode<E> getRight(){ return right; }

   //the setLeft() and setRight() functions
   //simply set the elements for the left and right
   //AVLNodes. the actual ordering is handled by the
   //AVLTree class
   public void setLeft(E element){
       if(left == null)
          this.left = new AVLNode<E>(element);
       else
          this.left.setElement(element);
   }

   public void setRight(E element){
       if(right == null)
          this.right = new AVLNode<E>(element);
       else
          this.right.setElement(element);
   }

   public void setLeftNode(AVLNode<E> temp){
       this.left = temp;
   }

   public void setRightNode(AVLNode<E> temp){
        this.right = temp;
   }

   public int getBalance(){
        int leftHeight = (left == null)?0:left.height();
        int rightHeight = (right == null)?0:right.height();

        return rightHeight - leftHeight;
   }
   private int height(){
        int leftHeight = (left == null)?0:left.height();
        int rightHeight = (right == null)?0:right.height();

        return 1 + Math.max(leftHeight, rightHeight);

   }

   public String toString(){
        return assemble(this, 0);
   }

   private String assemble(AVLNode<E> temp, int offset){
       String ret= "";
       for(int i = 0; i < offset; i++)
           ret += "\t";

       ret += temp.getElement() + "\n";

       if(temp.getLeft() != null){
            ret += "Left: " + assemble(temp.getLeft(), offset + 1);
       }
       if(temp.getRight() != null){
            ret += "Right: " + assemble(temp.getRight(), offset + 1);
       }
       return ret;

   }
}





Next, let's take a look at the AVLTree. Like all trees, it supports the three basic operations: insertion, removal, and lookup. These will be the operations covered in this tutorial.

So for the AVLTree has a pretty standard setup for a binary search tree. The elements must be mutually Comparable, and the AVLTree is rooted. One thing to note is that the AVLNode instance field is called "rootAbove." This AVLNode's left child will point to the root node of the tree. Thus, the actual Tree structure being manipulated is actually a subtree of a placeholder node. Since the parent node's pointer is updated after a rotation, having an "invisible" parent for the root node simplifies things.
public class AVLTree<E extends Comparable<? super E>> {

       private AVLNode<E> rootAbove;

       public AVLTree(){
            rootAbove = new AVLNode<E>();
       }




Since balancing is a key component of the AVL Tree, let's examine the rotation functionality used to accomplish this. Binary tree rotations work by moving a child node b up to its parent's level, and making the parent node a child node. When this happens, the new parent node has an extra child, and the new child node has one fewer children. So to fix this, one of the new parent's children is set as a child of the old parent node.

Let's see this in action, with the following Tree:
         5
        / \
       4   7
          / \
         6   9
            /
           8
         



Now when this Tree is initially rotated to the right, it looks like:
       7
     / | \
    5  6  9
    |     |
    4     8



An AVL Tree is a binary search tree though, so each node can have at most two children. The new root (7) has three children, and the old root (5) only has one child. So to satisfy the binary search tree property, the 6 is removed from the 7 and set as the 5 node's right child. The Tree now looks like:
          7
        /   \
       5     9
      / \   /
     4   6 8



In fact, there are four specific cases to consider when rotating an AVL Tree. The first two include the left or right sides containing both the child and grandchildren nodes. Examples of such trees are shown below. In either of these cases, simply rotating the child node of the root will balance the tree.
//left-left          //right-right
     5                     3
    /                       \
   4                         4
  /                           \
3                              5   



The other two cases are where the grandchildren nodes are on the opposite sides of the child nodes. That is, in the Trees shown above, in the left tree, the 4 Node would have a right child; and in the right tree, the 4 would have a left child. These cases are balanced by rotating the grandchildren nodes up two levels.
//left-right          //right-left
         6                  6
        /                    \ 
       4                      5 
        \                    /
         5                  4




Below is the code used to rotate a subtree. Not only is the subtree (rotateBase) important, but the parent of rotateBase is vital because it is used to update its child pointer to the new root of the subtree. Here, cases one and two described above are the base cases of this method. For cases three and four, the double rotations, the first rotation is performed to set the subtree up for either cases one or two. Then a recursive call is made to the rotate() method to have cases one and two executed.
     /**
        * @param rotateBase: The root of the subtree that is being rotated
        * @param rootAbove: The AVLNode that points to rotateBase
        *
        * This method rotates the subtree balancing it to within a margin of |1|.
        * */
       public void rotate(AVLNode<E> rotateBase, AVLNode<E> rootAbove){
            int balance = rotateBase.getBalance();

            if(Math.abs(balance) < 2){
                System.out.println("No rotate");
            }

            //gets the child on the side with the greater height
            AVLNode<E> child = (balance < 0) ? rotateBase.getLeft() : rotateBase.getRight();

            if(child == null)
                return;
            
            int childBalance = child.getBalance();
            AVLNode<E> grandChild = null;

            //both the child and grandchild are on the
            //left side, so rotate the child up to the root position
            if(balance < -1 && childBalance < 0){
                 if(rootAbove != this.rootAbove && rootAbove.getRight() == rotateBase){
                     rootAbove.setRightNode(child);
                 }
                 else{
                     rootAbove.setLeftNode(child);
                 }

                 grandChild = child.getRight();
                 child.setRightNode(rotateBase);
                 rotateBase.setLeftNode(grandChild);
                 return;
            }

            //both the child and the grandchild are on the
            //right side, so rotate the child up to the root position
            else if(balance > 1 && childBalance > 0){
                if(rootAbove != this.rootAbove && rootAbove.getRight() == rotateBase){
                     rootAbove.setRightNode(child);
                }
                 else{
                     rootAbove.setLeftNode(child);
                }

                 grandChild = child.getLeft();
                 child.setLeftNode(rotateBase);
                 rotateBase.setRightNode(grandChild);
                 return;
            }

            //the child is on the left side, but the grandchild is on the
            //right side, so rotate the grandchild up to the child position
            //so the condition of the first if statement is satisfied,
            //then recurse to have the first if statement evaluated
            else if(balance < -1 && childBalance > 0){
                grandChild = child.getRight();
                rotateBase.setLeftNode(grandChild);
                child.setRightNode(grandChild.getLeft());
                grandChild.setLeftNode(child);
                rotate(rotateBase, rootAbove);
                return;
            }

            //the child is on the right side, but the grandchild is on the
            //left side, so rotate the grandchild up to the child position
            //so the condition of the second if statement is satisfied,
            //then recurse to have the second if statement evaluated
            else if(balance > 1 && childBalance < 0){
                grandChild = child.getLeft();
                rotateBase.setRightNode(grandChild);
                child.setLeftNode(grandChild.getRight());
                grandChild.setRightNode(child);
                rotate(rotateBase, rootAbove);
                return;
            }

       }



The first operation to examine is inserting elements into the tree. AVLTree insertions work exactly like standard binary search tree insertions. Each AVLNode that is recursively traversed according to the relation of the element to insert in comparison to the element of the given AVLNode. Once the bottom of the AVLTree has been reached, the element is inserted. After the actual insertion, the subtrees are recursively rebalanced from the bottom up based on the recursive insert() calls.
     /**
        * @param element: The element to insert into the Tree
        *
        * This method invokes a private helper method to insert the element.
        * It passes the root as the place to start.
        * */
       public void insert(E element){
           insert(element, rootAbove.getLeft());
       }

       /**
        * @param element: The element to insert into the Tree
        * @param temp: The AVLNode to evaluate for recursive insertion
        * 
        * This method recursively traverses the Tree, inserting the
        * element at the appropriate spot and incrementing the balance
        * factors for the subtrees as it evaluates. The Tree will then 
        * recursively rebalance as necessary.
        * */
       private void insert(E element, AVLNode<E> temp){
            if(this.rootAbove.getLeft() == null){
                this.rootAbove.setLeftNode(new AVLNode<E>(element));
                return;
            }

            //travel left or right based on the
            //comparison of element to temp.element
            //remember that left means that element <= temp.element
            //and right means element > temp.element
            int compare = element.compareTo(temp.getElement());
            

            //travel to the left of the Tree, inserting
            //if the bottom has been reached
            if(compare <= 0){

                //System.out.println(temp.getLeft());
                if(temp.getLeft() == null){
                    temp.setLeft(element);
                    return;
                }

                insert(element, temp.getLeft());
            }

            //otherwise, travelling to the right of the Tree,
            //inserting if the bottom has been reached
            else{

                if(temp.getRight() == null){
                    temp.setRight(element);
                    return;
                }

                insert(element, temp.getRight());

            }

            //if the root is being evaluated it, rotate if necessary
            if(temp == rootAbove.getLeft()){
                  rotate(rootAbove.getLeft(), rootAbove);
            }

            //otherwise, rotate the left and right subtrees
            //as necessary
            if(temp.getLeft() != null){
                rotate(temp.getLeft(), temp);
            }

            if(temp.getRight() != null){
                rotate(temp.getRight(), temp);
            }
           

       } //end insert




The next operation to examine is the remove() method. It works by traversing the AVLTree in search of the element. Once the element is found, it is removed and replaced with either the farthest right Node on the left hand side of the element, or the farthest left Node on the right-hand side of the element based on whichever side has the greater height. Each of these Nodes can have at most one child, on the opposite side of the traversal (ie., the right Ndoe can have a left child, and vice versa). This helps ensure not only the balance of the subtree, but also that the replacement will be less than the element's right child and greater than its left child.

Let's look at an example to better understand the concept. Below is a basic AVL Tree. In order to remove 60, a successor needs to be found such that 54 is less than it, and 66 is greater than it. Because the left side has the greater weight, the far-right child (57) is the new successor. Since 57 has a child, the 54 right node now points to 55, and 57 becomes the new root.
Before removing 60
     60                            
    /  \
   54  66
  / \   \
51  57  70
   /
  55



After removing 60
     57
    /  \
   54  66
  / \   \
51  55  70



Finally, let's examine the code to remove an element from an AVLTree:
  /**
      * @param element: The element to remove from the AVLTree
      * @param temp: The root node of the subtree
      *
      * This method recursively traverses the AVLTree based on
      * the ordering of the element with respect to the Tree's
      * elements. If the element is not found, then nothing happens.
      * Otherwise, the element is removed, and either the far-right
      * element on its left child or the far left element on its right
      * child replaces it.
      ***/
     private void remove(E element, AVLNode<E> temp){
         if(temp == null)
              return;

          int compare = 0;

          if(temp != rootAbove)
              compare = element.compareTo(temp.getElement());

          boolean direction = (compare > 0 && temp != rootAbove);

          AVLNode<E> child = direction ? temp.getRight() : temp.getLeft();

          if(child == null)
              return;

         //if the root is perfectly balanced, slide the left Node up
         //and reinsert the left.right element if necessary
          if(temp == rootAbove && child.getBalance() == 0
                  && child.getElement().equals(element)){
             
             AVLNode<E> newRoot = child.getLeft();

             if(newRoot == null){
                 rootAbove.setLeftNode(null);
                 return;
              }

            else{
                enactRemoval(temp, child, false);
                return;
            }
         }

          //if the element is found and the root is not
          // perfectly balanced, remove it using enactRemoval()
          else if(element.compareTo(child.getElement()) == 0){
              enactRemoval(temp, child, direction);
          }

          //otherwise, recursively traverse the tree
          else{
              remove(element, child);
          }

     }

     /**
      * @param parent: The parent of the element to be removed
      * @param remove: The element to remove from the Tree
      * @param direction: false if remove is to the left of parent, true otherwise
      *
      * This method physically removes the AVLNode with the element from the
      * AVLTree, replacing it with the appropriate successor.
      ***/
     private void enactRemoval(AVLNode<E> parent, AVLNode<E> remove, boolean direction){
         AVLNode<E> temp = null;
         AVLNode<E> left = remove.getLeft();
         AVLNode<E> right = remove.getRight();

         //if the Node to remove is not a leaf, find the appropriate successor
          if(left != null || right != null){
             temp = findSuccessor(remove);
          }

         //if remove is the right child of parent, update parent's right node
          if(direction && (parent != rootAbove)){
              parent.setRightNode(temp);
         }

         //otherwise, update its left node with the successor
          else
              parent.setLeftNode(temp);

         //and update temp to point to remove's children
          if(temp != null){

              if(temp != left){
                  temp.setLeftNode(remove.getLeft());
              }

              if(temp != right){
                  temp.setRightNode(remove.getRight());
              }
          }

          //and finally, discard those references from remove
         //so that the removed Node is garbage collected sooner
          remove.setLeftNode(null);
          remove.setRightNode(null);
     }

     /**
      * @param root: The element for which to find a successor AVLNode
      * @return AVLNode<E>: The successor Node
      ***/
     private AVLNode<E> findSuccessor(AVLNode<E> root){
          AVLNode<E> temp = root;
          AVLNode<E> parent = null;

          //if the balance favors the right, traverse right
          //otherwise, traverse left
          boolean direction = (temp.getBalance() > 0);

          parent = temp;
          temp = (direction) ? temp.getRight() : temp.getLeft();

          if(temp == null)
              return temp;

          //and find the farthest left-Node on the right side,
          //or the farthest right-Node on the left side
          while((temp.getRight() != null && !direction ) ||
                (temp.getLeft() != null && direction)){

                parent = temp;
                temp = (direction) ? temp.getLeft() : temp.getRight();
          }



         //finally, update the successor's parent's references
         //to adjust for a left child on the right node, or a right
          //child on the left-node
         if(temp == parent.getLeft()){
             parent.setLeftNode(temp.getRight());
             temp.setRightNode(null);
         }
         else{
             parent.setRightNode(temp.getLeft());
             temp.setLeftNode(null);
         }

         return temp;
     }





The final operation to examine is the simplest one- lookup. The contains() method is a standard binary search tree lookup method, traversing the AVLTree based on element's relations to the various AVLNodes until either a match is found or it hits the bottom of the AVLTree.
/**
        * @param element: The element to search for in the AVLTree
        * @return boolean: true if the element is found, false otherwise
        *
        * The contains method simply traverses the binary search tree based on
        * element's relation to the AVLNodes in the Tree until a match is found
        * or it hits the bottom of the Tree.
        * */
       public boolean contains(E element){

           AVLNode<E> temp = rootAbove.getLeft();

           while(temp != null){
                if(temp.getElement().equals(element))
                    return true;

                int balance = element.compareTo(temp.getElement());
                temp = (balance < 0) ? temp.getLeft() : temp.getRight();
           }

           return false;
       }



Conclusion
In conclusion, AVL Trees are very simple binary search trees that use a clever technique to rotate the tree and maintain balance, thus allowing for O(log(n)) insertion, removal and lookup time.

Is This A Good Question/Topic? 2
  • +

Replies To: Data Structures- AVL Tree Tutorial

#2 jroland  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-June 11

Posted 28 June 2011 - 11:15 AM

Hi

I have added the public method
public void remove(E element)
{
remove(element, rootAbove);
}
but I have a problem/bug, see my example, thanks

AVLTree<String> avlTree = new AVLTree<String>();

avlTree.insert("0");
avlTree.insert("1");
avlTree.insert("2");
avlTree.insert("3");

//
avlTree.remove("1");

//
System.out.println(avlTree.contains("3")); // return false
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,113
  • Joined: 27-December 08

Posted 28 June 2011 - 11:42 AM

I made a couple minor tweaks. The findSuccessor() method only sets the appropriate child to null, and the enactRemoval() method checks as well to make sure parent != rootAbove in this if statement if(temp != right){ before updating temp's right child. You should be good to go. :)
Was This Post Helpful? 0
  • +
  • -

#4 jroland  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-June 11

Posted 28 June 2011 - 01:05 PM

Hi I have again a problem

AVLTree<String> avlTree = new AVLTree<String>();
avlTree.insert("0");
avlTree.insert("1");
avlTree.insert("2");

avlTree.remove("1");

System.out.println(avlTree.contains("2")); // return false

Can you reproduce the problem?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,113
  • Joined: 27-December 08

Posted 28 June 2011 - 01:17 PM

Worked fine for me. Check to make sure you're using the remove() method I have posted.
Was This Post Helpful? 0
  • +
  • -

#6 jroland  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-June 11

Posted 28 June 2011 - 01:45 PM

You have right, I have take the new code but with a new sample

int nbre  = 3;
            for(int i = 0; i < nbre; i++)
              avlTree.insert(String.valueOf(i));

            avlTree.remove("0");

            for(int i = 0; i < nbre; i++)
            {
              if (! avlTree.contains(String.valueOf(i)))
                System.out.println(i+" not present");     // 1 not present????
            }


Can you reproduce the problem?
I have problem if i change the value of nbre.
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,113
  • Joined: 27-December 08

Posted 28 June 2011 - 02:50 PM

My code worked fine when I ran your test. I added a check with the last edit to make sure if the Tree was perfectly balanced at the root level and the root was to be removed, shift the left element up. Did you catch that edit as well?
Was This Post Helpful? 0
  • +
  • -

#8 jroland  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-June 11

Posted 29 June 2011 - 10:16 AM

I get your code but I have again a problem with another test.
Can you please send me your code? at jean dot roland at gmx dot com
Thanks
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,113
  • Joined: 27-December 08

Posted 29 June 2011 - 11:42 AM

My code is posted. You are welcome to copy/paste it as is.
Was This Post Helpful? 0
  • +
  • -

#10 jroland  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-June 11

Posted 29 June 2011 - 12:28 PM

I have a problem with this example

int nbre = 7;
for(int i = 0; i < nbre; i++)
  avlTree.insert(String.valueOf(i));

System.out.println(avlTree);

avlTree.remove("2");

for(int i = 0; i < nbre; i++)
{
  if (!avlTree.contains(String.valueOf(i)))
    System.out.println(i + " not present"); // I see that 2,4,5,6 are not present and not only 2
}


Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,113
  • Joined: 27-December 08

Posted 29 June 2011 - 02:43 PM

I ran my code and your sample worked fine for me. Try the code I have posted again.
Was This Post Helpful? 0
  • +
  • -

#12 jroland  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-June 11

Posted 30 June 2011 - 11:53 AM

Hi Michael
I have updated my code but I have again a problem : sorry (I have also a NullPointerException)
My test code
Thanks

    int nbre = 10; // you can change this value
    for(int i = 0; i < nbre; i++)
    {
      for(int j = 0; j < i; j++)
      {
        try
        {
          // check
          if (! check(i, j, false))
          {
            System.out.println();
            System.out.println("fail with check("+i+", "+j+")");
            check(i, j, true);
          }
        }
        catch(Exception e)
        {
          System.out.println();
          System.err.println("exception with check("+i+", "+j+")");
          e.printStackTrace();
        }
      }
    }

  public static boolean check(int nbre, int indexToRemove, boolean print)
  {
    // create avl tree
    AVLTree<Integer> avlTree = new AVLTree<Integer>();

    // insert value
    for(int i = 0; i < nbre; i++)
      avlTree.insert(i);

    // remove index
    avlTree.remove(indexToRemove);

    // check if index is deleted
    boolean result = true;
    int count = 0;

    for(int i = 0; i < nbre; i++)
    {
      if (!avlTree.contains(i))
      {
        count++;
        result &= (indexToRemove == i);

        if (print)
          System.out.println(i + " not present");
      }
    }

    return count == 1 && result;
  }


Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,113
  • Joined: 27-December 08

Posted 30 June 2011 - 06:52 PM

I ran your test with nbre at 200 for a large sample size and it worked fine for me. Try again with my code...
Was This Post Helpful? 0
  • +
  • -

#14 jroland  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-June 11

Posted 01 July 2011 - 11:03 AM

it works fine for me
Thanks
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1