Data Structure Questions and Answers-Red Black Tree


 Buy/Download all MCQ Ebook   >>>Click Here<<<

Data Structure Questions and Answers-Red Black Tree

Click on any option to know the CORRECT ANSWERS

Question 1
What is the special property of red-black trees and what root should always be?
a color which is either red or black and root should always be black color only
height of the tree
pointer to next node
a color which is either green or black
Home science Questions answers

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
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

to get logarithm time complexity
to get linear time complexity
to get exponential time complexity
to get constant time complexity
GK Questions answers

Question 2 Explanation: 
We impose such restrictions to achieve self balancing trees with logarithmic complexities for insertions, deletions, search.

Question 3
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?

50-black root, 18-red left subtree, 100-red right subtree
50-red root, 18-red left subtree, 100-red right subtree
50-black root, 18-black left subtree, 100-red right subtree
50-black root, 18-red left subtree, 100-black right subtree
Current affairs Questions answers

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
What are the operations that could be performed in O(logn) time complexity by red-black tree?
insertion, deletion, finding predecessor, successor
only insertion
only finding predecessor, successor
for sorting
EVS Questions answers

Question 4 Explanation: 
We impose restrictions (refer question 2) to achieve logarithm time complexities.

Question 5
Which of the following is an application of Red-black trees and why?
used to store strings efficiently
used to store integers efficiently
can be used in process schedulers, maps, sets
for efficient sorting
Journalism Questions answers

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.


 Buy/Download all MCQ Ebook >>>CLICK HERE<<<