CS 660: Red-Black[To Lecture Notes Index] San Diego State University -- This page last updated October 21, 1995 A binary search tree is a red-black tree if: 1. Every node is either red or black 2. Every leaf (nil) is black 3. If a node is red, then both its children are black 4. Every simple path from a node to a descendant leaf contains the same number of black nodes Black-height of a node x, bh(x), is the number
