AVL Trees

AVL Tree is a self balancing Binary Search tree named after Soviet inventors George Adelson Velsky and Evangi Landis.

A height balanced BST is known as Avl which can have at most 1 difference with children.Height at leaves usually start with 0 but for AVL trees we do it from 1(for the ease of understanding).Here the difference between the left and right subtrees cannot be more than one for all nodes.Operations like Lookup, insertion and deleting all take  O(log(n)) time in both the average and worst case.

Operations:

Searching: Process is similar to search in ordinary Binary search tree.

Insertion: To make sure given tree remains AVL after every insertion. 

So we must rebalance, without violating the BST rule. The Insert operation involves two rotation 

1. Left Rotation 
2. Right Rotation

Steps to follow for Insertion:

1. Perform standard BST insert
2. Starting from w, find first unbalanced node
3. Rebalance the tree in the following ways accordingly 
1. Left Left case (Right Rotation)
2. Left right case (Left and right rotation)
3. Right Right case (Left Rotate)
4. Right left case (Right and Left Rotation)

AVL Tree Rebalancing

Algorithm

1.Perform normal BST insertion 2.Current node must be one of the ancestors of the newly inserted node. Update the height of the current node. 3.Get the balance factor(left-right subtree height) of the current node 4.If balance factor is greater than 1, then the current node is unbalanced and wer are either in the 1st case or second case to check whether it is 1st compare the newly inserted key with the key in left subtree root. 5.If balance factor is less than -1, then the current node is balanced and wer are either in 3rd case or 4th case.To check if it is 3rd ,compare the newly inserted node with node in the right subtree.


Deletion: Deletion follows the same procedure as Insertion except in place of insert we delete.


Blogs to follow: 1, 2, 3