Data Structure Questions and Answers-Red Black Tree

Data Structure Questions and Answers-Red Black Tree

Congratulations - you have completed Data Structure Questions and Answers-Red Black Tree.

You scored %%SCORE%% out of %%TOTAL%%.

Your performance has been rated as %%RATING%%


Your answers are highlighted below.
Question 1 [CLICK ON ANY COICE TO KNOW 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 COICE TO KNOW 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 COICE TO KNOW 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 COICE TO KNOW 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 COICE TO KNOW 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.

Once you are finished, click the button below. Any items you have not completed will be marked incorrect. Get Results
There are 5 questions to complete.