An AVL tree is a self-balancing binary search tree. It was invented by G.M. Adelson-Velski and E.M. Landis. In an AVL tree, heights of the two paired subtrees of any node differ by at most one and maintain an O(logn) search time. An AVL tree has the following properties:

1. Every sub-tree is an AVL tree.

2. The sub-trees of every node differ in height by at most one.

The

**balance factor**of a node is the height of its left subtree minus the height of its right subtree (sometimes opposite) and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees. The following is an example for a balanced tree.Balance factor of root node = height of left sub-tree - height of right sub-tree. Here, "4" is the root node. Its balance factor =0.

The code for defining each node is,

struct avl_node {

int data;

struct avl_node *left;

struct avl_node *right;

};

int data;

struct avl_node *left;

struct avl_node *right;

};

The code for finding the balance factor is,

int find_height(struct avl_node *node)

{

int height=0;

if (node !=NULL){

int left_height= find_height(node ->left);

int right_height= find_height(node -> right);

int max=(left_height > right_height) ? left_height : right_height;

height = 1+ max;

}

return height;

}

int get_diff(struct avl_node *node)

{

int left_height=find_height(node -> left);

int right_height=find_height(node -> right);

int b_factor= left_height - right_height;

return b_factor;

}

{

int height=0;

if (node !=NULL){

int left_height= find_height(node ->left);

int right_height= find_height(node -> right);

int max=(left_height > right_height) ? left_height : right_height;

height = 1+ max;

}

return height;

}

int get_diff(struct avl_node *node)

{

int left_height=find_height(node -> left);

int right_height=find_height(node -> right);

int b_factor= left_height - right_height;

return b_factor;

}

**Operations on AVL Tree**

The basic operation that carried out on an unbalanced binary search tree is the tree rotations. It helps to restore the height balance of the sub-trees.

**Insertion**

After inserting a node, it is necessary to check whether the trees satisfies the rules of AVL. For each node checked, if the balance factor remains −1, 0, or +1 then no rotations are necessary. However, if the balance factor becomes ±2 then the subtree rooted at this node is unbalanced. Rotations are necessary in this case.

There are four cases which need to be considered. Let P be the root of the unbalanced subtree, with R and L denoting the right and left children of P respectively.

**1. Right-Right case**

If the balance factor of P is -2 then the right subtree outweights the left subtree of the given node, and the balance factor of the right child (R) must be checked. If the balance factor of R is -1, a

**single left rotation**(with P as the root) is needed.The code for Right-Right rotation is ,

struct avl_node* right_right_rotation(struct avl_node *parent)

{

struct avl_node *node1;

node1=parent ->right;

parent->right = node1 -> left;

node1 -> left= parent;

return node1;

}

**2. Right-Left case**

If the balance factor of P is -2 then the right subtree outweights the left subtree of the given node, and the balance factor of the right child (R) must be checked.

If the balance factor of R is +1, two different rotations are needed. The first rotation is a

**right****rotation**with R as the root. The second is the**left rotation**with P as the root (Right-Left case).The code for Right-Left rotation is,

struct avl_node* right_left_rotation(struct avl_node *parent)

{

struct avl_node *node1;

node1=parent -> right;

parent->right = left_left_rotation(node1);

return right_right_rotation(parent);

}

{

struct avl_node *node1;

node1=parent -> right;

parent->right = left_left_rotation(node1);

return right_right_rotation(parent);

}

**3. Left-Left case**

If the balance factor of P is +2, then the left subtree outweighs the right subtree of the given node, and the balance factor of the left child (L) must be checked.

If the balance factor of L is +1, a

**single right rotation**(with P as the root) is needed.Code for Left-Left rotation is,

struct avl_node* left_left_rotation(struct avl_node *parent)

{

struct avl_node *node1;

node1 = parent -> left;

parent -> left = node1 -> right;

node1 -> right = parent;

return node1;

}

{

struct avl_node *node1;

node1 = parent -> left;

parent -> left = node1 -> right;

node1 -> right = parent;

return node1;

}

**4. Left-Right case**

If the balance factor of P is +2, then the left subtree outweighs the right subtree of the given node, and the balance factor of the left child (L) must be checked. If the balance factor of L is -1, two different rotations are needed. The first rotation is a

**left rotation**with L as the root. The second is a**right rotation**with P as the root.Code for Left-Right rotation is,

struct avl_node* left_right_rotation(struct avl_node *parent)

{

struct avl_node *node1;

node1= parent -> left;

parent-> left = right_right_rotation(node1);

return left_left_rotation(parent);

}

The following figure shows the above four operations,

The following functions check the balance factor of the parent nodes, and will decide the necessary rotations,

struct avl_node* balancing(struct avl_node *node)

{

int b_f= get_diff(node);

if (b_f >1) {

if (get_diff(node->left) >0)

node=left_left_rotation(node);

else

node=left_right_rotation(node);

}

else if(b_f < -1) {

if(get_diff(node ->right) >0)

node=right_left_rotation(node);

else

node=right_right_rotation(node);

}

return node;

}

struct avl_node* insert(struct avl_node *root,int val)

{

if (root==NULL) {

root = (struct avl_node*) malloc(sizeof(struct avl_node));

root -> data = val;

root -> left = NULL;

root -> right = NULL;

return root;

}

else if (val < root->data) {

root->left = insert(root->left, val);

root=balancing(root);

}

else if (val > root->data) {

root->right = insert(root->right, val);

root=balancing(root);

}

return root;

}

**Tree traversal**

Three types of traversals are Inorder traversal, Preorder traversal and Postorder traversal.

**Inorder traversal**

To traverse a non-empty binary tree in

**inorder**, perform the following operations recursively at each node:- Traverse the left subtree.
- Visit the root.
- Traverse the right subtree.

Code for Inorder traversal is,

void inorder(struct avl_node *tree)

{

if(tree == NULL)

return;

else {

inorder(tree -> left);

printf("%d\t",tree ->data);

inorder(tree ->right);

}

{

if(tree == NULL)

return;

else {

inorder(tree -> left);

printf("%d\t",tree ->data);

inorder(tree ->right);

}

}

**2. preorder traversal**

To traverse a non-empty binary tree in

**preorder**, perform the following operations recursively at each node, starting with the root node:- Visit the root.
- Traverse the left subtree.
- Traverse the right subtree.

Code for preorder traversal is,

void preorder(struct avl_node *tree)

{

if(tree == NULL)

return;

else {

printf("%d\t", tree ->data);

preorder(tree ->left);

preorder(tree ->right);

}

}

{

if(tree == NULL)

return;

else {

printf("%d\t", tree ->data);

preorder(tree ->left);

preorder(tree ->right);

}

}

**3. Postorder traversal**

To traverse a non-empty binary tree in

**postorder**, perform the following operations recursively at each node:- Traverse the left subtree.
- Traverse the right subtree.
- Visit the root.

Code for postorder traversal is,

void postorder(struct avl_node *tree)

{

if(tree == NULL)

return;

else {

postorder(tree ->left);

postorder(tree ->right);

printf("%d\t",tree ->data);

}

}

{

if(tree == NULL)

return;

else {

postorder(tree ->left);

postorder(tree ->right);

printf("%d\t",tree ->data);

}

}

thanx a lot man

ReplyDeleteDeus te pague.

ReplyDeleteExcellent tutorial.. Thanks a ton..

ReplyDeleteGreat tutorial.. Thanks

ReplyDeleteYou should keep the height as part of the node and update it. Else You will end up calculating the height always

ReplyDeleteits great..:)

ReplyDeletegood way of programming... excellent

ReplyDeletelogic for deleting the node from a avl tree ??

ReplyDeletelogic for creating and inserting nodes of same key value ??

ReplyDeleteviz,. for

if (val == root->data)

{

.

.

.

} ??

Excellent explaination

ReplyDeletegood work man!!

ReplyDeleteGreat post! Could you figure out how an interface in R to this function would look like?

ReplyDeleteHow to make a insertion?

ReplyDeleteGood! Clearer implementation than others.

ReplyDelete