AVL Tree – Introduction to rotations and its implementation

AVL tree is a self balancing binary search tree, where difference of right subtree and left subtree height to a node is at most 1.

A self-balancing binary tree is a binary tree that has some predefined structure, failing which the tree restructures itself. Examples of such tree are AVL Tree, Splay Tree, Red Black Tree etc.
Most of the operation in a BST(binary search tree) depends on the height of the tree and skewed structure is the worst case leads to O(n) time complexity. Therefore, whereas approaches are proposed. One of the popular ones is an AVL Tree named after two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis. The Height of an AVL tree is O(log N).

Read More – Binary Search Tree – Explanation with example

Balancing and Balance Factor

The balancing condition of AVL tree:

Balance factor = height(Left subtree) – height(Right subtree),

And it should be -1, 0 or 1. Other than this will cause restructuring (or balancing) the tree. Balancing performed is carried in the following ways,

1. Right rotation(RR)

In the binary search tree shown below is a case of right rotation. There is a single rotation required at the root 50, done as followed,

• 20 will be the new root.
• 50 takes ownership of 20’s right child,
• 10 is still the left child of 20.

2. Left rotation(LL)

In the binary search tree shown below is a case of left rotation where required. There is a single rotation required at the root 50, done as followed,

• 70 will be the new root.
• 50 takes ownership of 70’s left child.
• 80 is still the right child of 70.

3. Left right double rotation(LR)

Shown below is the case of LR rotation, here two rotations are performed. First RR and then, LL as follows,

• Right rotation is applied at 70, after restructuring, 60 takes the place of 70 and 70 as the right child of 60.
• Now left rotation is required at the root 50, 60 becomes the root. 50 and 70 become the left and right child respectively.

We could also think of the shown way to balance quickly rather than going with two rotations.

4. Right left double rotation(RL)

Shown below is the case of RL rotation, here two rotations are performed. First LL and then, RR as follows,

• Left rotation is applied at 30, after restructuring 40 takes the place of 30 and 30 as the left child of 40.
• Now right rotation is required at the root 50, 40 becomes root. 30 and 50 becomes the left and right child respectively.

We could also think of the shown way to balance quickly rather than going with two rotations.

Implementation

For implementing the AVL Tree, balance factor will be computed every time a node is inserted. For that, every node will have another attribute height h, that says the height of the node. The height of leaf node is taken as zero.

More – Play yourself with this animator to see how AVL works.

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

typedef struct node{
    int key;
    struct node *left;
    struct node *right;
    int height;
}Node;
 
/*for creating new node */ 
Node * newNode(int key){
     
    Node *temp = (Node *)malloc(sizeof(Node));
 
    temp->key = key;
    temp->left = NULL;
    temp->right = NULL;
    temp->height = 0; 
    return temp;
}

/*deciding max of i and j */
int max(int i, int j){
	return i>j?i:j;	
	}


int height(Node *p){
	return p==NULL?-1:(p->height);
	}	
 
Node *leftLeftRotn(Node *p){
	Node *q = (Node *)malloc(sizeof(Node));
	q = p->left;
	p->left = q->right;
	q->right = p;
	
	p->height = max(height(p->left), height(p->right)) + 1;
	q->height = max(height(q->left), p->height) + 1;
	
	return q;
	}
	
Node *rightRightRotn(Node *p){
	Node *q = (Node *)malloc(sizeof(Node));
	q = p->right;
	p->right = q->left;
	q->left = p;
	p->height = max(height(p->left), height(p->right)) + 1;
	q->height = max(height(q->right), p->height) + 1;
	
	return q;
	
	}
	
/*double rotation is performed as LR */	
Node *leftRightRotn(Node *p){
	p->left = rightRightRotn(p->left);
	p = leftLeftRotn(p);
	
	return p;	
	}

/*double rotation is performed as RL */	
Node *rightLeftRotn(Node *p){
	p->right = leftLeftRotn(p->right);
	p = rightRightRotn(p);
	return p;
	}			


 
Node *balance(Node *p){
	int bFactor, hL, hR;  /* hL & hR: height of left subtree and right subtree*/
	Node *pLeft, *pRight; /*pLeft & pRight: left and right subtree of root p */
	
	if(!p->left){
		hL = 0;
	} else{
		hL = p->left->height + 1;
	}
	if(!p->right){
		  hR = 0;
	} else{
		  hR = p->right->height + 1;
	}
	bFactor = hL - hR;
	
	if(bFactor  < 2 && bFactor > -2){
		return p;
		
	} else if(bFactor == 2){
		pLeft = p->left;
		
	 	if( height(pLeft->left) > height(pLeft->right) )
			return leftLeftRotn(p);
		else
			return leftRightRotn(p);
	} else {
			pRight = p->right;
		
	 	if( height(pRight->right) > height(pRight->left) )
			return rightRightRotn(p);
		else
			return rightLeftRotn(p);	
	}
}
 
/*for inserting the key, newNode is the node needed to be inserted */  
Node * insert(Node *p, Node *nwNode){
 
    if(!p){
        printf("Key %d\tinserted\n", nwNode->key);
        return nwNode;
    }
    if(nwNode->key > p->key){
 
        p->right = insert(p->right, nwNode);
        if(!(p->right))
            p->right = nwNode;
    }
    else{
        p->left = insert(p->left, nwNode);
        if(!(p->left))
            p->left = nwNode;
    }
    p->height = max(height(p->left), height(p->right)) + 1;
    
    p = balance(p); //balance checking and performing
    
    return p;
}
 
int main(void){
 
    Node *root = NULL; 
 
    printf("RL Rotation - \n");
    root = insert(root, newNode(50));
    root = insert(root, newNode(40));
    root = insert(root, newNode(45)); //RL Rotation required
    printf("after Rotation root of tree - %d\n", root->key); // after Rotation root should be 45
    
    printf("RR Rotation - \n");
    root = insert(root, newNode(30));
    root = insert(root, newNode(20)); //RR Rotation required
    printf("right of left child of root - %d\n", root->left->right->key); // right of left child of root should be 40
    
    printf("LL Rotation - \n");
    root = insert(root, newNode(60));
    root = insert(root, newNode(80)); //LL Rotation required
    printf("left of right child of root - %d\n", root->right->left->key); // left of right child of root should be 50

    printf("RL Rotation - \n");
    root = insert(root, newNode(70));
    root = insert(root, newNode(90));
    root = insert(root, newNode(65)); //RL Rotation required
    printf("right child of root  - %d\n", root->right->key); //right child of root should be 70

    return 0;
} 

Output:-
RL Rotation - 
Key 50	inserted
Key 40	inserted
Key 45	inserted
after Rotation root of tree - 45
RR Rotation - 
Key 30	inserted
Key 20	inserted
right of left child of root - 40
LL Rotation - 
Key 60	inserted
Key 80	inserted
left of right child of root - 50
RL Rotation - 
Key 70	inserted
Key 90	inserted
Key 65	inserted
right child of root  - 70

Application

AVL tree is no more in use as Red Black tree turns out as the better choice. Nevertheless, AVL Tree is best suited if the requirement is more search intensive.

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

Keep Learning… Happy Learning.. 🙂

Recommended -