There are three ways to traverse a binary tree. The first, known as "preorder," visits the root node, then traverses the left subtree in preorder, then traverses the right subtree in preorder. The second, known an "inorder," traverses the left subtree in inorder, then the root node, then the right subtree in inorder. (This particular ordering retrieves the nodes in lexical order; thus its name.) The third ordering is known as "postorder"; this ordering traverses the left subtree, the right subtree, then visits the root node. To iterate over the tree in one of these orderings, simply call rt_iter() (or rt_next() or rt_prev()) with the RBT_ORDER_PRE, RBT_ORDER_IN, or RBT_ORDER_POST flags. You may OR these flags with DB_FLAG_REVERSE to reverse the traversal ordering, if you wish.
|
Data Structures |
| struct | _rb_tree_s |
| | Red-black tree structure. More...
|
| struct | _rb_node_s |
| | Red-black tree node structure. More...
|
Defines |
| #define | RB_TREE_MAGIC |
| | Red-black tree magic number.
|
| #define | RB_TREE_INIT(comp, extra) |
| | Red-black tree static initializer.
|
| #define | rt_verify(tree) |
| | Red-black tree verification macro.
|
| #define | rt_frozen(tree) |
| | Determine if a red-black tree is frozen.
|
| #define | rt_count(tree) |
| | Red-black tree count.
|
| #define | rt_root(tree) |
| | Red-black tree root node.
|
| #define | rt_comp(tree) |
| | Red-black tree comparison function.
|
| #define | rt_extra(tree) |
| | Extra pointer data in a red-black tree.
|
| #define | RBT_ORDER_PRE |
| | Preorder tree traversal method.
|
| #define | RBT_ORDER_IN |
| | Inorder tree traversal method.
|
| #define | RBT_ORDER_POST |
| | Postorder tree traversal method.
|
| #define | RBT_ORDER_MASK |
| | Tree traversal method mask.
|
| #define | rt_prev(tree, node_io, flags) |
| | Get the previous node.
|
| #define | RB_NODE_MAGIC |
| | Red-black tree node magic number.
|
| #define | RB_NODE_INIT(value) |
| | Red-black tree node static initializer.
|
| #define | rn_verify(node) |
| | Red-black tree node verification macro.
|
| #define | rn_color(node) |
| | Red-black tree node color.
|
| #define | rn_tree(node) |
| | Red-black tree node's tree pointer.
|
| #define | rn_parent(node) |
| | Red-black tree node's parent pointer.
|
| #define | rn_left(node) |
| | Red-black tree node's left pointer.
|
| #define | rn_right(node) |
| | Red-black tree node's right pointer.
|
| #define | rn_key(node) |
| | Red-black tree node's key pointer.
|
| #define | rn_value(node) |
| | Red-black tree node's value pointer.
|
| #define | rn_isblack(node) |
| | Test if a given node is black.
|
| #define | rn_isred(node) |
| | Test if a given node is red.
|
| #define | rn_isleft(node) |
| | Test if a given node is the left node of its parent.
|
| #define | rn_isright(node) |
| | Test if a given node is the right node of its parent.
|
| #define | uncle(node) |
| | Locate the uncle of a node.
|
| #define | flip(node) |
| | Flip the color of a node.
|
| #define | _rn_clear(node) |
| | Clear a node.
|
| #define | _rt_update_parent(tree, node, new) |
| | Update a node's parent.
|
| #define | isleft(par, n) |
| | Determine if node is a left child of its parent.
|
| #define | sel_lr(t, n) |
| | Select a child node based on a condition.
|
| #define | sibling(par, n) |
| | Locate the sibling of a node.
|
| #define | l_neph(par, n) |
| | Locate "closer" nephew of a node.
|
| #define | r_neph(par, n) |
| | Locate "further" nephew of a node.
|
Typedefs |
| typedef _rb_tree_s | rb_tree_t |
| | Red-black tree.
|
| typedef _rb_node_s | rb_node_t |
| | Red-black tree node.
|
| typedef unsigned long(* | rb_iter_t )(rb_tree_t *tree, rb_node_t *node, void *extra) |
| | Red-black tree iteration callback.
|
| typedef long(* | rb_comp_t )(rb_tree_t *tree, db_key_t *key1, db_key_t *key2) |
| | Red-black tree comparison callback.
|
| typedef enum _rb_color_e | rb_color_t |
| | Red-black tree node color.
|
Enumerations |
| enum | _rb_color_e { RB_COLOR_NONE,
RB_COLOR_RED,
RB_COLOR_BLACK
} |
| | Red-black tree node color. More...
|
Functions |
| long | rbtree_comp (rb_tree_t *tree, db_key_t *key1, db_key_t *key2) |
| | Red-black tree comparison function.
|
| unsigned long | rt_init (rb_tree_t *tree, rb_comp_t comp, void *extra) |
| | Dynamically initialize a red-black tree.
|
| unsigned long | rt_add (rb_tree_t *tree, rb_node_t *node, db_key_t *key) |
| | Add a node to a red-black tree.
|
| unsigned long | rt_move (rb_tree_t *tree, rb_node_t *node, db_key_t *key) |
| | Move a node in a red-black tree.
|
| unsigned long | rt_remove (rb_tree_t *tree, rb_node_t *node) |
| | Remove a node from a red-black tree.
|
| unsigned long | rt_find (rb_tree_t *tree, rb_node_t **node_p, db_key_t *key) |
| | Find an entry in a red-black table.
|
| unsigned long | rt_next (rb_tree_t *tree, rb_node_t **node_io, unsigned long flags) |
| | Get the next node.
|
| unsigned long | rt_iter (rb_tree_t *tree, rb_node_t *start, rb_iter_t iter_func, void *extra, unsigned long flags) |
| | Iterate over each entry in a red-black tree.
|
| unsigned long | rt_flush (rb_tree_t *tree, rb_iter_t flush_func, void *extra) |
| | Flush a red-black tree.
|
| unsigned long | rn_init (rb_node_t *node, void *value) |
| | Dynamically initialize a red-black tree node.
|
| rb_node_t * | _rb_locate (rb_tree_t *tree, rb_node_t *node, db_key_t *key) |
| | Locate or insert a red-black tree node.
|
| void | _rb_rotate (rb_tree_t *tree, rb_node_t *child) |
| | Rotate tree nodes.
|
