c_rbtree.h File Reference

---

Detailed Description

Interface of the cynapses libc red-black tree implementation.

A red-black tree is a type of self-balancing binary search tree. It is complex, but has good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is the number of elements in the tree.

In red-black trees, the leaf nodes are not relevant and do not contain data. Therefore we use a sentinal node to save memory. All references from internal nodes to leaf nodes instead point to the sentinel node.

In a red-black tree each node has a color attribute, the value of which is either red or black. In addition to the ordinary requirements imposed on binary search trees, the following additional requirements of any valid red-black tree apply:

1. A node is either red or black. 2. The root is black. 3. All leaves are black, even when the parent is black (The leaves are the null children.) 4. Both children of every red node are black. 5. Every simple path from a node to a descendant leaf contains the same number of black nodes, either counting or not counting the null black nodes. (Counting or not counting the null black nodes does not affect the structure as long as the choice is used consistently.).

These constraints enforce a critical property of red-black trees: that the longest path from the root to a leaf is no more than twice as long as the shortest path from the root to a leaf in that tree. The result is that the tree is roughly balanced. Since operations such as inserting, deleting, and finding values requires worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red-black trees to be efficient in the worst-case, unlike ordinary binary search trees.

http://en.wikipedia.org/wiki/Red-black_tree

Definition in file c_rbtree.h.

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	c_rbnode_s
	Structure that represents a node of a red-black tree. More...
struct	c_rbtree_s
	Structure that represents a red-black tree. More...
Defines
#define	c_rbtree_destroy(T, DESTRUCTOR)
#define	c_rbtree_node_data(N)   ((N) ? ((N)->data) : NULL)
#define	c_rbtree_size(T)   (T) == NULL ? 0 : ((T)->size)
Typedefs
typedef struct c_rbnode_s	c_rbnode_t
typedef int	c_rbtree_compare_func (const void *key, const void *data)
typedef struct c_rbtree_s	c_rbtree_t
typedef int	c_rbtree_visit_func (void *obj, void *data)
typedef enum xrbcolor_e	xrbcolor_t
Enumerations
enum	xrbcolor_e { BLACK = 0, RED }
Functions
int	c_rbtree_check_sanity (c_rbtree_t *tree)
int	c_rbtree_create (c_rbtree_t **rbtree, c_rbtree_compare_func *key_compare, c_rbtree_compare_func *data_compare)
c_rbtree_t *	c_rbtree_dup (const c_rbtree_t *tree)
c_rbnode_t *	c_rbtree_find (c_rbtree_t *tree, const void *key)
int	c_rbtree_free (c_rbtree_t *tree)
c_rbnode_t *	c_rbtree_head (c_rbtree_t *tree)
int	c_rbtree_insert (c_rbtree_t *tree, void *data)
int	c_rbtree_node_delete (c_rbnode_t *node)
c_rbnode_t *	c_rbtree_node_next (c_rbnode_t *node)
c_rbnode_t *	c_rbtree_node_prev (c_rbnode_t *node)
c_rbnode_t *	c_rbtree_tail (c_rbtree_t *tree)
int	c_rbtree_walk (c_rbtree_t *tree, void *data, c_rbtree_visit_func *visitor)