🌳 AVL TREE (Adelson-Velsky and
Landis Tree)
🔷 1. Definition
An AVL Tree is a self-balancing Binary Search Tree (BST) in which:
For every node, the difference between the heights of its left and right subtrees is at most 1.
This difference is called the Balance Factor.
🔷 2. Balance Factor
Balance Factor (BF)=Height of Left Subtree−Height of Right Subtree\text{Balance Factor (BF)} = \text{Height of Left Subtree} - \text{Height of
Right Subtree}Balance Factor (BF)=Height of Left Subtree−Height of Right Subtree
Allowed values:
● –1
● 0
● +1
If BF becomes –2 or +2, the tree is unbalanced and needs rotation.
🔷 3. Why AVL Trees?
Normal BST can become skewed, making operations slow.
AVL trees:
✔ Always remain balanced
✔ Guarantee O(log n) time for search, insert, delete
🔷 4. Properties of AVL Tree
1. It is a Binary Search Tree
2. Self-balancing
3. Balance factor ∈ {–1, 0, +1}
4. Height is O(log n)
5. Inorder traversal gives sorted order
🔷 5. Operations in AVL Tree
● Search
● Insertion
● Deletion
● Rotations (balancing)
🔷 6. AVL TREE ROTATIONS
Rotations are used to balance the tree.
There are 4 cases:
✅ 1. LL Rotation (Left-Left)
When?
Insertion in left subtree of left child
Solution:
👉 Single Right Rotation
Example:
Insert: 30, 20, 10
Before:
30
20
10
After rotation:
20
/ \
10 30
✅ 2. RR Rotation (Right-Right)
When?
Insertion in right subtree of right child
Solution:
👉 Single Left Rotation
Example:
Insert: 10, 20, 30
After:
20
/ \
10 30
✅ 3. LR Rotation (Left-Right)
When?
Insertion in right subtree of left child
Solution:
👉 Left rotation + Right rotation
✅ 4. RL Rotation (Right-Left)
When?
Insertion in left subtree of right child
Solution:
👉 Right rotation + Left rotation
🔷 7. AVL INSERTION ALGORITHM
Steps:
1. Insert node like BST
2. Update height
3. Calculate balance factor
4. Perform required rotation
🔷 8. Pseudocode (Insertion)
insert(node, key):
if node is NULL
return new node
if key < [Link]
[Link] = insert([Link], key)
else if key > [Link]
[Link] = insert([Link], key)
else
return node
update height
balance = BF(node)
if balance > 1 and key < [Link]
return rightRotate(node)
if balance < -1 and key > [Link]
return leftRotate(node)
if balance > 1 and key > [Link]
[Link] = leftRotate([Link])
return rightRotate(node)
if balance < -1 and key < [Link]
[Link] = rightRotate([Link])
return leftRotate(node)
return node
🔷 9. C PROGRAM FOR AVL TREE (Insertion)
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *left,*right;
int height;
};
int height(struct node *n){
return n ? n->height : 0;
int max(int a,int b){
return (a>b)?a:b;
}
struct node* newNode(int data){
struct node* node=(struct node*)malloc(sizeof(struct node));
node->data=data;
node->left=node->right=NULL;
node->height=1;
return node;
struct node* rightRotate(struct node* y){
struct node* x=y->left;
struct node* T2=x->right;
x->right=y;
y->left=T2;
y->height=max(height(y->left),height(y->right))+1;
x->height=max(height(x->left),height(x->right))+1;
return x;
struct node* leftRotate(struct node* x){
struct node* y=x->right;
struct node* T2=y->left;
y->left=x;
x->right=T2;
x->height=max(height(x->left),height(x->right))+1;
y->height=max(height(y->left),height(y->right))+1;
return y;
int getBalance(struct node* n){
return n ? height(n->left)-height(n->right) : 0;
struct node* insert(struct node* node,int key){
if(node==NULL)
return newNode(key);
if(key<node->data)
node->left=insert(node->left,key);
else if(key>node->data)
node->right=insert(node->right,key);
else
return node;
node->height=1+max(height(node->left),height(node->right));
int balance=getBalance(node);
if(balance>1 && key<node->left->data)
return rightRotate(node);
if(balance<-1 && key>node->right->data)
return leftRotate(node);
if(balance>1 && key>node->left->data){
node->left=leftRotate(node->left);
return rightRotate(node);
if(balance<-1 && key<node->right->data){
node->right=rightRotate(node->right);
return leftRotate(node);
return node;
void inorder(struct node* root){
if(root){
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
int main(){
struct node* root=NULL;
int n,x;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&x);
root=insert(root,x);
inorder(root);
}
🔷 10. Example (Insertion)
Insert: 10, 20, 30
● Insert 10 → OK
● Insert 20 → OK
● Insert 30 → BF = –2
● Apply RR Rotation
Final Tree:
20
/ \
10 30
🔷 11. Time Complexity
Operation Complexity
Search O(log n)
Insert O(log n)
Delete O(log n)
🔷 12. Features (Exam Points)
✔ Self-balancing BST
✔ Guaranteed log time
✔ Uses rotations
❌
✔ Inorder traversal sorted
More rotations than Red-Black Tree
🔷 13. AVL Tree vs BST
Feature BST AVL
Balance No Yes
Height O(n) O(log n)
Speed Slow Fast