Manas Sinha

Developer | Designer

Manas Sinha

Developer | Designer

## By Manas | 2 October 2021 | 2 mins read

## AVL TREES

What are AVL Trees? | How to build one?

AVL trees named after three inventors Adelson-Velsky-and Landis, is a type of self balancing binary search tree. If you have no idea about these trees, read the introduction to self balancing trees article. So, as we know, a SBT is tree in which at any point the heights of the two child subtrees of any node differ by at most one. If that is the not the case the tree will rebalance itself to obey that property also keeping the Binary search tree property intact.

In a normal BST the time complexity of operations looks like this:

But in AVL trees the time complexity looks like this:

property | average case | worst case |
---|---|---|

Space | O(n) | O(n) |

Search | O(logn) | O(n) |

Insert | O(logn) | O(n) |

Delete | O(logn) | O(n) |

property | average case | worst case |
---|---|---|

Space | O(n) | O(n) |

Search | O(logn) | O(logn) |

Insert | O(logn) | O(logn) |

Delete | O(logn) | O(logn) |

Even in the worst case the AVL tree takes logN time.

## 0. REBALANCING?

While modifying the tree, i.e, inserting or deleting a value from the tree, the tree might become unbalanced. Following this, a re-balancing operation has to be done. The given repair tools are called tree rotations, because they move the keys only “vertically”, so that the “horizontal” in-order sequence of the keys is fully preserved (which is essential for a binary-search tree).

There are four possible tree-rotation operations:

- Right-Right
- Left-Left
- Right-Left
- Left-Right

## 1. SIMPLE ROTATIONS.

The rotaions right-right and left-left are simple rotations.

Left-Left rotation: While performing the left rotation, the nodes move to the left side. You might find on some websites saying the opposite that in left rotations stuff moving to the right and vice versa. Well that’s just a convention. At the end of the day you have to perform the same steps. Here, I will follow the simple notion that in left rotation stuff moves to the left. Why would I make my life more miserable than it already is..haha LOL.

- Rotating the node to the left that is unbalanced.
- Repositioning the left-subtree of that node after rotaion
- See the animation.

## c++ CODE FOR LL ROTATION

```
/* Author: The Binary Realm */
/* CPP function for left-left rotation */
TreeNode* LLRotation(TreeNode* root){
TreeNode* right_child = root->right;
root->right = right_child->left;
right_child->left = root;
return right_child;
}
```

## 2. Double ROTATIONS.

The rotaions right-left and left-right are double rotations.

Right-Left Rotation: Here we will perform two rotations. haha … surprise.

- Step 1: Find the Node that is unbalanced.
- Step 2: Perform a right rotaion on the right child of this node.
- Step 3: Perform a left rotation on the original unbalanced node.
- Step 4: Get vaccinated. What!!? it’s important.

## c++ CODE FOR RL ROTATION

```
/* Author: The Binary Realm */
/* CPP function for right-left rotation */
TreeNode* RLRotation(TreeNode* root){
root->right = RRRotation(root->right);
return LLRotation(root);
}
/*More Detailed code
if you are one of those people*/
TreeNode* RLRotation(TreeNode* root){
//Step 1: right rotaion on right child
TreeNode *right_child = root->right;
TreeNode *right_left_child = right_child->left;
right_child->left = right_left_child->right;
right_left_child->right = right_child;
root->right = right_left_child;
//Step 2: Left rotation on root node
right_child = root->right;
root->right = right_child->left;
right_child->left = root;
return right_child;
/* You can match each step performed with the animation perovided.
You will get a better understanding. */
}
```

Pingback: Balanced Trees & Introduction to Self Balancing Trees | Trees | Data Structures Simplified - TheBinaryRealm