`Eina`

provides functions for the management of *red-black trees*, a self-balancing binary search tree in which each node has an additional bit which provides the colour - red or black - and used toe ensure that the tree itself remains approximately balanced during insertions and deletions. While imperfect, red-black trees guarantee searching, insertion, and deletion operations complete within O(log *n*) time, in which *n* is the total number of elements found within the tree.

`Eina`

provides functions for creation, insertion, removal, deletion, and iteration of red-black trees and their nodes, with support for prefix, infix and postfix tree traversal.

Create a new red-black tree using the `eina_rbtree_inline_insert()`

function:

`Eina_Rbtree * eina_rbtree_inline_insert (NULL)`

The function will return the root of the new red-black tree.

Use the `eina_rbtree_inline_insert()`

function to insert a new node into an existing red-black tree:

```
Eina_Rbtree * eina_rbtree_inline_insert (
Eina_Rbtree * root,
Eina_Rbtree * node,
Eina_Rbtree_Cmp_Node_Cb cmp,
const void * data
)
```

Where `root`

is the root of a valid red-black tree, `node`

is the node to be inserted, `cmp`

is the callback to compare two nodes and `data`

is private data to help the compare function. The function will return the new root of the red-black tree.

Use the `eina_rbtree_inline_remove()`

function to remove a node from an existing red-black tree:

```
Eina_Rbtree * eina_rbtree_inline_remove (
Eina_Rbtree * root,
Eina_Rbtree * node,
Eina_Rbtree_Cmp_Node_Cb cmp,
const void * data
)
```

Where `root`

is the root of a valid red-black tree, `node`

is the node to be removed, `cmp`

is the callback to compare two nodes and `data`

is private data to help the compare function. The function will return the new root of the red-black tree.

Use the `eina_rbtree_delete()`

function to delete all nodes from an existing red-black tree:

```
Eina_Rbtree * eina_rbtree_inline_remove (
Eina_Rbtree * root,
Eina_Rbtree_Free_Cb func,
void * data
)
```

Where `root`

is the root of a valid red-black tree, `func`

is the callback that will free each node, and `data`

is private data to help the compare function.

Iterators can be associated with a red-black tree using the `eina_rbtree_iterator_prefix`

, `eina_rbtree_iterator_infix`

and `eina_rbtree_iterator_postfix`

functions, depending on whether you want to walk the tree using prefix, infix, or postfix walk methods respectively. In all cases the function is used as follows:

```
Eina_Iterator * eina_rbtree_iterator_prefix(const Eina_Rbtree * root)
[...]
Eina_Iterator * eina_rbtree_iterator_infix(const Eina_Rbtree * root)
[...]
Eina_Iterator * eina_rbtree_iterator_postfix(const Eina_Rbtree * root)
```

Where `root`

ins the root of a valid red-black tree. If `root`

is `NULL`

, a valid iterator will be provided but one which will always return `false`

to the function `eina_iterator_next()`

. If memory for the iterator cannot be allocated, the function returns `NULL`

and sets `EINA_ERROR_OUT_OF_MEMORY`

.

WARNING:If the structure of the red-black tree changes through the addition or removal of nodes the iterator will become invalid, and attempts to use the iterator may result in program crashes.

- Eina Red-Black Tree Doxygen Documentation
- A technical reference for the red-black tree API functions.