# Red-black Trees properties

1. Oct 16, 2015

### Joseph1739

I don't understand the requirements for a red-black tree.
Using this photo:

One of the 5 required properties is that all leaves are black.
A leaf is a node without a child, so that would only be 11 and 15 two links down from the root. So why is 1 and 25 black? They clearly have a child, so they are not leaves. Similarly, why is 6, 22, and 27 not black. They don't have children so they should be black.

2. Oct 16, 2015

### Integrand

That all leaves are black does not imply that all black nodes are leaves.

6, 22, and 27 do have child nodes, which are leaves marked NIL. Whether a given red-black tree has explicit leaves does not affect their role in balancing the tree.

3. Oct 16, 2015

### Joseph1739

So if a node is not a leaf, then the color can be chosen at random?

4. Oct 16, 2015

### Borg

What are the other rules?

5. Oct 18, 2015

### D H

Staff Emeritus
That all leaf nodes are black says something quite different than all black nodes are leaves. You apparently misread that property as the latter.

A leaf node in a binary search tree contains no data and has no children. The black nodes that contain 11 and 15, along with the red nodes that contain 6, 22, and 27 are not leaf nodes. Each of those nodes contains data (11, 15, 6, 22, and 27, respectively) and each has two children (all of which are leaf nodes).

You need to look at the other properties. The root node is black, so it's color cannot be chosen at random. Both child nodes of a red node must be black, so the colors of those child nodes cannot be chosen at random. Finally, there's the balancing rule. Just because a tree obeys the basic properties of a binary search tree and first four properties of a red-black tree does not necessarily mean that it is a red-black tree.