# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

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

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

to get logarithm time complexity | |

to get linear time complexity | |

to get exponential time complexity | |

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?

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 |

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?

insertion, deletion, finding predecessor, successor | |

only insertion | |

only finding predecessor, successor | |

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?

used to store strings efficiently | |

used to store integers efficiently | |

can be used in process schedulers, maps, sets | |

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.