AVL Tree - MySirG.Com

1.
The balance factor for an AVL tree is either

(a) 0,1 or –1
(b) –2,–1 or 0
(c) 0,1 or 2
(d) All the above

Answer

(a) Binary tree is said to be balanced, if the difference between the heights of left and right sub trees of every node in the tree is either -1, 0 or +1.

2.
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

(a) 2
(b) 3
(c) 4
(d) 5

Answer

(b) AVL trees are binary trees with the following restrictions.
1) the height difference of the children is at most 1.
2) both children are AVL trees

3.
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

(a) 2
(b) 3
(c) 4
(d) 5

Answer

(b) AVL trees are binary trees with the following restrictions.
1) the height difference of the children is at most 1.
2) both children are AVL trees

4.
Re-balancing of AVL tree costs

(a) Ο(1)
(b) Ο(log n)
(c) Ο(n)
(d) Ο(n2)
Answer

(b) AVL rotations have complexity of Ο(log n)

5.
In ______________ tree, the heights of two child subtree of any node differ by at most one
(a) Binary tree
(b) Red black tree
(c) Splay tree
(d) AVL tree
Answer

(d) In AVL tree the heights of the two child subtrees of any node differ by at most one

6.
AVL Trees have a faster
(a) insertion
(b) deletion
(c) updation
(d) retrival
Answer

(d) 88 Retrieval of element is fast in AVL tree. The number of steps required to find an item depends on the distance between the item and the root node. An AVL tree is balanced binary search tree in which the difference between the height of any node’s left and right subtree is at most one. That’s why searching is faster in AVL tree.

7.
How is an insertion of a node into an AVL tree carried out?
(a) By treating an AVL tree as a binary search tree
(b) By updating the balance factors working upward from insertion point to the root
(c) Both a & b
(d) None of the Above
Answer

(c) Insertion of a node into an AVL tree is similar to binary search tree. For inserting new node, first we have to search the position and then insert the node at its proper position. After insertion, the balance might be change. We already know that balance factor in AVL tree are -1, 0, 1. So the balance factor of any node become other than these value, then we have to restore the property of AVL tree to achieve permissible balance factor.

8.
What would happen if the balance factor of a node in an AVL tree is ‘ 1 ‘
(a) Heights of left and right sub trees become equal
(b) Height of left sub tree is one more than the height of right sub tree
(c) Height of left sub tree is one less than the height of right tree
(d) None of the Above
Answer

(b) If the balance factor of a node in an AVL tree is ‘ 1 ‘ then Height of left subtree is one more than the height of right subtree.

9.
The number of possible binary trees with 5 nodes is.
(a) 40
(b) 41
(c) 42
(d) 32
Answer

10.
Which of the following techniques represents the precise sequence of an In – Order Traversal of a Binary Tree?
(a) Visit the Root, Traverse Left Subtree, Traverse Right Subtree
(b) Traverse Left Subtree; Visit the Root, Traverse Right Subtree
(c) Traverse Left Subtree, Traverse Right Subtree, Visit the Root
(d) None of the Above
Answer

(b)Traversing a binary tree means visiting each node of a tree exactly once. Traversal of tree gives the linear order of nodes. There are three types of traversal in binary tree. Preorder, Inorder and Postorder traversal.

AVL Tree