Red black trees This data structure requires an extra one- bit color field in each node Red-black properties I. Every node is either red or black 2. The root and leaves(nil's)are black 3. If a node is red then its parent is black 4. All simple paths from any node x to a descendant leaf have the same number of black nodes= black-height(x) o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.3© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.3 Red-black trees This data structure requires an extra one￾bit color field in each node. Red-black properties: 1. Every node is either red or black. 2. The root and leaves (NIL’s) are black. 3. If a node is red, then its parent is black. 4. All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x)