| Date | Sun, 05 Aug 2012 21:27:34 -0400 | From | Rik van Riel <> | Subject | 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 making the child black, > which we can do efficiently in rb_erase(). __rb_erase_color() then > only needs to handle the no-childs case and can be modified accordingly. > > Signed-off-by: Michel Lespinasse<walken@google.com>
Acked-by: Rik van Riel <riel@redhat.com>
-- All rights reversed
|