red-black treee

[Pavel <asl.pavel@xxxxxxxxx>]

Hi guys plz correct me if im wrong. But it seems __rb_erase_color (
lib/rbtree.h ) violate property of the red-black tree ( both children
of the red node should be black )

I think instead:
[code]:
if ((!other->rb_left || rb_is_black(other->rb_left)) &&
     (!other->rb_right || rb_is_black(other->rb_right)))
 {
     rb_set_red(other);
     node = parent;
     parent = rb_parent(node);
 }
[/code]

should be thmth like this:
[code]
 if ( (!sibling->rb_left || rb_is_black(sibling->rb_left)  ) &&
      (!sibling->rb_right || rb_is_black(sibling->rb_right)) )
 {
      if ( rb_is_black(parent) ) {
            // all is black
             rb_set_red(sibling);
             node = parent;
             parent = rb_parent(node);
      } else {
             // parent is red , everything else black
             rb_set_black(parent);
             rb_set_red(sibling);
             node = root->rb_node;
             break;
      }
}
[/code]

Plz show me were im wrong! Thx.

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx
Please read the FAQ at http://kernelnewbies.org/FAQ