Data Structure Questions and Answers – Red Black Tree


This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Red Black Tree”.

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

Explanation: Though both trees are balanced, AVL trees should have more rotations than red-black trees because there are more insertions and deletions to make the tree balanced. However, AVL trees should be used if further searching is needed.

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

Explanation: In terms of finding first and next elements, redblack trees have O(logn) for ordering elements. In addition, if the size of the hash table increases or decreases, rehashing is needed, which can be very costly in real time. Also, rather than storing elements in input order, red black stores them in sorted order.

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

Explanation: With the support of significant bits, the node pointers can be used to store colour. This approach has some limitations, such as not working in languages like Java that do not use pointers.

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

Explanation: When inserting and deleting frequently, use red black, AVL when inserting and deleting less frequently, and B-tree when paging from a sluggish storage unit.

5. What is the below pseudo code trying to do, where pt is a node pointer and root pointer?

  redblack(Node root, Node pt) :
    if (root == NULL)
       return pt
    if ( <
        root.left  =   redblack(root.left, pt);
        root.left.parent = root
    else if ( >
        root.right = redblackt(root.right, pt)
        root.right.parent = root
   return root

A) insert a new node
B) delete a node
C) search a node
D) count the number of nodes

Explanation: The code takes the root node and the node to be inserted and performs an insertion operation on them.

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

Explanation: A colour red or black is used as an extra attribute. Because if root were red, one of the red-black tree properties, which states that the number of black nodes from root to null nodes must be the same, would be broken.

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

Explanation: To achieve self-balancing trees with logarithmic complexities for insertions, deletions, and check, we impose certain constraints.


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

Explanation: Given all of the characteristics of the red-black tree, 50 must be the black seed, and there are two subtree options. One choice is to make all nodes of the tree black (50-black root, 18-red left subtree, 100-red right subtree), while the other is to make all nodes of the tree red (50-black root, 18-red left subtree, 100-red right subtree).

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

Explanation: We impose restrictions to achieve logarithm time complexities.
impose restrictions are:
. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black.

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

Explanation: In the Linux kernel, the RB tree is used as a fully equal scheduler process scheduling algorithm. It’s used to make insertions and retrievals go faster.

A self-balancing binary search tree is a red–black tree. Each node contains an additional bit that represents “colour” (“red” or “black”), which is used to keep the tree balanced during insertions and deletions. The new tree is rearranged and “repainted” to restore the colouring properties that limit how unbalanced the tree can become in the worst case. The properties have been created in such a way that this rearranging and recoloring can be done quickly.

Leave a Reply

Your email address will not be published. Required fields are marked *