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.
