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.
typedef struct AVLtree {
	int val;
	struct AVLtree* left;
	struct AVLtree* right;
	int ht;
} AVLtree;
  • Now , we need operations like below
struct Node* insert(AVLtree* node, int value);
void delete(AVLtree *Node, int value);
struct node *search(AVLtree *node, int value);

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 
Insert 1:

     1     => the tree is balance
Insert 3:
   
      (1)  h=-1
      / \
         (3) h=0

The tree is balance
Insert 5: 
        (1) h=-2  == > here the balance factor is disturbed
        / \ 
           (3) h=-1
            \
             (5) h=0

 The tree is now not a balance tree

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.

  Not Balance                         after rotation
     (1)h=-2                               (3)
    /  \                                   /  \
      (3)h=-1    =====> left rotate      (1)  (5)
        \
        (5)h=0
  • Again let us insert 5,4 and 3 into a new avl tree.
Insert 5:

       (5) h=0
      /  \
insert 4

       (5) h=1
      /
    (4)h=0
insert 3

        (5) h=2
       /
     (4) h=1
     /
   (3) h=0

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.

       (5)                             (4)
      /                                /  \
    (4)     ==> rotate right ==>     (3)  (5)
   /
 (3)

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 )
   (5) h=-2                     (5)                     (4)
   /                            /                       / \
 (3) h=-1   ==> Left rotate   (4)   => right rotate   (3) (5)
   \                         /
    (4)h=0                 (3)
  •  Right left Case:  ( Insert 3, 5  and 4 )
  (3)                   (3)
   \                      \                       (4)
   (5) => right rotate    (4)  > rotate left      / \
  /                         \                   (3)  (5)
 (4)                        (5)

avl tree rotation

1) Left Left Case and c code

T1, T2, and T3 are subtrees.
         y                                      x 
        / \                                   /   \
       x   T3      Right Rotate              T1     y
      / \          - - - - - - - - ->             /  \ 
     T1  T2                                      T2  T3


AVLtree* right_rotate(AVLtree* y) {
	AVLtree* x = y->left;
	y->left = x-<right;
	update_height(y);

	x->right = y;
	update_height(x);
	return x;
}

2) Right Right Case

  x                                y
 /  \                            /   \ 
T1   y     Left Rotate          X    T3
    /  \   - - - - ->          / \
   T2   T3                    T1  T2

   
AVLtree* left_rotate(AVLtree* x) {
	AVLtree* y = x->right;
	x->right = y->left;;
	update_height(x);

	y->left = x;
	update_height(y);
	return y;
}

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

#include <stdio.h>
#include<stdlib.h>

typedef struct AVLtree {
	int val;
	struct AVLtree* left;
	struct AVLtree* right;
	int ht;
} AVLtree;

int height(AVLtree* root) {
	return (root != NULL) ? root->ht : -1;
}

int max(int m, int n) {
	if (m > n)
		return m;
	else
		return n;
}

void update_height(AVLtree* root) {
	root->ht = 1 + max(height(root->left), height(root->right));
}

int balance_factor(AVLtree* root) {
	if (root == NULL) {
		return 0;
	}
	return height(root->left) - height(root->right);
}

AVLtree* left_rotate(AVLtree* x) {
	AVLtree* y = x->right;
	x->right = y->left;
	update_height(x);

	y->left = x;
	update_height(y);
	return y;
}

AVLtree* right_rotate(AVLtree* y) {
	 AVLtree* x = y->left;
	y->left = x->right;
	update_height(y);

	x->right = y;
	update_height(x);
	return x;
}

AVLtree* insert(AVLtree* root, int value) {
	
if (root == NULL) {
		AVLtree *n = (AVLtree*) malloc(sizeof(node));
		n->val = value;
		n->left = NULL;
		n->right = NULL;
		n->ht = 0;
		return n;
	}

	// Insert value into the correct sub-tree.
	if (value < root->val) {
		root->left = insert(root->left, value);
	} else {
		root->right = insert(root->right, value);
	}

	// Rebalance the tree after insertion.
	int w = balance_factor(root);
     //detect Left-left case
     if (w > 1 && value < root->left->val)
        return right_rotate(root);
 
    // Detect Right Right Case
    if (w < -1 && value > root->right->val)
        return left_rotate(root);
 
    // Detect Left Right Case
    if (w > 1 && value > root->left->val)
    {
        root->left =  left_rotate(root->left);
        return right_rotate(root);
    }
 
    //detect Right Left Case
    if (w < -1 && value < root->right->val)
    {
        root->right = right_rotate(root->right);
        return left_rotate(root);
    }
	update_height(root);
	return root;
}

// free memory
void dispose(AVLtree *n) {
	if (n == NULL)
		return;
	dispose(n->left);
	dispose(n->right);
	free(n);
}

int isAVL(AVLtree *root) {
	if (root == NULL)
		return 1;

	int bf = height(root->left) - height(root->right);

	if (bf <= 1 && bf > -2 && isAVL(root->left) && isAVL(root->right))
		return 1;

	return 0;
}

void test() {
	AVLtree *root = NULL;
	root = insert(root, 1);
	root = insert(root, 2);
	root = insert(root, 3);
	root = insert(root, 4);
	root = insert(root, 6);
	root = insert(root, 8);

	printf("testing avlness...\n");
	if (isAVL(root))
		printf("AVL tree\n");
	else
		printf("Check your algo\n");
	//dispose avl tree
	dispose(root);
	root = NULL;
}

int main() {
	test();
	return 0;
}

 

Ref:

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



Related Contents to follow