On Mon, 1 May 2006, Brian wrote:
> I am reading through the tree(3), and I need some clarification. If I
> want to correctly remove an element from a red black tree that I have
> found and free it's memory allocation, this code should work, right?
>
> find.i = 400;
> n = RB_FIND(inttree, &head, &find);
> if (n != NULL) {
> n = RB_REMOVE(inttree, &head, n);
> free(n);
> } else if (n == NULL)
> (void)printf("satisfied NULL check\n");
It depends entirely on how you are allocating the tree entries. You
didn't say... Either way, you don't need to worry about the return
value of RB_REMOVE, just use the value returned by RB_FIND() directly.
> I ask because the man page is clear for splay trees, but I am not
> certain for Red Black trees. I looked at /usr/include/sys/tree.h, and
> I did not find any explicit free's.
That is because it is a data structure and not an allocator. The caller
must do all its own memory management.
> I assume that since RB_REMOVE will provide me with a pointer to the
> removed element, that all I need to do is free it.
RB_FIND() gives you a pointer to the element. RB_REMOVE() just gives
you back whatever element pointer you put in, so there is no point in
looking at the return value.
> Also, is the above the most efficient way to find and remove an
> element from a red black tree?
That depends. It may be to search using RB_FIND(), but your application
may have other ways that are quicker. Who knows?
-d
