Lemma 13.1 A red-black tree with n internal nodes has height at most 21g(n+1). ●Proof:. We start by showing that the subtree rooted at any node x contains at least 2bh(x)-1 internal nodes. If x is the root,the tree contains at least 2bh(root)-1 internal nodes ·n≥2 bh(root))-1 Let h be the height of the tree.The black-height of the root must be at least h/2;thus,n22h/2-1• Proof: • We start by showing that the subtree rooted at any node x contains at least 2bh(x) -1 internal nodes. • If x is the root, the tree contains at least 2bh(root) -1 internal nodes • n≥ 2 bh(root) -1 • Let h be the height of the tree. The black-height of the root must be at least h/2; thus, n≥2 h/2 -1