# Data Structure Questions and Answers-Red Black Tree

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