AVL Tree

• AVL Trees are Self-Balanced Binary Search Trees.

• In AVL trees, the balancing factor of each node is either 0 or 1 or -1.

• Balance Factor of AVL Tree calculated as = Height of Left Sub-tree - Height of Right Sub-tree

Construction of AVL Trees -

• Insertion Operation is performed to construct the AVL Tree.

• Inserting the element in the AVL tree is same as the insertion performed in BST.

• After insertion, check the balance factor of each node of the resulting tree.

  • After the insertion, the balance factor of each node is either 0 or 1 or -1, then the tree is considered to be balanced, concludes the operation, and inserts the next element if any.

  • After the insertion, the balance factor of at least one node is not 0 or 1 or -1, then the tree is considered to be imbalanced, perform the suitable rotation to balance the tree, and after the tree is balanced, insert the next element if any.

Rotations used to Balance the AVL Tree -

• After inserting an element in the AVL tree,

• If a tree becomes imbalanced, then there exists one particular node in the tree by balancing which the entire tree becomes balanced automatically.

• To rebalance the tree, balance that particular node.

To find that particular node:

• Traverse the path from the newly inserted node to the root node.
• Check the balance factor of each node that is encountered while traversing the path.
• The first encountered imbalanced node will be the node that needs to be balanced.

To balance that node:

• Count three nodes in the direction of the leaf node.

• Then, use the concept of AVL Tree Rotations to rebalance the tree.

  • LL Rotation - In LL rotation, every node moves one position to left from the current position.

  • RR Rotation - In RR rotation, every node moves one position to right from the current position.

  • LR Rotation - In LR rotation, at first, every node moves one position to the left and then one position to right from the current position.

  • RL Rotation - In RL rotation, at first every node moves one position to right and then one position to left from the current position.

Step-by-Step Construction of the AVL Tree for the given Sequence 21, 26, 30, 9, 4, 14, 28, 18,15,10, 2, 3, 7