This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “AVL Tree”.
1. Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?
A) just build the tree with the given input
B) find the median of the set of elements given, make it as root and construct the tree
C) use trial and error
D) use dynamic programming to build the tree
Explanation: Sort the input, find the median element among it, set it as the base, and recursively build left and right subtrees with elements less and greater than the median element. This means that the subtrees only vary in height by one.
2. What maximum difference in heights between the leafs of a AVL tree is possible?
A) log(n) where n is the number of nodes
B) n where n is the number of nodes
C) 0 or 1
D) atmost 1
Explanation: Since the height of an AVL tree is log(n), we may form a tree at each level with a height difference between subtrees of at most 1, and hence there can be log(n) such levels (n).
3. Consider the pseudo code:
int avl(binarysearchtree root): if(not root) return 0 left_tree_height = avl(left_of_root) if(left_tree_height== -1) return left_tree_height right_tree_height= avl(right_of_root) if(right_tree_height==-1) return right_tree_height
Does the above code can check if a binary search tree is an AVL tree?
Explanation: There is no condition to verify the height difference between the left and right subtrees. if (absolute(left_tree_height – right_tree_height)>1) must be added.
4. Consider the below left-left rotation pseudo code where the node contains value pointers to left, right child nodes and a height value and Height() function returns height value stored at a particular node.
avltree leftrotation(avltreenode z): avltreenode w =x-left x-left=w-right w-right=x x-height=max(Height(x-left),Height(x-right))+1 w-height=max(missing)+1 return w
What is missing?
A) Height(w-left), x-height
B) Height(w-right), x-height
C) Height(w-left), x
Explanation: We’re trying to make a left rotation in the code, so we need to find the limit of those two values.
5. Why to prefer red-black trees over AVL trees?
A) Because red-black is more rigidly balanced
B) AVL tree store balance factor in every node which costs space
C) AVL tree fails at scale
D) Red black is more efficient
Explanation: Every node in an AVL tree must store the balance factor (-1, 0, 1), resulting in a space cost of O(n), where n is the number of nodes. However, in red-black, we can use the sign of the number (if the numbers being stored are all positive) to save space for balancing data. There are a variety of other reasons why redblack is preferred.
6. What is the maximum height of an AVL tree with p nodes?
Explanation: If the tree’s height is he, the number of nodes that add up to p can be written as N(he)=N(he-1)+1+N(he-1)+1+N(he-1)+1+N(he-1)+1+N(he-1)+1+N(he-1)+1+N(he-1)+1+N(he-1)+1+N(he-1) (he-2). Since N(he), which is p, can be written in terms of height as the beside recurrence relation, which when solved yields N(he)= O(logp) as the worst case height, N(he)= O(logp)
7. To restore the AVL property after inserting a element, we start at the insertion point and move towards root of that tree. is this statement true?
Explanation: It’s worth noting that after insertion, only the path from that point to the node, or only the subtrees, are height-balanced.
8. What is an AVL tree?
A) a tree which is balanced and is a height balanced tree
B) a tree which is unbalanced and is a height balanced tree
C) a tree with three children
D) a tree with atmost 3 children
Explanation: It’s a self-balancing tree with a maximum height difference of one metre.
9. Why we need to a binary tree which is height balanced?
A) to avoid formation of skew trees
B) to save memory
C) to attain faster memory access
D) to simplify storing
Explanation: Dealing with random values is always impossible in the real world, and the likelihood that you are dealing with non-random values (such as sequential) leads to skew trees, which is the worst case scenario. As a result, we use rotations to achieve height balance.
10. Which of the below diagram is following AVL tree property?
A) only i
B) only i and ii
C) only ii
D) i is not a binary search tree
Explanation: The AVL tree has the property of being a height balanced tree with a maximum difference of one between the left and right subtrees. Binary search trees are used in all AVL trees.
The AVL tree (for Adelson-Velsky and Landis, the inventors) is a self-balancing binary search tree. It was the first time such a data structure was devised. It is not important to know the absolute height to keep balance factors up to date; it is sufficient to know the previous balance factors and the shift in height. Two bits per node are adequate for storing AVL balance information in the conventional manner.