AVL Tree

Understanding AVL Trees: Insertion , Deletion and Rotation Mechanisms for Balancing

Till now we have been talking about trees and its traversals in general, We have basically learnt how to balance our cycle, now its time to ride it effeciently. A tree can be effeciently traversed is its height balanced.

A tree is called a Balanced Binary tree, if each node possesses one of the following properties:

1. A node is called left heavy (or right heavy) , if the longest path in its one subtree is one longer than the longest path of its other subtree. (Basically the length is one step longer than the other)
2. A node is called balanced, if the longest path in both right and left subtrees are equal.

A tree is said to be height balanced if each node fulfills any one of these three balance factors

Here L — Left heavy, R — Right heavy, B — Balanced, U — Unbalanced

AVL TREE

In an unbalanced (or skewed) binary search tree the worst case time complexity of a search is O(n), but for balanced height binary tree gives time complexity of O(log n ) even in the worst case.

One of the most popular types of balanced tree is the AVL (Adelson — Velskii and Landis) tree.

A non empty binary tree is called an AVL tree if and only if the (mod of) difference in path lengths of a left subtree and right subtree are less than equal to one.

h(Tl) — h(Tr) is known as the balance factor (BF)

BF = (-1) when the tree is right heavy

BF = 1 when the tree is left heavy

BF = 0 when tree is balanced.

Insertion in AVL tree

There are three possible things which can happen after the insertion

1. The node which was earlier either left or right heavy, now becomes balanced. (ideal)
2. The node was balanced and now becomes left/right heavy (issok, still manage)
3. The node was heavy and the new node is inserted in the heavy sub-tree, creating an unbalanced subtree, such a node is called critical node ( screws up the entire tree)

Here the U — is the critical node/ pivot node

Case 3 leads to an unbalanced tree, hence we need to make some transformations on the tree such that

a) The inorder traversal of the transformed tree is the same as the original tree.

b) The transformed tree is balanced

TRANSFORMATION

1. Right Rotation

This bit requires certain degree of imagination and visualisation from your side… okay? Let’s start

Credits : My DSA prof 🙏

Imagine picking the A node of the tree given above, now twist it in such a way that you are pushing B node up and A down. Basically, grab the A node and rotate your wrist clockwise. The hold node ‘E’ switches places from RPTR of B to LPTR of A ( Assume it got kicked out of B’s place cause A occupied it and A feeling guilty gave it a place of its own)

Algorithm

1. Initially ‘p’ pointer is pointing to the root so p = A

2. q = LPTR[p]

3. hold = RPTR [q]

4. RPTR[q] = p

5. LPTR[p] = hold

Try doing the inorder traversal of both the trees, you will find out they are the same. ( Don’t know how to? Fret not! and click here)

Left Rotation

Similar to the above procedure, but hold A and twist it anti-clockwise. Because A is going to occupy LPTR of C, the original LPTR of C gets kicked out and occupies RPTR of A.

Algorithm

1. Initially ‘p’ is pointer pointing to the root of the tree , p = A
2. q = RPTR [p]
3. hold = LPTR [q]
4. LPTR [q] = p
5. RPTR [p] = hold

Now for when to twist which

CASE 1: LEFT — TO — LEFT INSERTION

You have inserted the node in the left subtree of the left child of the pivot node. (Damn, way to complicate an easy line🤣. Calm down and read it again, but consider the diagram of tree given above)

In this case, consider the pivot as P, and its left child as Q and do RIGHT ROTATION.

CASE 2: RIGHT — TO — RIGHT INSERTION

Unbalance occurs due to insertion in the right subtree of the right child of the pivot node

In this case consider the pivot as P, and its right child as Q and do LEFT ROTATION.

CASE 3: LEFT — TO — RIGHT INSERTION

Unbalance occurs due to (wait for it) insertion in the right subtree of the left child of the pivot node

Here, first we need to do LEFT ROTATION considering the left child as the P and then RIGHT ROTATION considering the pivot child as the P.

CASE 4: RIGHT — TO — LEFT INSERTION

Unbalance occurs due to insertion in the left sub-tree of the right child of the pivot node.

First, we need to do RIGHT ROTATION considering the right child as P then do LEFT ROTATION considering the pivot node as P.

To be honest, these rules can look like a lot, I know. Once you try out questions you will realised that all these rules boil down to just one concept, rotate the pivot node along the direction which has a lack of nodes ( opposite to the excess). Simple as that!

DELETION IN AN AVL TREE

After all the hills we have crossed and valleys we have ventured through to get to this point, you will find that deletion from an AVL tree is actually a simple concept.

It is same as that in a BST tree…

CASE 1: If there is no children of the node to be deleted, simply delete the node ( ideal case)

CASE 2: If the node has a left/ right child , the child replaces the node and the node itself gets deleted. Basically, the parent gets directly connected to the child and the node is removed (Ok, some what manageable)

CASE 3: If node has both children, then replace the node with its inorder successor, and delete the inorder successor node using CASE.1 or CASE.2 (Might take time understanding, use one of the above trees and try it out, you will understand the logic!)

After deletion use respective rotation to balance the tree in the end. Use the logic of “rotate the tree towards the less heavy side” and you will prevail!