Data Structure Questions and Answers-Red Black Tree
Click on any option to know the CORRECT ANSWERS
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.
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.
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.
What are the operations that could be performed in O(logn) time complexity by red-black tree?
insertion, deletion, finding predecessor, successor
only finding predecessor, successor
Question 4 Explanation:
We impose restrictions (refer question 2) to achieve logarithm time complexities.
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.