## AVL Trees

One of the more popular balanced trees, known as an AVL tree in Data Structures, was introduced in 1962 by Adelson-Velski and Landis

**Definition:**

An empty binary search tree is an AVL tree. If T is a non empty binary search tree with T_{2 }and T_{R} as its left and right sub trees, The T is an AVL tree iff.

- T
_{2 }and T_{R }are AVL trees and - | h
_{L – }h_{R }| < =1 where h_{L }and h_{R}are the heights of T_{L}and T_{ respectively}

_{ Or}

An Avl trees is a binary search tree in which for every node in the tree, The height of the left and right Sub trees differ by at most1.

h_{L} – h_{R} =1

This is AVL Tree

h_{L} – h_{R} =2

This is not AVL Tree

This is also a AVL tree

hL = Height of left sub tree =2

|hl – hR |=|2-3|=|-

1|=1

| hL –hR| <=1

The difference between heights at left sub tree and right sub tree is called balancing Factor of a node.

**Importance of Rotations**** :**

- The insert and delete operations of AVL tree are the same as binary search tree (BST)
- Since an insertion(deletion) involve adding (deleting) a tree node, this can only increase (decrease) the heights of same sub tree(s) by 1
- Thus, the AVL tree property may be violated
- If the AVL tree property is violated ata node x, it means that the height of left(x) and right(x) differ by exactly 2
- After the insertion or deletion operations, we need to examine the tree and see if any node violates the AVL tree property
- If the AVL tree property is violated at node so, single or double rotation will be applied to x to restore the AVL tree property.
- Rotation will be applied in a bottom up manner starting at the place of insertion(deletion)
- Thus when we perform a rotation at x, The AVL tree property is restored at all proper descendants of x.

This fact is important.

**Single Rotations**** :**

**RR rotation :-** [ Right – Right Rotation]

### **Double Rotations :**

**LR Rotaion c Left Right Rotation :**

_{ }**Ex : Example of RL Rotation : **

**Ex: Example of LR Rotation:**

**Example:**

Construct an AVL tree with the following elements

3,2,1,4,5,6,716,15,14

**Insertion :**

- Trace from path of inserted leaf towards the root, and check if the AVL tree property is violated perform rotation if necessary
- For insertion, once we perform (Single or doubles) rotation at a node x, The AVL tree property is already restored. We need not to perform any rotation at any ancestor of X.
- Thus one rotation is enough to restore the AVL tree properly
- There are 4 different cases (actually 2) , so don’t mix up them
- The time complexity to perform rotation is 0(1)
- The time completely to insert, and find a node that violates the AVL property is dependent on the height of the tree, which is 0(log(n))
- So insertion takes o(log(n))

**Deletion**** :**

- Delete a node X as in ordinary BST(Note that X is either a leaf or X has exactly one child)
- Check and restore the AVL tree property.
- Trace from path of deleted node towards the root and check if the AVL tree property is violated
- Similar to an insertion operation, there are four cases to restore the AVL tree property.
- The only difference from insertion is that after we perform a rotation at x, we may have to perform, a rotation at some ancestors of x, It may involve several rotations.
- Therefore, we must continue to trace the path until we reach the root.
- The time complexity to delete a node is dependent on the height of the tree, which is also o(log(n))