AVL Trees | Self-Balancing Trees | Everything You need To know
logo
Manas Sinha
Developer | Designer
logo
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:
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)
But in AVL trees the time complexity looks like this:
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
The type of rotation one will perform will depend on the heavieness of the unbalanced node. Heaviness can be of two type: left-heavy and right-heavy. If the balance factor at a node is positive the subtree is left-heavy and if it is negative, it is right-heavy. The following image will make everything clear as day.

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.
So, coming to left-rotation, one thing to keep in mind that the inorder arragement of the nodes don’t change while we are doing the rotation. This makes sure that the binary search tree property remains intact. LL rotation is done in two steps:
  • 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;
}

Similar to this, right-right rotation is done. I’ll leave the coding part of this to you. See the animation to get the intuition for RR rotation while keeping in mind the criteria for RR rotation.

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. */
}
Similar to this, left-right rotation is done. I’ll leave the coding part of this to you. See the animation to get the intuition for LR rotation while keeping in mind the criteria for LR rotation.
So this marks the end of AVL Trees. There are many self balancing trees out there. One of the most important one are Red Black Trees We will learn about them in some other article.

LEAVE A COMMENT

If you like the post leave a comment and share it.

This Post Has One Comment

Leave a Reply