http://en.wikipedia.org/wiki/Red_black_tree

I am reading this, but very confusing about the graph that showed in
case 4. This picture is at the left of case 4. My question is, what is
the node 4 and 5?

It is obvious a leaf and from the definition it is black. The tree
before the node N insertion violates the rule for a red black tree:

5. Every simple path from a node to a descendant leaf contains the
same number of black nodes. (Not counting the leaf node.)

Because:
Path(G->5) = 2
Path(G->1) = 1

So the tree before the node N insertion is not a red black tree!
What's the example for?

Maybe I am wrong but please correct me, thank you!
BTW: I am reading Linux kernel source that contains ref to this
concept, so I post it to the Linux related forum.

abai

[ Post a follow-up to this message ]

"Bin Chen" <binary.chen@gmail.com> a ¨¦crit dans le message de news:
1174656577.167043.5460@p15g2000hsd.googlegroups.com...
> http://en.wikipedia.org/wiki/Red_black_tree
>
> I am reading this, but very confusing about the graph that showed in
> case 4. This picture is at the left of case 4. My question is, what is
> the node 4 and 5?
>
> It is obvious a leaf and from the definition it is black. The tree
> before the node N insertion violates the rule for a red black tree:
>
> 5. Every simple path from a node to a descendant leaf contains the
> same number of black nodes. (Not counting the leaf node.)
>
> Because:
> Path(G->5) = 2
> Path(G->1) = 1
>
> So the tree before the node N insertion is not a red black tree!
> What's the example for?
>
> Maybe I am wrong but please correct me, thank you!
> BTW: I am reading Linux kernel source that contains ref to this
> concept, so I post it to the Linux related forum.
I would tell that 4 and 5 are so called "null nodes" (left and right of U
pointing nowhere), then Path (G->U) = 1 is Ok.

Armel

[ Post a follow-up to this message ]