Image for post
Image for post

An AVL Tree is a self balancing binary search tree (BST). It is named after Adelson-Velsky and Landis, the inventors of the AVL tree. The height of an AVL sub-tree can differ at most by 1. This allows us to search for an element in the AVL tree in log base 2 n time or O(log n), where n is the number of elements in the tree. As a matter of fact this allows for operations such as max, min, insertion, and deletion to all be O( log n).

When inserting values into the AVL tree, the tree may become unbalanced, we can check if it is balanced or not by using the balance factor to make sure the height of the sub-tree doesn’t differ by more than 1.

The balance factor of a node (N) in a binary tree is defined as the height difference.

BalanceFactor(N) = Height(RightSubtree(N) ) — Height(LeftSubtree(N))
or
BalanceFactor(N) = Height(LeftSubtree(N)) — Height(RightSubtree(N) )

BalanceFactor(N) belongs to the set {-1,0,1}

If the balance factor doesn’t equal -1,0, or 1 then our tree is unbalanced, and we need to perform certain operations to balance the tree. Specifically we need to do one or more of 4 tree rotations (Left Rotation, Right Rotation, Left Right Rotation, Right Left Rotation).

Image for post
Image for post
https://en.wikipedia.org/wiki/Tree_rotation#/media/File:Tree_Rebalancing.gif

There are 4 cases to balance an AVL Tree

When a node is inserted in the right subtree of the right subtree and the tree becomes unbalanced, meaning the balance factor of a node/subtree isn’t -1, 0, or 1, then we need to perform a left rotation.

Image for post
Image for post
Right Right Case
Image for post
Image for post
Balanced tree after left rotation

When a node is inserted in the left subtree of the left subtree and the tree becomes unbalanced, meaning the balance factor of a node/subtree isn’t -1, 0, or 1, then we need to perform a left rotation.

Image for post
Image for post
Left Left Case
Image for post
Image for post
Balanced tree after right rotation

A left right rotation is a combination of the left rotation followed by a right rotation. This occurs when a node is inserted into the right subtree of the left subtree, and the tree becomes unbalanced. First we need to execute the left rotation on the left subtree, note the node will still be unbalanced because of the left subtree of the left subtree. Next we need to perform the right rotation to balance the tree.

Image for post
Image for post
Left Right unbalanced tree
Image for post
Image for post
The tree after a left rotation
Image for post
Image for post
The tree after a right rotation

A right left rotation is a combination of the right rotation followed by a left rotation. This is another type of double rotation like the left right rotation. This operation needs to be performed when a node is inserted into the left subtree of the right subtree and the tree becomes unbalanced. The first thing we do is perform the right rotation followed by the left rotation to balance the tree.

Image for post
Image for post
Right Left Case
Image for post
Image for post
The tree after a Right Rotation
Image for post
Image for post
The balanced tree after a left rotation

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Recurrence Relation:

Image for post
Image for post

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store