What are the Misunderstandings about Red-Black Tree Properties?

[Joseph1739]

I don't understand the requirements for a red-black tree.
Using this photo:
https://upload.wikimedia.org/wikipedia/commons/6/66/Red-black_tree_example.svg

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.

 

[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.

 

[Joseph1739]

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.

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

 

[Borg]

I don't understand the requirements for a red-black tree.
Using this photo:
https://upload.wikimedia.org/wikipedia/commons/6/66/Red-black_tree_example.svg

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.

What are the other rules?

 

[D H]

One of the 5 required properties is that all leaves are black.

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 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.

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).

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

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.