Questions: Red-Black Trees

Question 1

Which pair of red-black properties together directly guarantees that tree height is O(log n)?

• A. Root is black AND every null leaf is black
• B. Red nodes have only black children AND all root-to-leaf paths have equal black-node counts
• C. All nodes are colored AND no two consecutive red nodes exist on any path
• D. Root is black AND red nodes have only black children

Answer: (B)

Property 5 (equal black-height on all paths) ensures the 'shortest' root-to-null path has some black count b. Property 4 (no consecutive reds) limits the 'longest' path to alternating red-black nodes: length ≤ 2b. Since all paths have the same black-height and b ≥ log₂(n+1)/2, total height is bounded by 2 log₂(n+1) = O(log n). Without both properties together the height bound breaks down.

Question 2

A team is choosing between an AVL tree and a red-black tree for a container that undergoes frequent insertions and deletions with occasional lookups. Which is the better choice and why?

• A. AVL tree — it has strictly tighter balance and therefore shorter height for the same node count
• B. Red-black tree — it requires fewer rotations per modification, making insertions and deletions cheaper
• C. AVL tree — red-black trees degenerate under many insertions
• D. Red-black tree — it guarantees O(1) average lookup time

Answer: (B)

Red-black trees require at most 2 rotations per insertion and 3 per deletion, whereas AVL trees may rotate at every level up to O(log n) per operation to maintain their stricter balance invariant. For workloads dominated by modifications, this makes red-black trees faster in practice. AVL trees are preferred when pure lookups vastly dominate because their tighter balance keeps the tree shorter. The choice depends on the access pattern — neither is universally superior.

Question 3

A new node is always inserted as red in a red-black tree because inserting it as black would immediately violate the black-height invariant.

• T. True
• F. False

Answer: True

Property 5 requires every root-to-leaf path to have the same number of black nodes. Adding a black node on the new path increases its black count while leaving all other paths unchanged — an immediate violation. Inserting red avoids this, though it may create a consecutive-reds violation (property 4) if the parent is also red. A property-4 violation is fixable by local recoloring or at most two rotations; a property-5 violation would require rebalancing every other path in the tree.

Question 4

Red-black trees are more strictly balanced than AVL trees, so their height is typically shorter for the same number of nodes.

• T. True
• F. False

Answer: False

AVL trees are more strictly balanced: they maintain the invariant that child subtree heights differ by at most 1, keeping height close to log₂(n). Red-black trees allow a longer worst-case height (up to 2 log₂(n+1)) because paths can alternate red and black nodes. Red-black trees trade some lookup efficiency for cheaper modification operations. This is why standard library containers (std::map, Java's TreeMap) typically use red-black trees — modifications are more common than pure lookups in general-purpose use.

Question 5

Why does fixing a red-black violation after insertion require at most two rotations, regardless of tree size?

Model answer: The fix works bottom-up: if the inserted red node's uncle is also red, the violation is resolved by recoloring alone (uncle and parent turn black; grandparent turns red) and the problem may propagate upward. If the uncle is black, the violation is fully resolved in one or two rotations plus recoloring at the current level without further propagation. The rotation cases always terminate immediately, so rotations total at most two per insertion regardless of how much recoloring propagates.

This bounded rotation count is the key practical advantage over AVL trees, which may require a rotation at each level on the way back up. Red-black trees' more relaxed invariant (black-height equality rather than height-difference ≤ 1) means most violations resolve with local recoloring that can propagate upward, requiring rotations only at the boundary cases, and never more than twice per insertion.