# DS – AVL Trees

AVL Trees

• An AVL tree is a balanced binary search tree(BBST).
• Named after their inventors, Adelson – Velskii and Landis, they were the first dynamically balanced trees to be proposed.

BST:

• Smaller element goes left and larger elements goes right to Parent.
• BST is not a balanced Tree.
• Searching and any operation taking much time in BST.
• Height of the Tree increases when the Tree is not balance.
• In BST, we search for a node level by level

AVL Tree:

• Solution to Balanced Binary search Tree.
• An AVL tree follows Binary search tree rules only
• The sub-trees of every node differ in height by at most one.
• Every sub-tree is an AVL tree.
• abs( (height of right sub tree) – (height of left sub tree) ) ≤ 1

Rules of AVL tree: Smaller element goes left and larger elements goes right to Parent.

Balanced Tree: Height of Right sub tree – Height of left sub tree = 0

• We are not checking the number of nodes in the sub tree.
• We are checking the height of tree to balance as follows:

If the height of left sub tree or right sub tree is 0 or +1 or -1, the Tree is balanced, we cannot perform any rotations.

Imbalanced tree: When the sub tree height is either +2 or -2 is called imbalanced tree. We need to perform rotations to balance the Tree.

Scroll to Top