Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 10 M

Year: May 2015

• AVL is self-balancing binary tree named after Adelson-Velsky-Landis, its founders.
• In AVL tree, the difference in height of two nodes is at the most one.

• AVL trees are similar to binary search trees, except that there is an extra variable associated with every node called as the Balance_factor. The value of balance_factor is calculated as

  $$\text{Balance_factor=Height of left Sub tree- Height of Right Sub tree.}$$

• If balance_factor =1; the tree is said to be left-heavy
• If balance_factor=0; the tree is stable
• If balance_factor=-1;the tree is right-heavy
• If balance_factor >1 or balance_factor < -1; The tree is unbalanced and the node is called as critical node. We need to balance by using one of the four rotation methods