NIELIT 2017 July Scientist B (CS) - Section B: 7

Question

A balance factor in AVL tree is used to check

• A. what rotation to make
• B. if all child nodes are at same level
• C. when the last rotation occurred
• D. if the tree is unbalanced

Comments

@Sachin Mittal 1  Sir ,balance factor is used to check whether the avl tree is balanced or not … but in answer key in gateoverflow book of nielit pyq answer is given that it is used to see which rotation to make . could you kindly clarify which one is correct ?

Answer 1

A balancing factor in the AVL tree is used to check whether the tree is balanced or not.

Balance Factor of Node A = Height of right subtree of A - Height of left subtree of A.

The allowed balance factors are {-1,0,1}. Otherwise, the node is unbalanced.

If any node is unbalanced we cannot guarantee O(log n) search time. Therefore, AVL tree uses the concept of Balance Factor.

Hence, Option D is the correct option.

Answer 2

AVL trees are self balancing therefore have BF [-1,0,1]. The BF is checked to guess the rotation in tree. Option 3 is correct.