A

binary tree that satisfies these properties:

1. Every

node is either red or black.

2. Every

leaf 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

trees.

By preserving these properties you create an approximately

balanced tree that can be searched at

O( lg n).