Data Structure MCQ - Avl Tree
Q1.What is the worst case possible height of AVL tree?
- 2Logn Assume base of log is 2
- 1.44log n Assume base of log is 2
- Depends upon implementation
- Theta(n)
Answer:- (B).
A
100
/
50 200
/
10 300
B
100
/
/
50 200
/ /
10 150 300
/
5
C
100
/
/
50 200
/ /
10 60 150 300
/
5 180 400
- Only A
- A and C
- A, B and C
- Only B
Answer:- (B).
Explanations :A Binary Search Tree is AVL if balance factor of every node is either -1 or 0 or 1. Balance factor of a node X is [(height of X->left) - (height of X->right)]. In Tree B, the node with value 50 has balance factor 2. That is why B is not an AVL tree.
Explanations :A Binary Search Tree is AVL if balance factor of every node is either -1 or 0 or 1. Balance factor of a node X is [(height of X->left) - (height of X->right)]. In Tree B, the node with value 50 has balance factor 2. That is why B is not an AVL tree.
- Splay Tree
- AVL Tree
- Red Black Tree
- All of the above
Answer:- (D).
- The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf
- At least one children of every black node is red
- Root may be red
- A leaf node may be red
Answer:- (A).
- p
- log(p)
- log(p)/2
- p/2
Answer:- (B).
Explanations :Consider height of tree to be ‘he’, then number of nodes which totals to p can be written in terms of height as N(he)=N(he-1)+1+N(he-2). since N(he) which is p can be written in terms of height as the beside recurrence relation which on solving gives N(he)= O(logp) as worst case height.
Explanations :Consider height of tree to be ‘he’, then number of nodes which totals to p can be written in terms of height as N(he)=N(he-1)+1+N(he-2). since N(he) which is p can be written in terms of height as the beside recurrence relation which on solving gives N(he)= O(logp) as worst case height.
- just build the tree with the given input
- find the median of the set of elements given, make it as root and construct the tree
- use trial and error
- use dynamic programming to build the tree
Answer:- (B).
Explanations :Sort the given input, find the median element among them, make it as root and construct left and right subtrees with elements lesser and greater than the median element recursively. this ensures the subtrees differ only by height 1.
Explanations :Sort the given input, find the median element among them, make it as root and construct left and right subtrees with elements lesser and greater than the median element recursively. this ensures the subtrees differ only by height 1.
- log(n) where n is the number of nodes
- n where n is the number of nodes
- 0 or 1
- atmost 1
Answer:- (A).
Explanations :At every level we can form a tree with difference in height between subtrees to be atmost 1 and so there can be log(n) such levels since height of AVL tree is log(n).
Explanations :At every level we can form a tree with difference in height between subtrees to be atmost 1 and so there can be log(n) such levels since height of AVL tree is log(n).
- Because red-black is more rigidly balanced
- AVL tree store balance factor in every node which costs space
- AVL tree fails at scale
- Red black is more efficient
Answer:- (B).
Explanations :Every node in an AVL tree need to store the balance factor (-1, 0, 1) hence space costs to O(n), n being number of nodes. but in red-black we can use the sign of number (if numbers being stored are only positive) and hence save space for storing balancing information. there are even other reasons where redblack is mostly prefered.
Explanations :Every node in an AVL tree need to store the balance factor (-1, 0, 1) hence space costs to O(n), n being number of nodes. but in red-black we can use the sign of number (if numbers being stored are only positive) and hence save space for storing balancing information. there are even other reasons where redblack is mostly prefered.
- just build the tree with the given input
- find the median of the set of elements given, make it as root and construct the tree
- use trial and error
- use dynamic programming to build the tree
Answer:- (B).
Explanations :Sort the given input, find the median element among them, make it as root and construct left and right subtrees with elements lesser and greater than the median element recursively. this ensures the subtrees differ only by height 1.
Explanations :Sort the given input, find the median element among them, make it as root and construct left and right subtrees with elements lesser and greater than the median element recursively. this ensures the subtrees differ only by height 1.
- to avoid formation of skew trees
- to save memory
- to attain faster memory access
- to simplify storing
Answer:- (A).
Explanations :In real world dealing with random values is often not possible, the probability that u are dealing with non random values(like sequential) leads to mostly skew trees, which leads to worst case. hence we make height balance by rotations.
Explanations :In real world dealing with random values is often not possible, the probability that u are dealing with non random values(like sequential) leads to mostly skew trees, which leads to worst case. hence we make height balance by rotations.
Copyright © 2022 Shineskill Software Pvt. Ltd., All rights reserved.