Related Blog Items

• Binary Search Trees
• Printing Binary Trees in Ascii
• Data structures lectures
• Binary decimal conversion....
• Binary to decimal

An AVL (adelson-velskii-landis) tree also known as balanced tree is a binary search tree with a balance condition.
The balance condition is that for every node in the tree, the height of left and right subtrees can differ by at most 1. The condition ensures that the depth of the tree is O(log N).

      9                           9
     / \                         / \
    /   \                       /   \
   /     \                     /     \
  5      15                   5      15
 / \     /                   / \     / \
2   6   /                   2   6   /   \
       13                          13   20
      /                           /
     /                           /
    12                          12                

fig1:BST but               fig2:BST and is balanced(AVL) tree
not balanced tree

as the node 15 in fig1 is out of balance because height of left sub tree is 2 and height of right sub tree is 0.
You might be wondering how to compute height, here it is

height(Tree) = MAX(height(left-sub-tree), height(right-sub-tree)) + 1;

for example, height(9) = MAX(height(5), height(15)) + 1;
height(5) = MAX(height(2), height(6)) + 1 = 1;
height(15) = MAX(height(13), -1) + 1 = 2
so, height(5) = MAX(1, 2) + 1 = 3;

Maintaining height information of each node is necessary to check the balancing condition in AVL (balanced) tree.
So, here is the AVL (balanced) tree node representation

struct Tree 
{
  Tree * left, 
  Tree * right;
  int element;
  int height;
};

Here are the operations which are possible on Balanced (AVL) tree ADT,

1)Make Empty
2)Height
3)Find
4)FindMin
5)FindMax
6)Insert
7)Delete

All operations can be performed in O(log N) time, except possibly insertion. when we do an insertion, we need to update the balancing information for the nodes on the path back to root, but the reason that insertion is potentially difficult is that inserting a node could voilate the AVL (balanced) tree property. For example inserting 10 in fig2 would voilate the AVL tree property.
So, the inorder to maintain the balancing condition the tree has to be modified, this modification operation is called rotation.

Our algorithms used tail recursion, as the average depth of a binary search tree is O(log N),
the amount of stack space used is expected to be only O(log N).

1. Make Empty

This operation is for mainly intialization and can be used to destroy entire search tree also.

Tree *make_empty(Tree *t)
{
  if (t != NULL)
  {
    make_empty(t->left);
    make_empty(t->right);
    free(t);
    t = NULL;
  }
 
  return NULL;
}

2. Height

Finds height of the tree

int height(Tree *t)
{
  if (t == NULL)
  {
    return -1;
  }
  else
  {
    return t->height;
  }
}

3. Find

This operation returns a Tree node pointer in the search tree that has key X, or returns NULL if there is such node.
We make a recursive call on sub tree of the tree , either left or right, depending on the relationship of key X to the
element stored in the tree node

Tree *find(int elem, Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
 
  if (elem < t->element)
  {
    return find(elem, t->left);
  }
  else if (elem > t->element)
  {
    return find(elem, t->right);
  }
  else
  {
    return t;
  }
}

4. FindMin

This operation returns the smallest element node in the tree, i.e. left most element of the tree

Tree *find_min(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->left == NULL)
  {
    return t;
  }
  else
  {
    return find_min(t->left);
  }
}

5. FindMax

This operation returns the biggest element node in the tree, i.e. right most element of the tree

Tree *find_max(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->right == NULL)
  {
    return t;
  }
  else
  {
    return find_max(t->right);
  }
}

6. Insert

This operation applies a Find operation on the tree, if its found, does nothing., otherwise,
insert the element at the last spot on the path traversed. After insertion, only nodes that are on the path from the insertion point to the root might have their balance altered because only those nodes have their subtrees altered. As we follow up the path and update the balancing information, we may find a node whose new balance voilates the AVL (balance) condition. We need to rebalance the tree to satisfy AVL property. A violation of the AVL property may occur in four cases: (N is a node to be rebalanced)
1) An insertion into the left subtree of the left child of the node N
2) An insertion into the right subtree of the left child of the node N
3) An insertion into the left subtree of the right child of the node N
4) An insertion into the right subtree of the right child of the node N

cases 1 & 4 can be fixed by single rotation
cases 2 & 3 can be fixed by double rotation

single and double rotation will be explained after explaing insert and delete operations.

//Insert i into the tree t, duplicate will be discarded
//Return a pointer to the resulting tree.                 
Tree * insert(int value, Tree * t) 
{
  Tree * new_node;
  if (t == NULL) 
  {
    new_node = (Tree *) malloc (sizeof (Tree));
    if (new_node == NULL) 
    {
	    return t;
    }
 
    new_node->element = value;
    new_node->height = 0;
    new_node->left = new_node->right = NULL;
    return new_node;
  }
  else if (value < t->element) 
  {
    t->left = insert(value, t->left);
    if (height(t->left) - height(t->right) == 2)
    {
      if (value < t->left->element)
      {
        t = single_rotation_with_left(t);
      }
      else
      {
        t = double_rotation_with_left(t);
      }
    }
  } 
  else if (value > t->element) 
  {
    t->right = insert(value, t->right);
    if (height(t->right) - height(t->left) == 2)
    {
      if (value > t->right->element)
      {
        t = single_rotation_with_right(t);
      }
      else
      {
        t = double_rotation_with_right(t);
      }
    }
   } 
  //else duplicate, ignore it
 
  t->height = MAX(height(t->left), height(t->right)) + 1;
  return t;
}

7. Delete

This is the complicated operation among other tree operations. If the node to be deleted is a leaf, it can be deleted immediately. If the node has one child, the node can deleted after its parents adjusts a pointer to bypass the node. While deleting a node which has two children, the general strategy is to replace the data of this node with the smallest data of the right subtree and recursively delete that node.

After deletion, only nodes that are on the path from the deletion point to the root might have their balance altered because only those nodes have their subtrees altered. As we follow up the path and update the balancing information, we may find a node whose new balance voilates the AVL (balance) condition.
We need to rebalance the tree to satisfy AVL property using single and double rotation operations in similar way as we did for insertion operation.

Tree * delete(int value, Tree * t) 
{
  //Deletes node from the tree
  // Return a pointer to the resulting tree
 
  Tree * x;
  Tree *tmp_cell;
 
  if (t==NULL) return NULL;
 
  if (value < t->element) 
  {
    t->left = delete(value, t->left);
 
    if (height(t->right) - height(t->left) >= 2)
    {
      if (t->left && (value < t->left->element))
      {
        t = double_rotation_with_right(t);
      }
      else
      {
        t = single_rotation_with_right(t);
      }
    }
  } 
  else if (value > t->element) 
  {
    t->right = delete(value, t->right);
 
    if (height(t->left) - height(t->right) >= 2)
    {
      if (t->right && (value > t->right->element))
      {
        t = double_rotation_with_left(t);
      }
      else
      {
        t = single_rotation_with_left(t);
      }
    }
 
  } 
  else if (t->left && t->right)
  {
    tmp_cell = find_min(t->right);
    t->element = tmp_cell->element;
    t->right = delete(t->element, t->right);
  }
  else
  { 
    tmp_cell = t;
    if (t->left == NULL)
      t = t->right;
    else if (t->right == NULL)
      t = t->left;
    free(tmp_cell);
    tmp_cell = NULL;
  }
 
  return t;
}

Single Rotation

Single Rotation fixes voilations cause by the below cases (N is a node to be rebalanced)
1) An insertion into the left subtree of the left child of the node N
4) An insertion into the right subtree of the right child of the node N

Single Raotation does as below..

     k2                k1
     / \              /  \
    k1  z     -->    x    k2
   / \                   /  \
  x   y                 y    z              

examples for single rotation:

Before single rotating left at 20

   20
   /
  15
 /
5

After single rotating left

 15
 / \
5  20

Here is the code for single rotation..

//Single rotation left
//     k2                k1
//     / \              /  \
//    k1  z     -->    x    k2
//   / \                   /  \
//  x   y                 y    z              
Tree *single_rotation_with_left(Tree *k2)
{
  Tree *k1;
 
  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), height(k2->right)) + 1;
 
  //return new root
  return k1;
}
 
//Single rotation right
//     k2                k1
//     / \              /  \
//    x  k1     -->    k2   z
//       / \          /  \
//      y   z        x    y
Tree *single_rotation_with_right(Tree *k2)
{
  Tree *k1;
 
  k1 = k2->right;
  k2->right = k1->left;
  k1->left = k2;
 
  k2->height = MAX(height(k2->left), height(k2->right)) + 1;
  k1->height = MAX(height(k1->right), height(k2->left)) + 1;
 
  //return new root
  return k1;
}

Double Rotation

Single Rotation fixes voilations cause by the below cases (N is a node to be rebalanced)
2) An insertion into the right subtree of the left child of the node N
3) An insertion into the left subtree of the right child of the node N

Double Raotation does as below..

      k3                k2
     / \              /  \
    k1  d     -->    k1    k3
   / \              / \   /  \
  a   k2           a   b c    d
     /  \
    b    c

examples for double rotation:

Before double rotating right at 10

     10
    /  \
   5    15
      /  \
     12  16
      \
      13

After double rotating right

     12
    /  \
   10   15
  /    /  \
 5    13  16

Here is the code for single rotation..

//Double rotation left
//      k3                k2
//     / \              /  \
//    k1  d     -->    k1    k3
//   / \              / \   /  \
//  a   k2           a   b c    d   
//     /  \
//    b    c
Tree *double_rotation_with_left(Tree *k3)
{
  //rotate between k1 & k2
  k3->left = single_rotation_with_right(k3->left);
 
  //rotate between k3 & k2
  return single_rotation_with_left(k3);
}
 
//Double rotation right
//      k3                k2
//     / \               /  \
//    a   k1     -->   k3    k1
//       / \          / \   /  \
//      k2  d        a   b c    d   
//     /  \
//    b    c
Tree *double_rotation_with_right(Tree *k3)
{
  //rotate between k1 & k2
  k3->left = single_rotation_with_left(k3->right);
 
  //rotate between k3 & k2
  return single_rotation_with_right(k3);
}

Here are the operations examples..

After inserting element 20..
20

After inserting element 5..

 20
 /
5

After inserting element 15..

 15
 / \
5  20

After inserting elements 9, 13..

   15
   / \
  9  20
 / \
5  13

After inserting elements 2, 6, 12, 14, ..

      9
     / \
    /   \
   /     \
  5      15
 / \     / \
2   6   /   \
       13   20
      / \
     /   \
    12   14

After inserting elements 15..

      9
     / \
    /   \
   /     \
  5      15
 / \     / \
2   6   /   \
       13   20
      / \
     /   \
    12   14

After inserting elements 16..

      9
     / \
    /   \
   /     \
  5      15
 / \     / \
2   6   /   \
       /     \
      13     20
     / \     /
    /   \   16
   12   14

After inserting elements 17..

      9
     / \
    /   \
   /     \
  5      15
 / \     / \
2   6   /   \
       /     \
      /       \
     13       17
    / \       / \
   /   \     /   \
  12   14   16   20

After inserting elements 18..

          15
          / \
         /   \
        /     \
       /       \
      9        17
     / \       / \
    /   \     /   \
   /     \   16   20
  5      13       /
 / \     / \     18
2   6   /   \
       12   14

After inserting elements 19..

          15
          / \
         /   \
        /     \
       /       \
      9        17
     / \       / \
    /   \     /   \
   /     \   16   19
  5      13       / \
 / \     / \     /   \
2   6   /   \   18   20
       12   14

After deleting a node (14)

          15
          / \
         /   \
        /     \
       /       \
      9        17
     / \       / \
    /   \     /   \
   /     \   16   19
  5      13       / \
 / \     /       /   \
2   6   12      18   20

After deleting a node (13)

       15
       / \
      /   \
     /     \
    9      17
   / \     / \
  5  12   /   \
 / \     16   19
2   6         / \
             /   \
            18   20

After deleting a node (5)

       15
       / \
      /   \
     /     \
    9      17
   / \     / \
  6  12   /   \
 /       16   19
2             / \
             /   \
            18   20

After deleting a node (10)

       15
       / \
      /   \
     /     \
    9      17
   / \     / \
  6  12   /   \
 /       16   19
2             / \
             /   \
            18   20

After deleting a node (14, 15)

       16
       / \
      /   \
     /     \
    9      19
   / \     / \
  6  12   /   \
 /       17   20
2         \
          18

After deleting a node (16)

       17
       / \
      /   \
     /     \
    9      19
   / \     / \
  6  12   /   \
 /       18   20
2

After deleting a node (19)

       17
       / \
      /   \
     /     \
    9      20
   / \     /
  6  12   18
 /
2

After deleting a node (18, 20)

     9
    / \
   /   \
  6    17
 /     /
2     12

Download the AVL (Balanced) Tree Source Code [note: I’ve used some what old compiler(msvc6.0), if you are using a new compiler you may get some compilation errors, fix them yourself otherwise drop a message over here]

Popularity: 28%

You need to log on to convert this article into PDF

Related Blog Items

• Binary Search Trees
• Printing Binary Trees in Ascii
• Data structures lectures
• Binary decimal conversion....
• Binary to decimal

This entry was written by ponnada and posted on December 28, 2007 at 6:55 pm and filed under C Tidbits, Data Structures in C/C++. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.