Data Structure Questions and Answers-Red Black Tree

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

Data Structure Questions and Answers-Red Black Tree

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What is the special property of red-black trees and what root should always be?
A
a color which is either red or black and root should always be black color only
B
height of the tree
C
pointer to next node
D
a color which is either green or black
Question 1 Explanation: 
An extra attribute which is a color red or black is used. root is black because if it is red then one of red-black tree property which states that number of black nodes from root to null nodes must be same, will be violated.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Why do we impose restrictions like

. root property is black

. every leaf is black

. children of red node are black

. all leaves have same black

A
to get logarithm time complexity
B
to get linear time complexity
C
to get exponential time complexity
D
to get constant time complexity
Question 2 Explanation: 
We impose such restrictions to achieve self balancing trees with logarithmic complexities for insertions, deletions, search.

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Cosider the below formations of red-black tree.

All the above formations are incorrect for it to be a redblack tree. then what may be the correct order?

A
50-black root, 18-red left subtree, 100-red right subtree
B
50-red root, 18-red left subtree, 100-red right subtree
C
50-black root, 18-black left subtree, 100-red right subtree
D
50-black root, 18-red left subtree, 100-black right subtree
Question 3 Explanation: 
Considering all the properties of red-black tree, 50 must be the black root and there are two possibilities for subtrees. one is option a and other is making all nodes of the tree to be black.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What are the operations that could be performed in O(logn) time complexity by red-black tree?
A
insertion, deletion, finding predecessor, successor
B
only insertion
C
only finding predecessor, successor
D
for sorting
Question 4 Explanation: 
We impose restrictions (refer question 2) to achieve logarithm time complexities.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Which of the following is an application of Red-black trees and why?
A
used to store strings efficiently
B
used to store integers efficiently
C
can be used in process schedulers, maps, sets
D
for efficient sorting
Question 5 Explanation: 
RB tree is used for Linux kernel in the form of completely fair scheduler process scheduling algorithm. It is used for faster insertions, retrievals.

There are 5 questions to complete.