UGC NET CSE | August 2024 | Part 2 | Question: 4

Question

$\_\_\_\_\_\_$ is a Self Balancing binary search tree, where the path from the root to the furthest leaf is no more than twice as long as the path from the root to nearest leaf.

• A. Expression tree
• B. Game tree
• C. Red-Black tree
• D. Threaded tree

Answer 1

A Red-Black tree maintains its balance through a specific set of rules (involving coloring nodes red or black). These rules ensure that the tree remains "approximately" balanced, specifically following the property you mentioned:

• The Rule: The shortest possible path from the root to a leaf consists only of black nodes.

• The Constraint: The longest possible path can have alternating red and black nodes.

• The Result: Because no two red nodes can be adjacent, the longest path (root to furthest leaf) cannot be more than twice as long as the shortest path (root to nearest leaf). so option c