Red Black Tree | Data Structure MCQs

  • 1. 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.) a color which is either green or black
   C.) pointer to next node
   D.) height of the tree

Answer: Option 'A'

a color which is either red or black and root should always be black color only

  • 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
   A.) to get logarithm time complexity
   B.) to get exponential time complexity
   C.) to get linear time complexity
   D.) to get constant time complexity

Answer: Option 'A'

to get logarithm time complexity.
We impose such restrictions to achieve self balancing trees with logarithmic complexities for insertions, deletions, search.

  • 3. What are the operations that could be performed in O(logn) time complexity by red-black tree?
   A.) only insertion
   B.) only finding predecessor, successor
   C.) for sorting
   D.) insertion, deletion, finding predecessor, successor

Answer: Option 'D'

We impose restrictions (refer question 2) to achieve logarithm time complexities.

  • 4. Which of the following is an application of Red-black trees and why?
   A.) for efficient sorting
   B.) can be used in process schedulers, maps, sets
   C.) used to store strings efficiently
   D.) used to store integers efficiently

Answer: Option 'B'

can be used in process schedulers, maps, sets
RB tree is used for Linux kernel in the form of completely fair scheduler process scheduling algorithm. It is used for faster insertions, retrievals.

  • 5. When it would be optimal to prefer Red-black trees over AVL trees?
   A.) when log(nodes) time complexity is needed
   B.) when there are more insertions or deletions
   C.) when more search is needed
   D.) when tree must be balanced

Answer: Option 'B'

when there are more insertions or deletions
Though both trees are balanced, when there are more insertions and deletions to make the tree balanced, AVL trees should have more rotations, it would be better to use red-black. but if more search is required AVL trees should be used.

  • 6. Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?
   A.) no they are not preferred
   B.) because of resizing issues of hash table and better ordering in redblack trees
   C.) because they can be implemented using trees
   D.) because they are balanced

Answer: Option 'B'

Redblack trees have O(logn) for ordering elements in terms of finding first and next elements. also whenever table size increases or decreases in hash table you need to perform rehashing which can be very expensive in real time. also red black stores elements in sorted order rather than input order.

  • 7. How can you save memory when storing color information in Red-Black tree?
   A.) storing color information in the node structure
   B.) using least significant bit of one of the pointers in the node for color information
   C.) using another array with colors of each node
   D.) using negative and positive numbering

Answer: Option 'B'

using least significant bit of one of the pointers in the node for color information
The node pointers can be used to store color with the help of significant bits. the exceptions of this method are in languages like java where pointers are not used this may not work.

  • 8. When to choose Red-Black tree, AVL tree and B-trees?
   A.) sorting, sorting and retrieval respectively
   B.) many inserts, many searches and when managing more items respectively
   C.) many searches, when managing more items respectively and many inserts respectively
   D.) retrieval, sorting and retrieval respectively

Answer: Option 'B'

many inserts, many searches and when managing more items respectively