**AVL**(Adelson-Velskii and Landis scientists who found this tree) trees are balanced Binary search trees. All the operations like addition, deletion and searching in the worst case of O(log(n)).

**What are AVL Trees:**AVL trees are balanced binary search trees. A tree said to be balanced if the height of the left sub tree and right sub tree difference should be at most one at each node. i.e left sub tree and right sub tree difference should either 0, 1, -1.

**Why AVL Trees**: The problem with

**Binary Search Tree**(BST) is that, if the given input values are in any sorted order(ascending or descending) the BST will be completely left or right as shown below. So Search will take worst case of O(n) where n is the no. of nodes in the BST.

Left skewed BST |

Right skewed BST |

From the above images it is very clear that , BST is not advisable to construct for sorted input values.

**How to construct AVL Tree:**Construction of AVL tree is same as Binary search tree, but the difference is after inserting the new node into the tree or deleting a node from the tree, again need to check each node for the balance. if the tree is not balanced, we need to re-structure or rebuild the tree for balancing using

**rotation**.

**Algorithm for AVL Tree:**

**Step1:**Get the

*element*to insert into the tree.

**Step2:**if the tree is empty, make the node as

*root*node.

**Step3:**If the tree is not empty, traverse the tree until it reaches NULL in such a way that

if(

*element*>

*node->element*)

move

*node*to

*node->right*

else if(

*element*<

*node->element*)

move

*node*to

*node->left*

**Step4:**After inserting check for the height of the node in Tree

**Step5:**If any node is not balanced, find the

**rotation**type.

**Step6:**After doing the rotation, adjust the new heights of the rotated nodes

**Example of the AVL Tree:**Below is the AVL tree which satisfies Binary search tree property at each node and the difference between left sub tree height and right sub tree height is at most 1.

AVL Tree |

## No comments:

Post a Comment