{"id":11671,"date":"2023-01-18T06:43:28","date_gmt":"2023-01-18T06:43:28","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11671"},"modified":"2023-01-24T09:54:47","modified_gmt":"2023-01-24T09:54:47","slug":"avl-tree-in-data-structure","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/avl-tree-in-data-structure\/","title":{"rendered":"AVL Tree in Data Structure"},"content":{"rendered":"

\"\"<\/p>\n

In this article, we will learn what is AVL tree in data structure, what are different rotations in the AVL tree, the operations of the AVL tree in data structure, and the program to perform various operations on the AVL tree in data structure.<\/p>\n

What is the AVL tree in data structure?<\/h2>\n

The name AVL comes from the inventor of this algorithm GM Adelson, Velsky, and EM Landis. The AVL tree is also called a Height Balanced Binary Search Tree. It is called a height-balanced binary search because the balance factor of each node in the AVL tree is 1,0, or -1. The balance factor<\/strong> of any node is the subtraction of the height of the left sub-tree and the height of the right sub-tree. Let\u2019s see how to calculate the balance factor with an example.<\/p>\n

Balance factor of node = height of left sub-tree of – height of right subtree<\/strong><\/p>\n

\"\"<\/p>\n

In the above example, we can see that the height of the left sub-tree is 2, and the height of the right sub-tree is also 2. So, our balance factor for the root node will be 2-2 = 0.<\/p>\n

\"\"<\/p>\n

In the above example, we can see that the height of the left sub-tree is 2, and the height of the right sub-tree is also 1. So, our balance factor for the root node will be 2 – 1 = 1.<\/p>\n

\"\"<\/p>\n

In the above example, we can see that the height of the left sub-tree is 1, and the height of the right sub-tree is also 2. So, our balance factor for the root node will be 1 – 2 = -1.<\/p>\n

Now, we know what is balance factor of the node in the AVL tree is. Let\u2019s see an example of an AVL tree in data structure with a balance factor for each node.<\/p>\n

\"\"<\/p>\n

In the above example, we can say the above binary search tree is the AVL tree because the balance factor of each node is either 1 or 0, or -1. Every AVL tree is always a binary search tree but every binary search tree is not always an AVL tree.<\/p>\n

Rotations in AVL tree:<\/h2>\n

There are four types of rotation in the AVL tree:
\n1. LL Rotation:<\/strong> this rotation is performed when a newly inserted node is in the left sub-tree of the left subtree of the particular node.
\n2. RR Rotation:<\/strong> this rotation is performed when a newly inserted node is in the right sub-tree of the right subtree of the particular node.
\n3. LR Rotation:<\/strong> this rotation is performed when a newly inserted node is in the right sub-tree of the left subtree of the particular node.
\n4. RL Rotation:<\/strong> this rotation is performed when a newly inserted node is in the left sub-tree of the right subtree of the particular node.<\/p>\n

LL Rotation:<\/h3>\n

LL Rotation is performed when a newly added node violates the property of the AVL tree which means it changes the balance factor of a node out of range -1 to 1. Let\u2019s see an example to perform LL Rotation in the AVL tree.<\/p>\n

\"\"<\/p>\n

In the above example, we have inserted a new node 10 to the left of left to node 30. We can see that after inserting a new node the balance factor of node 30 becomes 2 and the tree becomes unbalanced. To make this tree balanced tree we will apply LL Rotation on the tree. We will apply the right rotation and after that, we can see the resultant tree becomes balanced.<\/p>\n

RR Rotation:<\/h3>\n

RR Rotation is performed when a newly added node violates the property of the AVL tree which means it changes the balance factor of a node out of range -1 to 1. Let\u2019s see an example to perform RR Rotation in the AVL tree.<\/p>\n

\"\"<\/p>\n

In the above example, we have inserted a new node 30 to the right of right to node 10. We can see that after inserting a new node the balance factor of node 10 becomes -2 and the tree becomes unbalanced. To make this tree balanced tree we will apply RR Rotation on the tree. We will apply the left rotation and after that, we can see the resultant tree becomes balanced.<\/p>\n

LR Rotation:<\/h3>\n

LR Rotation is performed when a newly added node violates the property of the AVL tree which means it changes the balance factor of a node out of range -1 to 1. Let\u2019s see an example to perform LR Rotation in the AVL tree.<\/p>\n

\"\"<\/p>\n

In the above example, we have inserted a new node 20 to the right of the left to node 30. We can see that after inserting a new node the balance factor of node 30 becomes -2 and the tree becomes unbalanced. To make this tree balanced tree we will apply LR Rotation on the tree. We will apply the left rotation and after that, we will apply the right rotation. Now the tree becomes unbalanced like in the first case and we have to apply LL Rotation. We can see the resultant tree becomes balanced.<\/p>\n

RL Rotation:<\/h3>\n

RL Rotation is performed when a newly added node violates the property of the AVL tree which means it changes the balance factor of a node out of range -1 to 1. Let\u2019s see an example to perform RL Rotation in the AVL tree.<\/p>\n

\"\"<\/p>\n

In the above example, we have inserted a new node 20 to the left of the right to node 30. We can see that after inserting a new node the balance factor of node 30 becomes -2 and the tree becomes unbalanced. To make this tree balanced tree we will apply RL Rotation on the tree. We will apply the right rotation and after that, we will apply the left rotation. Now the tree becomes unbalanced like in the second case and we have to apply RR Rotation. We can see the resultant tree becomes balanced.<\/p>\n

AVL tree in data structure example with dry-run<\/h2>\n

Let\u2019s take an example to understand the AVL tree in data structures.<\/p>\n

Insertion:<\/strong>
\nLet\u2019s see how an insertion operation is performed in the AVL tree.
\nElements = 17 18 19 11 10
\nWe will try to add each element one by one<\/p>\n

insert 17:<\/strong>
\n\"\"<\/p>\n

We can see that we have inserted 17 in the tree and it becomes the root of the tree. The tree is also balanced.<\/p>\n

insert 18:<\/strong>
\n\"\"<\/p>\n

After inserting 18, we can see that still, the tree is balanced thus we don\u2019t need to modify it.<\/p>\n

insert 19:<\/strong>
\n\"\"<\/p>\n

After inserting 19, we can see that the balance factor of 17 becomes -2 and the tree becomes unbalanced. Now, we will apply RR rotation to the tree and we can see that it becomes a balanced tree after applying RR rotation.<\/p>\n

insert 11:<\/strong>
\n\"\"<\/p>\n

After inserting 11, we can see that the tree is still a balanced tree. So, we do not need to modify it.<\/p>\n

insert 10:<\/strong>
\n\"\"<\/p>\n

After inserting 10, we can see that the balance factor of 17 and 18 becomes 2 and the tree becomes unbalanced. Now, we will apply LL rotation after that, the tree becomes balanced.<\/p>\n

Deletion:<\/strong>
\nLet\u2019s see how a deletion operation is performed in the AVL tree.
\n\"\"<\/p>\n

We have taken the above example to the AVL tree. Now, let\u2019s try to delete a node from the tree.
\n\"\"<\/p>\n

In the above image, we can see that we are trying to delete node 19 from the tree.
\n\"\"<\/p>\n

We can see that after the deletion of node 19, the balance factor of node 18 becomes 2 and the tree becomes unbalanced. Now, we will apply LL rotation to make the tree balanced.<\/p>\n

Program of the AVL tree in data structure:<\/h2>\n

Let\u2019s see how to write a program of the AVL tree in data structure.
\n\t\t\t\t\t\t