red/black trees

C# 4.0 in a Nutshell mentions a red/black tree on page 290. To that end I thought I'd look up trees at wikipedia. Of trees:

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
3. Both the left and right subtrees must also be binary search trees.

 
 

red/black trees

1. A node is either red or black.
2. The root is black. (This rule is sometimes omitted from other definitions. Since the root can always be changed from red to black, but not necessarily vice-versa, this rule has little effect on analysis.)
3. All leaves are the same color as the root.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

 
 

The red/black thing is basically a constraint on how a tree is shaped.

Note: a leaf is a node with no children