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;
};
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;
}
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);
}
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;
}
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);
}
}
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);
}
}
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);
}
}
