Red black tree wiki confusing - Unix

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

+ Reply to Thread
Results 1 to 2 of 2

Thread: Red black tree wiki confusing

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


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



+ Reply to Thread