Red black tree wiki confusing  Linux
This is a discussion on Red black tree wiki confusing  Linux ; 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 ...

Red black tree wiki confusing
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

Re: Red black tree wiki confusing
"Bin Chen" a ¨¦crit dans le message de news:
1174656577.167043.5460@p15g2000hsd.googlegroups.co m...
> 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