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

[Rik van Riel]

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@xxxxxxxxxx>

Acked-by: Rik van Riel <riel@xxxxxxxxxx>


--
All rights reversed
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/