AVL Tree [Theory]

AVL TREE

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. For example :

  

(Left : Correct AVL Tree || Right : Wrong AVL Tree)

The reason why right AVL tree is wrong because the above tree is not AVL because differences between heights of left and right subtrees for 8 and 18 is greater than 1.

AVL trees have an additional guarantee:

The difference between the depth of right and left subtrees cannot be more than one. In order to maintain this guarantee, an implementation of an AVL will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee. AVL trees have a worst case lookup, insert and delete time of O(log n).

In AVL Tree, we can perform Insertion and Deletion.

·       Insertion

To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing. Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).

AVL Insertion Process

You will do an insertion similar to a normal Binary Search Tree insertion. After inserting, you fix the AVL property using left or right rotations.

·       If there is an imbalance in left child of right subtree, then you perform a left-right rotation.

·       If there is an imbalance in left child of left subtree, then you perform a right rotation.

·       If there is an imbalance in right child of right subtree, then you perform a left rotation.

·       If there is an imbalance in right child of left subtree, then you perform a right-left rotation.

·       Deletion

To make sure that the given tree remains AVL after every deletion, we must augment the standard BST delete operation to perform some re-balancing. Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).

·       Balance

In AVL tree, after performing every operation like insertion and deletion we need to check the balance factor of every node in the tree. If every node satisfies the balance factor condition then we conclude the operation otherwise we must make it balanced. We use rotation operations to make the tree balanced whenever the tree is becoming imbalanced due to any operation.

Rotation operations are used to make a tree balanced.There are four rotations and they are classified into two types:

Single Left Rotation (LL Rotation)

In LL Rotation every node moves one position to left from the current position.

Single Right Rotation (RR Rotation)

In RR Rotation every node moves one position to right from the current position.

Left Right Rotation (LR Rotation)

The LR Rotation is combination of single left rotation followed by single right rotation. In LR Rotation, first every node moves one position to left then one position to right from the current position.

Right Left Rotation (RL Rotation)

The RL Rotation is combination of single right rotation followed by single left rotation. In RL Rotation, first every node moves one position to right then one position to left from the current position.

References :

https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

https://www.geeksforgeeks.org/avl-tree-set-2-deletion/?ref=lbp

https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/