# 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 -

Subscribe
Notify of Inline Feedbacks Jia Rong Yang
5 years ago

why we need to malloc while rotation (RR & LL) and without free it afterward? Vivek
5 years ago

Thanks for finding mistake.
Line no 34 and 46, q is used as temp variable, plz edit it “Node *q;” only. mvnov
2 years ago

RR，LL，LR，RL are types, not rotations.
RR means inserting a node to the right of right subtree，for this scenario, it should apply left rotation (counter clockwise direction).
LL means inserting a node to the left of left subtree, it should apply clockwise rotation. 1 year ago

Your RL and LR rotations are wrong they should be reversed Carlos
1 year ago

The following lines in ‘balance’
if(!(p->right))
p->right = nwNode;
and
if(!(p->left))
p->left = nwNode;

never execute. Carlos
1 year ago

Sorry not balance but insert

6
0