In this tutorial blog we will see how to write c program for avl tree data structure.

what is avl tree?

avl tree is self balancing binary search tree such that

  • The sub-trees of every node differ in height by at most one. it means difference between height of left subtree and right subtree of any node of binary search tree lies in range of -1,0 or +1.
  • Every subtree itself is avl tree.
  • Difference in heights of left subtree and right subtree is also known as balance factor. In case of avl tree balance factor must be 1,0 or -1. For example see below figure ,left side bst tree is avl tree and right side bst tree is not an avl tree.

how to write c program for avl tree data structure

how to write c program for avl tree data structure

  • To implement avl tree and some operations on it , we need to first decide data structure.

  • Now , we need operations like below

Now let us implement insert operation

  • During implementation of insert operation on avl tree, we need to keep in mind following details
  1.  Insertion will be according to binary search tree.
  2.  After each insertion we need to find balance factor of ancestors node.
  3. If the balance factor is not in range of 1,-1 or 0 , it means we need to balance the avl tree. The balance factor will be calculated as (height of left subtree) – (height of right subtree).
  4. Let us see how to balance, For example let us insert 1 ,3, and 5 

From the tree we can see that the balance factor of node ( value 1) is disturbed and violates the avl tree property. From the diagram also we can see that the left side is heavier that the right side. To balance the tree we need left rotation.

  • Again let us insert 5,4 and 3 into a new avl tree.

From the tree we can see that the balance factor of node ( value 5) is disturbed and violates the avl tree property. From the diagram also we can see that the right side is heavier that the left side. To balance the tree we need right rotation.

The above two examples are the cases where to balance avl tree we need single right or left rotation. Let us see the cases where we need double rotation.

  • Left right Case:  ( Insert 5 , 3  and 4 )

  •  Right left Case:  ( Insert 3, 5  and 4 )

avl tree rotation

1) Left Left Case and c code

2) Right Right Case

Sample code for how to write c program for avl tree data structure

 

Ref:

http://home.iitj.ac.in/~ramana/avl-trees.pdf




Related Contents to follow