**AVL Tree-**

- AVL trees are special kind of binary search trees.
- In AVL trees, height of left subtree and right subtree of every node differs by at most one.
- AVL trees are also called as
**self-balancing binary search trees**.

**Also Read-** **Binary Search Trees**

**Example-**

Following tree is an example of AVL tree-

This tree is an AVL tree because-

- It is a binary search tree.
- The difference between height of left subtree and right subtree of every node is at most one.

Following tree is not an example of AVL Tree-

This tree is not an AVL tree because-

- The difference between height of left subtree and right subtree of root node = 4 – 2 = 2.
- This difference is greater than one.

**Balance Factor-**

In AVL tree,

- Balance factor is defined for every node.
- Balance factor of a node = Height of its left subtree – Height of its right subtree

In AVL tree, Balance factor of every node is either 0 or 1 or -1. |

**AVL Tree Operations-**

Like **BST Operations**, commonly performed operations on AVL tree are-

- Search Operation
- Insertion Operation
- Deletion Operation

**Also Read-** **Insertion in AVL Tree**

After performing any operation on AVL tree, the balance factor of each node is checked.

There are following two cases possible-

**Case-01:**

- After the operation, the balance factor of each node is either 0 or 1 or -1.
- In this case, the AVL tree is considered to be balanced.
- The operation is concluded.

**Case-02:**

- After the operation, the balance factor of at least one node is not 0 or 1 or -1.
- In this case, the AVL tree is considered to be imbalanced.
- Rotations are then performed to balance the tree.

**AVL Tree Rotations-**

Rotation is the process of moving the nodes to make tree balanced. |

**Kinds of Rotations-**

There are 4 kinds of rotations possible in AVL Trees-

- Left Rotation (LL Rotation)
- Right Rotation (RR Rotation)
- Left-Right Rotation (LR Rotation)
- Right-Left Rotation (RL Rotation)

**Cases Of Imbalance And Their Balancing Using Rotation Operations-**

**Case-01:**

**Case-02:**

**Case-03:**

**Case-04:**

To gain better understanding about AVL Trees and Rotations,

**Download Handwritten Notes Here-**

**Next Article-** **AVL Tree Properties**

Get more notes and other study material of **Data Structures**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.