Height of a red-black tree Theorem. a red-black tree with n keys has height h≤21g(n+1) Proof. (The book uses induction. Read carefully. INTUITION. Merge red nodes into their black parents o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.9© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.9 Height of a red-black tree Theorem. A red-black tree with n keys has height h ≤ 2 lg(n + 1). Proof. (The book uses induction. Read carefully.) INTUITION: • Merge red nodes into their black parents