What is a red-black tree?
a) A self-balancing binary search tree where each node has an extra color attribute
b) A binary heap with two colors
c) A balanced AVL tree with different color properties
d) A linked list where each node has a color
Answer:
a) A self-balancing binary search tree where each node has an extra color attribute
Explanation:
A red-black tree is a self-balancing binary search tree in which each node has an extra color attribute, either red or black. The tree is balanced by maintaining specific properties, such as the rule that no two red nodes can be adjacent and that every path from the root to a leaf must have the same number of black nodes.
Red-black trees provide logarithmic time complexity for search, insertion, and deletion operations, making them efficient for use in databases and memory management systems.
The balancing of a red-black tree is less strict than that of an AVL tree, making red-black trees slightly faster in practice for insertion and deletion operations.
Reference:
DSA (Data Structures and Algorithms) MCQ Questions and Answers