AVL tree

AVL tree

AVL tree is a self-propelled search tree where each node stores additional information called a balance factor with a value of -1, 0, or +1.

Balance Factor

The balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of that node's right subtree.

Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree)

The balance factor maintains the self-balancing property of an AVL tree. The value of the balance factor should always be -1, 0, or +1.

Operations on an AVL tree

Various operations that can be performed on an AVL tree are:

Rotating the subtrees in the AVL tree

In rotation operation, the subtree mode positions are rotated.

There are two types of exchange:

1. Rotate Left: The right node configuration is converted to the left node settings in the left rotation.
2. Rotate Right: In the right rotation, the arrangement of the nodes on the left is converted to the settings in the right-hand position.