AVL tree is a self balancing binary search tree and it was named after its founders, Adelson, Velski and Landiis.
For every internal node of AVL tree, the height of the children of v can differ by at most 1.
Example:
a
/ \
b c
/ \ / \
e f g h
Above tree is an example for AVL tree. The height of internal nodes c,d and a are 1, 1 and 2 correspondingly. And the difference in height of children of any internal is not exceeding 1.
Insertion:
The height of few nodes might get changed on inserting a new node into an AVL tree.
If AVL tree becomes unbalanced during the insertion operation, then we need to travel up the tree from the newly created node until we find the first node X such that its grandparent Z is unbalanced node and we need to re-balance or reorganize it using either single rotation or double rotation.
Rotation allows user to reorganize Binary Search Tree locally. And it is of two types.
1. Single rotation
2. Double rotation
Single rotations:
ST - sub-tree
ST1 - subtree 1
y x
/ \ / \
x ST3 => ST1 y
/ \ / \
ST1 ST2 ST2 ST3
y x
/ \ => / \
ST3 x y ST2
/ \ / \
ST1 ST2 ST3 ST1
Example 1(insertion in left sub-tree):
BF(balance factor) = (height of left sub-tree) - (height of right sub-tree)
(ht: 1) 10 (BF = 1)
/
5
Insert 3 to the above AVL tree.
(ht: 2) 10 (BF = 2)
/
5(BF = 1 & ht = 1)
/
3
There is an unbalance in the above AVL tree. We need to reorganize it using rotation.
5 (BF=0 & ht = 1)
/ \
3 10
Example 2(insertion in right sub-tree):
10(ht = 1 & BF = 1)
\
20
Insert 30 to the above AVL tree.
10 (ht = 2 & BF= 2)
\
20(ht = 1 & BF = 1)
\
30
There is an unbalance in the above AVL tree. We need to reorganize it using rotation.
20 (BF = 0 & ht = 1)
/ \
10 30
Double Rotation:
x x z
/ \ / \ / \
y ST4 z ST4 y x
/ \ => / \ => / \ / \
ST1 z y ST3 ST1 ST2 ST3 ST4
/ \ / \
ST2 ST3 ST1 ST2
x x z
/ \ / \ / \
ST1 y => ST1 z => x y
/ \ / \ / \ / \
z ST4 ST2 y ST1 ST2 ST3 ST4
/ \ / \
ST2 ST3 ST3 ST4
Example 3:
Insert 45 to the below AVL tree.
50 (BF= 1 & ht = 2)
/ \
(Bf=0&ht=1)40 60(BF=0 & ht=0)
/ \
30 48
50 (BF= 2 & ht = 3)
/ \
(Bf=1&ht=2)40 60(BF=0 & ht=0)
/ \
30 48 (BF=0 & ht=0)
/
45
Height balance property is violated at root node since its balance factor is 2. So, we need to double rotation for this case in order to make the above AVL tree balanced.
Single rotation between 40 and 48(left rotation).
50
/ \
48 60
/
40
/ \
30 45
Single rotation between 48 and 50(right rotation).
48
/ \
40 50
/ \ \
30 45 60
So, after double rotation the above AVL tree is height balanced.
Example 4:
50 (BF = 1 & ht = 2)
/ \
40 70 (BF = 0 & ht = 1)
/ \
60 80
Insert 55 to the above AVL tree.
50 (BF = 2 & ht = 3)
/ \
40 70 (BF = 1 & ht = 2)
/ \
60 80
/
55
So, height balance property is violated at the root node. So, we need to do double rotation in order to make the above AVL tree height balanced.
Single rotation(right) between 60 and 70.
50
/ \
40 60
/ \
55 70
\
80
Single rotation(left) between 50 and 60.
60
/ \
50 70
/ \ \
40 55 80
After double rotation, the above AVL tree is height balanced.
Deletion:
We will either delete a leaf or a node with only one child when we do deletion in a Binary search tree. Deletion in AVL tree is more similar to Binary search tree. But in addition to deletion, we need to re-balance the AVL tree if the height balance property is violated.
When we delete a node from AVL tree, we need to check the height balance from the deleted node to the root node. We need to reorganize the nodes where ever(height balance property violated) necessary.
#include <stdio.h>
#include <stdlib.h>
struct AVLTree_Node {
int data, bfactor;
struct AVLTree_Node *link[2];
};
struct AVLTree_Node *root = NULL;
struct AVLTree_Node * createNode(int data) {
struct AVLTree_Node *newnode;
newnode = (struct AVLTree_Node *)malloc(sizeof (struct AVLTree_Node));
newnode->data = data;
newnode->bfactor = 0;
newnode->link[0] = newnode->link[1] = NULL;
return newnode;
}
void insertion (int data) {
struct AVLTree_Node *bf, *parent_bf, *subtree, *temp;
struct AVLTree_Node *current, *parent, *newnode, *ptr;
int res = 0, link_dir[32], i = 0;
if (!root) {
root = createNode(data);
return;
}
bf = parent_bf = root;
/* find the location for inserting the new node*/
for (current = root; current != NULL; ptr = current, current = current->link[res]) {
if (data == current->data) {
printf("Cannot insert duplicates!!\n");
return;
}
res = (data > current->data) ? 1 : 0;
parent = current;
if (current->bfactor != 0) {
bf = current;
parent_bf = ptr;
i = 0;
}
link_dir[i++] = res;
}
/* create the new node */
newnode = createNode(data);
parent->link[res] = newnode;
res = link_dir[i = 0];
For every internal node of AVL tree, the height of the children of v can differ by at most 1.
Example:
a
/ \
b c
/ \ / \
e f g h
Above tree is an example for AVL tree. The height of internal nodes c,d and a are 1, 1 and 2 correspondingly. And the difference in height of children of any internal is not exceeding 1.
Insertion:
The height of few nodes might get changed on inserting a new node into an AVL tree.
If AVL tree becomes unbalanced during the insertion operation, then we need to travel up the tree from the newly created node until we find the first node X such that its grandparent Z is unbalanced node and we need to re-balance or reorganize it using either single rotation or double rotation.
Rotation allows user to reorganize Binary Search Tree locally. And it is of two types.
1. Single rotation
2. Double rotation
Single rotations:
ST - sub-tree
ST1 - subtree 1
y x
/ \ / \
x ST3 => ST1 y
/ \ / \
ST1 ST2 ST2 ST3
y x
/ \ => / \
ST3 x y ST2
/ \ / \
ST1 ST2 ST3 ST1
Example 1(insertion in left sub-tree):
BF(balance factor) = (height of left sub-tree) - (height of right sub-tree)
(ht: 1) 10 (BF = 1)
/
5
Insert 3 to the above AVL tree.
(ht: 2) 10 (BF = 2)
/
5(BF = 1 & ht = 1)
/
3
There is an unbalance in the above AVL tree. We need to reorganize it using rotation.
5 (BF=0 & ht = 1)
/ \
3 10
Example 2(insertion in right sub-tree):
10(ht = 1 & BF = 1)
\
20
Insert 30 to the above AVL tree.
10 (ht = 2 & BF= 2)
\
20(ht = 1 & BF = 1)
\
30
There is an unbalance in the above AVL tree. We need to reorganize it using rotation.
20 (BF = 0 & ht = 1)
/ \
10 30
Double Rotation:
x x z
/ \ / \ / \
y ST4 z ST4 y x
/ \ => / \ => / \ / \
ST1 z y ST3 ST1 ST2 ST3 ST4
/ \ / \
ST2 ST3 ST1 ST2
x x z
/ \ / \ / \
ST1 y => ST1 z => x y
/ \ / \ / \ / \
z ST4 ST2 y ST1 ST2 ST3 ST4
/ \ / \
ST2 ST3 ST3 ST4
Example 3:
Insert 45 to the below AVL tree.
50 (BF= 1 & ht = 2)
/ \
(Bf=0&ht=1)40 60(BF=0 & ht=0)
/ \
30 48
50 (BF= 2 & ht = 3)
/ \
(Bf=1&ht=2)40 60(BF=0 & ht=0)
/ \
30 48 (BF=0 & ht=0)
/
45
Height balance property is violated at root node since its balance factor is 2. So, we need to double rotation for this case in order to make the above AVL tree balanced.
Single rotation between 40 and 48(left rotation).
50
/ \
48 60
/
40
/ \
30 45
Single rotation between 48 and 50(right rotation).
48
/ \
40 50
/ \ \
30 45 60
So, after double rotation the above AVL tree is height balanced.
Example 4:
50 (BF = 1 & ht = 2)
/ \
40 70 (BF = 0 & ht = 1)
/ \
60 80
Insert 55 to the above AVL tree.
50 (BF = 2 & ht = 3)
/ \
40 70 (BF = 1 & ht = 2)
/ \
60 80
/
55
So, height balance property is violated at the root node. So, we need to do double rotation in order to make the above AVL tree height balanced.
Single rotation(right) between 60 and 70.
50
/ \
40 60
/ \
55 70
\
80
Single rotation(left) between 50 and 60.
60
/ \
50 70
/ \ \
40 55 80
After double rotation, the above AVL tree is height balanced.
Deletion:
We will either delete a leaf or a node with only one child when we do deletion in a Binary search tree. Deletion in AVL tree is more similar to Binary search tree. But in addition to deletion, we need to re-balance the AVL tree if the height balance property is violated.
When we delete a node from AVL tree, we need to check the height balance from the deleted node to the root node. We need to reorganize the nodes where ever(height balance property violated) necessary.
See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs
Example Program For Insertion, Deletion & Traversal In AVL Tree(in C):
#include <stdlib.h>
struct AVLTree_Node {
int data, bfactor;
struct AVLTree_Node *link[2];
};
struct AVLTree_Node *root = NULL;
struct AVLTree_Node * createNode(int data) {
struct AVLTree_Node *newnode;
newnode = (struct AVLTree_Node *)malloc(sizeof (struct AVLTree_Node));
newnode->data = data;
newnode->bfactor = 0;
newnode->link[0] = newnode->link[1] = NULL;
return newnode;
}
void insertion (int data) {
struct AVLTree_Node *bf, *parent_bf, *subtree, *temp;
struct AVLTree_Node *current, *parent, *newnode, *ptr;
int res = 0, link_dir[32], i = 0;
if (!root) {
root = createNode(data);
return;
}
bf = parent_bf = root;
/* find the location for inserting the new node*/
for (current = root; current != NULL; ptr = current, current = current->link[res]) {
if (data == current->data) {
printf("Cannot insert duplicates!!\n");
return;
}
res = (data > current->data) ? 1 : 0;
parent = current;
if (current->bfactor != 0) {
bf = current;
parent_bf = ptr;
i = 0;
}
link_dir[i++] = res;
}
/* create the new node */
newnode = createNode(data);
parent->link[res] = newnode;
res = link_dir[i = 0];
/* updating the height balance after insertion */
for (current = bf; current != newnode; res = link_dir[++i]) {
if (res == 0)
current->bfactor--;
else
current->bfactor++;
current = current->link[res];
}
/* right sub-tree */
if (bf->bfactor == 2) {
printf("bfactor = 2\n");
temp = bf->link[1];
if (temp->bfactor == 1) {
/*
* single rotation(SR) left
* x y
* \ / \
* y => x z
* \
* z
*/
subtree = temp;
bf->link[1] = temp->link[0];
temp->link[0] = bf;
temp->bfactor = bf->bfactor = 0;
} else {
/*
* double rotation (SR right + SR left)
* x x z
* \ \ / \
* y => z => x y
* / \ ///
* z y
*/
subtree = temp->link[0];
temp->link[0] = subtree->link[1];
subtree->link[1] = temp;
bf->link[1] = subtree->link[0];
subtree->link[0] = bf;
/* update balance factors */
if (subtree->bfactor == -1) {
bf->bfactor = 0;
temp->bfactor = 1;
} else if (subtree->bfactor == 0) {
bf->bfactor = 0;
temp->bfactor = 0;
} else if (subtree->bfactor == 1) {
bf->bfactor = -1;
temp->bfactor = 0;
}
subtree->bfactor = 0;
}
/* left sub-tree */
} else if (bf->bfactor == -2) {
temp = bf->link[0];
if (temp->bfactor == -1) {
/*
* single rotation(SR) right
* x y
* / / \
* y => z x
* /
* z
*/
subtree = temp;
bf->link[0] = temp->link[1];
temp->link[1] = bf;
temp->bfactor = bf->bfactor = 0;
} else {
/*
* double rotation - (SR left + SR right)
* x x z
* / / / \
* y => z => y x
* \ /
* z y
*/
subtree = temp->link[1];
temp->link[1] = subtree->link[0];
subtree->link[0] = temp;
bf->link[0] = subtree->link[1];
subtree->link[1] = bf;
/* update balance factors */
if (subtree->bfactor == -1) {
bf->bfactor = 1;
temp->bfactor = 0;
} else if (subtree->bfactor == 0) {
bf->bfactor = 0;
temp->bfactor = 0;
} else if (subtree->bfactor == 1) {
bf->bfactor = 0;
temp->bfactor = -1;
}
subtree->bfactor = 0;
}
} else {
return;
}
if (bf == root) {
root = subtree;
return;
}
if (bf != parent_bf->link[0]) {
parent_bf->link[1] = subtree;
} else {
parent_bf->link[0] = subtree;
}
return;
}
void deletion(int data) {
int link_dir[32], res = 0, i = 0, j = 0, index = 0;
struct AVLTree_Node *ptr[32], *current, *temp, *x, *y, *z;
current = root;
if (!root) {
printf("Tree not present\n");
return;
}
if ((root->data == data) && (root->link[0] == NULL)
&& (root->link[1] == NULL)) {
free(root);
root = NULL;
return;
}
/* search the node to delete */
while (current != NULL) {
if (current->data == data)
break;
res = data > current->data ? 1 : 0;
link_dir[i] = res;
ptr[i++] = current;
current = current->link[res];
}
if (!current) {
printf("Given data is not present!!\n");
return;
}
index = link_dir[i - 1];
temp = current->link[1];
/* delete the node from the AVL tree - similar to BST deletion */
if (current->link[1] == NULL) {
if (i == 0) {
temp = current->link[0];
free(current);
root = temp;
return;
} else {
ptr[i - 1]->link[index] = current->link[0];
}
} else if (temp->link[0] == NULL) {
temp->link[0] = current->link[0];
temp->bfactor = current->bfactor;
if (i > 0) {
ptr[i-1]->link[index] = temp;
} else {
root = temp;
}
link_dir[i] = 1;
ptr[i++] = temp;
} else {
/* delete node with two children */
j = i++;
while (1) {
link_dir[i] = 0;
ptr[i++] = temp;
x = temp->link[0];
if (x->link[0] == NULL)
break;
temp = x;
}
x->link[0] = current->link[0];
temp->link[0] = x->link[1];
x->link[1] = current->link[1];
x->bfactor = current->bfactor;
if (j > 0) {
ptr[j - 1]->link[index] = x;
} else {
root = x;
}
link_dir[j] = 1;
ptr[j] = x;
}
free(current);
for (i = i - 1; i >= 0; i = i--) {
x = ptr[i];
if (link_dir[i] == 0) {
x->bfactor++;
if (x->bfactor == 1) {
break;
} else if (x->bfactor == 2) {
y = x->link[1];
if (y->bfactor == -1) {
/* double rotation - (SR right + SR left) */
z = y->link[0];
y->link[0] = z->link[1];
z->link[1] = y;
x->link[1] = z->link[0];
z->link[0] = x;
/* update balance factors */
if (z->bfactor == -1) {
x->bfactor = 0;
y->bfactor = 1;
} else if (z->bfactor == 0) {
x->bfactor = 0;
y->bfactor = 0;
} else if (z->bfactor == 1) {
x->bfactor = -1;
y->bfactor = 0;
}
z->bfactor = 0;
if (i > 0) {
index = link_dir[i - 1];
ptr[i - 1]->link[index] = z;
} else {
root = z;
}
} else {
/* single rotation left */
x->link[1] = y->link[0];
y->link[0] = x;
if (i > 0) {
index = link_dir[i - 1];
ptr[i - 1]->link[index] = y;
} else {
root = y;
}
/* update balance factors */
if (y->bfactor == 0) {
x->bfactor = 1;
y->bfactor = -1;
break;
} else {
x->bfactor = 0;
y->bfactor = 0;
}
}
}
} else {
x->bfactor--;
if (x->bfactor == -1) {
break;
} else if (x->bfactor == -2) {
y = x->link[0];
if (y->bfactor == 1) {
/* double rotation - (SR right + SR left) */
z = y->link[1];
y->link[1] = z->link[0];
z->link[0] = y;
x->link[0] = z->link[1];
z->link[1] = x;
/* update balance factors */
if (z->bfactor == -1) {
x->bfactor = 1;
y->bfactor = 0;
} else if (z->bfactor == 0) {
x->bfactor = 0;
y->bfactor = 0;
} else if (z->bfactor == 1) {
x->bfactor = 0;
y->bfactor = -1;
}
z->bfactor = 0;
if (i > 0) {
index = link_dir[i - 1];
ptr[i - 1]->link[index] = z;
} else {
root = z;
}
} else {
/* single rotation right */
x->link[0] = y->link[1];
y->link[1] = x;
if (i <= 0) {
root = y;
} else {
index = link_dir[i - 1];
ptr[i - 1]->link[index] = y;
}
/* update balance factors */
if (y->bfactor == 0) {
x->bfactor = -1;
y->bfactor = 1;
break;
} else {
x->bfactor = 0;
y->bfactor = 0;
}
}
}
}
}
}
void searchElement(int data) {
int flag = 0, res = 0;
struct AVLTree_Node *node = root;
if (!node) {
printf("AVL tree unavailable!!\n");
return;
}
while (node != NULL) {
if (data == node->data) {
printf("%d is present in AVL Tree\n", data);
flag = 1;
break;
}
res = data > node->data ? 1 : 0;
node = node->link[res];
}
if (!flag)
printf("Search Element not found in AVL tree\n");
return;
}
void inorderTraversal(struct AVLTree_Node *myNode) {
if (myNode) {
inorderTraversal(myNode->link[0]);
printf("%d ", myNode->data);
inorderTraversal(myNode->link[1]);
}
return;
}
int main() {
int key, ch;
while (1) {
printf("1. Insertion\t2. Deletion\n");
printf("3. Searching\t4. Traversal\n");
printf("5. Exit\nEnter your choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter the key value:");
scanf("%d", &key);
insertion(key);
break;
case 2:
printf("Enter the key value to delete:");
scanf("%d", &key);
deletion(key);
break;
case 3:
printf("Enter the search key:");
scanf("%d", &key);
searchElement(key);
break;
case 4:
inorderTraversal(root);
printf("\n");
break;
case 5:
exit(0);
default:
printf("Wrong Option!!\n");
break;
}
printf("\n");
}
return 0;
}
Output(AVL Tree - insertion, deletion, traversal & search - C Program):
jp@jp-VirtualBox:$ ./a.out
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:30
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:15
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:40
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:10
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:25
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:50
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:4
10 15 25 30 40 50
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:3
Enter the search key:30
30 is present in AVL Tree
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:2
Enter the key value to delete:40
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:2
Enter the key value to delete:50
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:2
Enter the key value to delete:15
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:4
10 25 30
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:5
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:30
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:15
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:40
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:10
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:25
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter the key value:50
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:4
10 15 25 30 40 50
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:3
Enter the search key:30
30 is present in AVL Tree
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:2
Enter the key value to delete:40
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:2
Enter the key value to delete:50
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:2
Enter the key value to delete:15
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:4
10 25 30
1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:5
No comments:
Post a Comment