# What Is AVL in Data Structure?

//

Heather Bennett

What Is AVL in Data Structure?

An AVL tree is a self-balancing binary search tree, where the difference in heights of the left and right subtrees of any node is at most one. The name “AVL” is derived from the initials of the inventors, Adelson-Velsky and Landis.

## Why Use AVL Trees?

AVL trees are essential in scenarios where efficient searching, insertion, and deletion operations are required. Unlike regular binary search trees, which can become unbalanced and lead to inefficient operations, AVL trees maintain their balance throughout.

### The Balancing Act

In an AVL tree, each node stores a balance factor that represents the height difference between its left and right subtrees. This balance factor can be either -1, 0, or 1. When inserting or deleting nodes from an AVL tree, the balance factors are adjusted to ensure that no node violates the height property.

If a new node is inserted into an AVL tree and causes an imbalance (balance factor of a node becomes greater than 1 or less than -1), rotations are performed to restore balance. Rotations involve reorganizing the structure of the tree while maintaining the order of elements.

Rotations:

• Left Rotation: In this operation, a right-heavy subtree is rotated to become left-heavy.
• Right Rotation: Here, a left-heavy subtree is rotated to become right-heavy.
• Left-Right Rotation: This rotation combines a left rotation followed by a right rotation to balance a subtree.
• Right-Left Rotation: Similarly, this rotation combines a right rotation followed by a left rotation.