In a RBT, no path from a node x to a leaf is more than twice as long as any other path from x to a leaf.

Let bh(x) be the black height of x. Then the length of a longest path from x to a leaf

= 2*bh*(*x*) {a path on which red and black nodes alternate}

Length of the shortest possible path from x to a leaf

*
bh*(*x*) {a path that only contains blacks}

Hence the result.

**Result 2**

A red-black tree with n internal nodes has height at most

2log(*n* + 1)

Consider any node x and the subtree rooted at x. We will first show that this subtree has at least

2^{bh(x)} - 1 internal nodes

We do this by induction on the height of x. If h(x) = 0, bh(x)
= 0, x is leaf and hence the subtree has no internal nodes, as corroborated
by

2^{0} - 1 = 0

Let h(x) > 0 and let x1 and x2 be its two children (Figure 5.11)

Note that h(x1), h(x2) are both h(x) - 1. Assume the result to be true for x1 and x2. We shall show the result is true for x.

Now,

bh(x_{1}) |
bh(x) and bh(x)
- 1 |
||

bh(x_{2}) |
bh(x) and bh(x)
- 1 |

Therefore, the tree with root x1 has at least

2^{bh(x)
- 1} - 1
internal nodes

whereas the tree with root x2 has at least

2^{bh(x)
- 1} - 1
internal nodes

Thus the tree with root x has at least

1 + 2^{bh(x) - 1} - 1 + 2^{bh(x) - 1} - 1 = 2^{bh(x)}
- 1
internal nodes

To complete the proof, let h be the height of the tree. Then

*
bh* (root)

Thus

n/TD> |
2^{h/2} - 1 |
||

h/TD> |
2log(n + 1) |