Re: [PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()

On 08/02/2012 06:34 PM, Michel Lespinasse wrote: An interesting observation for rb_erase() is that when a node has exactly one child, the node must be black and the child must be red. An interesting consequence is that removing such a node can be done by simply replacing it with its child and

Re: [PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()

On 08/02/2012 06:34 PM, Michel Lespinasse wrote: An interesting observation for rb_erase() is that when a node has exactly one child, the node must be black and the child must be red. An interesting consequence is that removing such a node can be done by simply replacing it with its child and

[PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()

An interesting observation for rb_erase() is that when a node has exactly one child, the node must be black and the child must be red. An interesting consequence is that removing such a node can be done by simply replacing it with its child and making the child black, which we can do efficiently

[PATCH v2 5/9] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()

An interesting observation for rb_erase() is that when a node has exactly one child, the node must be black and the child must be red. An interesting consequence is that removing such a node can be done by simply replacing it with its child and making the child black, which we can do efficiently