|
Home > Archive > Unix Programming > March 2007 > Red black tree wiki confusing
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Red black tree wiki confusing
|
|
| Bin Chen 2007-03-23, 1:22 pm |
| 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
| |
| Armel Asselin 2007-03-23, 1:22 pm |
|
"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
|
|
|
|
|