Perfectly balanced as all things should be — AVL trees

In computer science , an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree . It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one.

Wait, What?

Many of these words that I mentioned above might be a jargon for you. You might be wondering, what do you mean by a Binary Search Tree , what is an AVL tree, etc.
Let’s have a brief discussion on the below mentioned topics :
1. What is BST(Binary Search Tree) ?
2. Drawbacks of a BST.
3. How can a BST be improved ?

Post that, we will broaden our knowledge by understanding the following:
4. What is an AVL tree?
5. Rotations in AVL tree.
6. How to create an AVL tree?

So, let’s get started.

1. What is a Binary Search Tree ?

A binary search tree is basically a binary tree , whose internal nodes each store a key (and optionally, an associated value), and each has two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search property: the key in each node is greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree . The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.

The definition of a binary search tree can vary slightly with respect to equality. Under some definitions, the tree cannot have duplicate values. In others, the duplicate values will be on the right or can be on either side.

A perfectly balanced BST

This is a perfectly balanced binary search tree (A perfect binary tree is one that is both full and complete).

We can imply that the above tree is a BST as it satisfies the BST property.
BST’s are usually used for searching elements .
The height of a BST can be:
* Max height= n
* Min height= log n
where n is the number of nodes in a BST.

Since the time complexity for searching is equal to the the height of the tree. Therefore, the time complexity for searching an element is
*O(log n) in average case and
*O(n) in the worst case scenario.

2. Drawbacks of a BST.

The height of a binary search tree is determined by the order in which the elements are inserted.
Say, we take the same set of keys but the different order of insertion as an example to clarify this scenario .
The keys are 5, 10, 20, 25, 30, 40, 50.

height of the BST = log n

Case I — When the order of insertion is 30, 40, 10, 50 ,20 ,5, 35 -> height of the BST= log n .

height of the BST = n

Case II — When the order of insertion is 50, 40, 35, 30, 20, 10, 5 ->height of the BST=n .

So the problem with a BST is that we cannot control the height to be in the logarithmic range (log n) and it becomes equal to linear (n ), which is the same as linear search.

3. How can a BST be improved ?

For the same set of values, different order of insertion determines the height of the tree. For a tree with number of elements = n , there can be number of combinations = n!(hence n! no. of trees) . Obviously, we prefer the smallest of them so that the search time can be reduced to log n order .

To make an unbalanced BST a balanced one , we introduce rotations.

Let us consider a simple example of a BST with three elements with the order of insertion as 30, 20, 10 .

unbalanced BST

In order to make this balanced, we can use the nail and thread analogy(consider a nail at the root element and a thread sliding over nail). When we pull the thread towards the right . The 20 becomes the new root , with 10 as the left subtree and 30 as the right subtree. Hence the tree becomes balanced and looks as below :

balanced bst after a rotation

This gives us an idea of the AVL trees .

4. What is an AVL tree?

Now, we are perfectly positioned to understand what we mentioned in the first line of this article.
In computer science , an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree . It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one.

AVL tree is a height balanced binary search tree. To balance the height of a BST we define a factor called as the “balance factor”.

The balance factor of a binary tree is the difference in heights of its two subtrees (hR — hL).

balance factor = height of the left subtree-height of the right subtree

The balance factor (bf) of a height balanced binary tree may take on one of the values -1, 0, +1.

Condition for balanced node of a BST:
|bf| = |hl-hr| ≤1

5. Rotations in AVL tree.

To balance itself, an AVL tree may perform the following four kinds of rotations −

i. Left-Left rotation

ii. Right-Right rotation

iii. Left-Right rotation

iv. Right-Left rotation

The first two rotations are single rotations and the next two rotations are double rotations. To have an unbalanced tree, we at least need a tree of height 2.
With this simple tree, let’s understand them one by one.

i. Left-Left rotation

Balancing a BST via LL rotation

If a tree becomes unbalanced, when a node is inserted into the left subtree of the left subtree, then we call it a LL-imbalance , so let us call this rotation also as LL-rotation .

ii. Right-Right rotation

Balancing a BST via RR rotation

If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we call it a RR-imbalance , so let us call this rotation also as RR-rotation .

iii. Left-Right rotation

A left-right rotation is a combination of left rotation followed by right rotation.

Balancing a BST via LR rotation

iv. Right-Left rotation

The second type of double rotation is Right-Left Rotation. It is a combination of right rotation followed by left rotation.

Balancing a BST via RL rotation

6. How to create an AVL tree.

Since we now have a clear understanding of the basic fundamentals, let’s go ahead and create our own AVL tree from scratch.

Say, we have to insert keys 40, 20, 10, 25, 30, 22, 50 in the order as mentioned.

Step-1: Insert 40

Step-1: Insert 40

Step-2 : Insert 20

Step-2 : Insert 20

Step 3 : Insert 10

Step 3(A): Insert 10

As soon as we insert 10, the tree becomes imbalanced due to LL-insertion, therefore perform a LL rotation about the key value 40.

Step 3(B): Balanced AVL after inserting 10

Step 4 : Insert 25

Step 4 : Insert 25

Step 5 : Insert 30

Step 5(A) : Insert 30

On inserting 30, keys 40 as well as 20 becomes imbalanced.

Whenever 2 nodes become imbalanced, we start form the node which we inserted and go upwards towards its ancestors, the first imbalanced node that we encounter has to be balanced first.

Step 5(B) : Balanced AVL after inserting 30

Step 6 : Insert 22

Step 6(A) : Insert 22

The root node becomes imbalanced, due to insertion in RLL, so do we have to perform a RLL rotation? Nope.
We always consider the 1st two of all the notations, therefore we perform RL rotation.

Step 6(B) : Balanced AVL after inserting 22

Step 7 : Insert 50

Step 7(A) : Insert 50

This imbalanced tree can be balanced by an RR rotation about the key value 30.

Step 7(B) : Balanced AVL after inserting 50

Hence, the AVL tree is perfectly balanced ✌

Resources

There are a whole host of resources out there on AVL trees, if you just know what to Google for when you search for them. Height-balanced trees are a pretty common concept in core computer science classes, so they are usually covered in CS curriculum at some point or another. If you’re looking for some further reading (that isn’t too math-heavy just yet), the links below are a good place to start.

1. AVL Trees, AVL Sort, MIT Department of Computer Science
2. Data Structures and Algorithms — AVL Trees, Tutorialspoint
3. AVL Trees, Professor Eric Alexander
4. How to determine if a binary tree is height-balanced, Geeksforgeeks
5. Balanced Binary Search Trees, Professor Karl R. Abrahamson
6. Height-Balanced Binary Search Trees, Professor Robert Holte

If you like such articles, check out my hashnode profile and my blog website.

Thanks for reading.