Final answer:
Red-black trees are balanced. On any path from the root to an external node, at least half of the nodes are black. As a result, the longest path from the root to an external node is less than twice as long as the shortest path.
Step-by-step explanation:
Proving that on any path from the root to an external node in T, at least half of the nodes are black: To prove this, we can use a proof by contradiction. Let's assume that there is a path from the root to an external node in T where less than half of the nodes are black. In order for this path to be shorter than half of the nodes, it would need to have a consecutive sequence of red nodes. However, this violates the red-black tree properties, as it would result in two consecutive red nodes. Therefore, it is proven that on any path from the root to an external node in T, at least half of the nodes are black.
Using (a) to show that the longest path from the root to an external node is less than twice as long as the shortest path from the root to an external node: Let's consider the shortest path from the root to an external node, which consists only of black nodes. By (a), we know that at least half of the nodes in this path are black. Now, let's consider the longest path from the root to an external node. This path can have a maximum of double the number of nodes as the shortest path, since it can alternate between black and red nodes. However, by (a), we also know that on this longest path, at least half of the nodes are black. Therefore, the longest path from the root to an external node is less than twice as long as the shortest path from the root to an external node.