Introduction

This implementation of a red black tree suports any kind of object in it. It is a simple implementation and should compile on all systems.

Although this implementation is generic it requires that the objects stored in it be "malloched" before insertion. The reason for such thing lies in the implementation of destroy_rbtree, which frees the stored nodes.

Compilation

Compilation can be done easily with gcc. One example might be gcc -c rbtree.c

If debug info is required you can recompile with -DDEBUG. Note that some times your program may stop or fail due to this rbtree implementation, if so recompile it with -DDEBUG to get the appropriate error messages.

Using it

The user must provide two aditional functions.

The first one should have the following signature:

void* function_name(struct stree_node* node);

This function should return the key used in the red black tree. For example, if one is creating a red black tree of integers and the value stored in the tree is the address of each integer, this function should return node->node.

The second function should have the following signature:

uint64_t function_name(void* keyA, void* keyB);

This function should compare the two keys and return:

• 0 if the keys are the same.
• A number less than 0 if the keys are in the right order.
• A number bigger than 0 if the keys are not in the right order.

Note that these functions should be passed to the new_rbtree function. However, if a simple address comparison fits your needs then you should call new_simple_rbtree(), which automatically will create the comparison and key functions for you.

Function description

tree_root* new_simple_rbtree()

This function creates and returns a rbtree with pointer comparison.
The pointers being compared are the addresses of the stored objects.

tree_root* new_rbtree(void* (key_function_pointer)(struct stree_node node), int64_t (compare_function_pointer)(void keyA, void* keyB))

This function creates and returns a rbtree with key and compare functions defined by the user.
The first function will be used to return a key and the second function will be used to compare keys.

void* rb_tree_insert(tree_root* root, void* node)

This function inserts a node in the given rbtree.
If exists a node with the same key in the tree as the node being stored, then a pointer to the older node is returned.
This is done so the user can deallocate the memory. Otherwise NULL will be returned.

void* rb_tree_delete(tree_root* root, void* key)

This function removes from the tree the node with the given key.
The returned value is a pointer to that node.

void* search_rbtree(tree_root root, void* key)

Duh... search the tree and return the pointer to the founded value. If no node is found then NULL is returned.

void destroy_rbtree(tree_root* root)

This function deletes the tree AND the stored values.

tree_iterator* new_tree_iterator(tree_root* root)

Allocate a new iterator to the values stored in the tree.

uint8_t tree_iterator_has_next(tree_iterator* it)

Check if there are values still to be iterated.

void* tree_iterator_next(tree_iterator* it)

Return the next value in the iteration. There is no guarantee about the order of the returned values.

void destroy_iterator(tree_iterator* it)

Destroy the given iterator.