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.. 🙂