Макросы |
#define | VERIFY_RBTREE 0 /* only for debugging */ |
#define | INDENT_STEP 4 |
Определения типов |
typedef L_RBTREE_NODE | node |
Перечисления |
enum | { L_RED_NODE = 1,
L_BLACK_NODE = 2
} |
Функции |
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 node * | grandparent (node *n) |
static node * | sibling (node *n) |
static node * | uncle (node *n) |
static void | verify_properties (L_RBTREE *t) |
static void | verify_property_1 (node *root) |
static void | verify_property_2 (node *root) |
static l_int32 | node_color (node *n) |
static void | verify_property_4 (node *root) |
static void | verify_property_5 (node *root) |
static void | verify_property_5_helper (node *n, int black_count, int *black_count_path) |
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) |
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) |
l_int32 | l_compareKeys (l_int32 keytype, RB_TYPE left, RB_TYPE right) |