doc
|
Go to the source code of this file.
Data Structures | |
struct | c_rbnode_s |
struct | c_rbtree_s |
Macros | |
#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 *, void *) |
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) |
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:
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.