Red-black tree properties in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the color property of Red-Black Trees

Which of the following statements correctly describes the color property of nodes in a red-black tree?

A Every node is either red or black, and the root must always be black.

B Nodes can be any color, but leaves are always black.

C Every node is either red or black, and the root must always be red.

D Only leaf nodes are colored, and internal nodes are colorless.

💡 Hint

Recall the rule about the root node's color in red-black trees.

In red-black trees, every node is colored either red or black. The root node is always black to maintain balance properties.

📋 Factual

intermediate

Black-height property of Red-Black Trees

What does the black-height property of a red-black tree ensure?

A The number of black nodes is always greater than the number of red nodes in the tree.

B All paths from a node to its descendant leaves contain the same number of red nodes.

C All paths from the root to any leaf contain the same number of black nodes.

D All paths from a node to its descendant leaves contain the same number of black nodes.

💡 Hint

Think about the balance condition related to black nodes on paths from any node.

The black-height property states that every path from a given node to its descendant leaves must have the same number of black nodes, ensuring balanced black node distribution.

🔍 Analysis

advanced

Identifying violations in Red-Black Tree properties

Given a red-black tree where a red node has a red child, which property is violated?

A The root must be black.

B All paths from a node to its leaves must have the same number of black nodes.

C Every red node must have black children.

D Leaves are always black.

💡 Hint

Recall the rule about red nodes and their children.

One key property is that red nodes cannot have red children. This prevents two reds in a row, maintaining balance.

❓ Comparison

advanced

Comparing Red-Black Tree and AVL Tree balancing

Which statement best describes the difference in balancing between red-black trees and AVL trees?

A AVL trees enforce stricter balancing than red-black trees, resulting in faster lookups but potentially slower insertions and deletions.

B Red-black trees enforce stricter balancing than AVL trees, resulting in faster insertions but slower lookups.

C Both trees enforce the same balancing rules but differ in node coloring.

D AVL trees allow red nodes, while red-black trees do not.

💡 Hint

Consider how strict each tree type is about height differences.

AVL trees maintain a stricter balance condition, which keeps the tree more balanced and improves lookup speed but can slow down insertions and deletions due to more rotations.

❓ Reasoning

expert

Calculating maximum height of a Red-Black Tree

What is the maximum height h of a red-black tree with n internal nodes?

Choose the correct formula relating h and n.

A h ≤ log₂(n + 1) / 2

B h ≤ 2 × log₂(n + 1)

C h ≤ log₂(n)

D h ≤ 3 × log₂(n + 1)

💡 Hint

Recall the property that the longest path is at most twice the shortest path in a red-black tree.

The maximum height of a red-black tree with n nodes is at most twice the logarithm base 2 of (n + 1). This is because red-black trees guarantee that no path is more than twice as long as any other.