|
static void | destroy_helper (node *n) |
|
static void | count_helper (node *n, l_int32 *pcount) |
|
static void | print_tree_helper (FILE *fp, node *n, l_int32 keytype, l_int32 indent) |
|
static l_int32 | compareKeys (l_int32 keytype, RB_TYPE left, RB_TYPE right) |
|
static node * | grandparent (node *n) |
|
static node * | sibling (node *n) |
|
static node * | uncle (node *n) |
|
static l_int32 | node_color (node *n) |
|
static node * | new_node (RB_TYPE key, RB_TYPE value, l_int32 node_color, node *left, node *right) |
|
static node * | lookup_node (L_RBTREE *t, RB_TYPE key) |
|
static void | rotate_left (L_RBTREE *t, node *n) |
|
static void | rotate_right (L_RBTREE *t, node *n) |
|
static void | replace_node (L_RBTREE *t, node *oldn, node *newn) |
|
static void | insert_case1 (L_RBTREE *t, node *n) |
|
static void | insert_case2 (L_RBTREE *t, node *n) |
|
static void | insert_case3 (L_RBTREE *t, node *n) |
|
static void | insert_case4 (L_RBTREE *t, node *n) |
|
static void | insert_case5 (L_RBTREE *t, node *n) |
|
static node * | maximum_node (node *root) |
|
static void | delete_case1 (L_RBTREE *t, node *n) |
|
static void | delete_case2 (L_RBTREE *t, node *n) |
|
static void | delete_case3 (L_RBTREE *t, node *n) |
|
static void | delete_case4 (L_RBTREE *t, node *n) |
|
static void | delete_case5 (L_RBTREE *t, node *n) |
|
static void | delete_case6 (L_RBTREE *t, node *n) |
|
static void | verify_properties (L_RBTREE *t) |
|
L_RBTREE * | l_rbtreeCreate (l_int32 keytype) |
|
RB_TYPE * | l_rbtreeLookup (L_RBTREE *t, RB_TYPE key) |
|
void | l_rbtreeInsert (L_RBTREE *t, RB_TYPE key, RB_TYPE value) |
|
void | l_rbtreeDelete (L_RBTREE *t, RB_TYPE key) |
|
void | l_rbtreeDestroy (L_RBTREE **pt) |
|
L_RBTREE_NODE * | l_rbtreeGetFirst (L_RBTREE *t) |
|
L_RBTREE_NODE * | l_rbtreeGetNext (L_RBTREE_NODE *n) |
|
L_RBTREE_NODE * | l_rbtreeGetLast (L_RBTREE *t) |
|
L_RBTREE_NODE * | l_rbtreeGetPrev (L_RBTREE_NODE *n) |
|
l_int32 | l_rbtreeGetCount (L_RBTREE *t) |
|
void | l_rbtreePrint (FILE *fp, L_RBTREE *t) |
|
Basic functions for using red-black trees. These are "nearly" balanced
sorted trees with ordering by key that allows insertion, lookup and
deletion of key/value pairs in log(n) time.
We use red-black trees to implement our version of:
* a map: a function that maps keys to values (e.g., int64 --> int64).
* a set: a collection that is sorted by unique keys (without
associated values)
There are 5 invariant properties of RB trees:
(1) Each node is either red or black.
(2) The root node is black.
(3) All leaves are black and contain no data (null).
(4) Every red node has two children and both are black. This is
equivalent to requiring the parent of every red node to be black.
(5) All paths from any given node to its leaf nodes contain the
same number of black nodes.
Interface to red-black tree
L_RBTREE *l_rbtreeCreate()
RB_TYPE *l_rbtreeLookup()
void l_rbtreeInsert()
void l_rbtreeDelete()
void l_rbtreeDestroy()
L_RBTREE_NODE *l_rbtreeGetFirst()
L_RBTREE_NODE *l_rbtreeGetNext()
L_RBTREE_NODE *l_rbtreeGetLast()
L_RBTREE_NODE *l_rbtreeGetPrev()
l_int32 l_rbtreeGetCount()
void l_rbtreePrint()
General comparison function
static l_int32 compareKeys()
Definition in file rbtree.c.