rbt.h File Reference

red–black self-balancing binary search tree More...

#include "a.h"

Include dependency graph for rbt.h:

Go to the source code of this file.

Data Structures
struct	a_rbt_node
	instance structure for red–black binary search tree node More...
union	a_rbt
	instance structure for red–black binary search tree root More...

Macros
#define	A_RBT_ROOT   {A_NULL}
#define	a_rbt_entry(ptr, type, member)
	access the struct for this entry
#define	a_rbt_foreach(cur, root)
	iterate over a red–black binary search tree in-order
#define	A_RBT_FOREACH(cur, root)
#define	a_rbt_foreach_reverse(cur, root)
	iterate over a red–black binary search tree in-order reverse
#define	A_RBT_FOREACH_REVERSE(cur, root)
#define	a_rbt_pre_foreach(cur, root)
	iterate over a red–black binary search tree preorder
#define	A_RBT_PRE_FOREACH(cur, root)
#define	a_rbt_pre_foreach_reverse(cur, root)
	iterate over a red–black binary search tree preorder reverse
#define	A_RBT_PRE_FOREACH_REVERSE(cur, root)
#define	a_rbt_post_foreach(cur, root)
	iterate over a red–black binary search tree postorder
#define	A_RBT_POST_FOREACH(cur, root)
#define	a_rbt_post_foreach_reverse(cur, root)
	iterate over a red–black binary search tree postorder reverse
#define	A_RBT_POST_FOREACH_REVERSE(cur, root)
#define	a_rbt_fortear(cur, next, root)
	tear a red–black binary search tree using postorder traversal
#define	A_RBT_FORTEAR(cur, next, root)

Typedefs
typedef struct a_rbt_node	a_rbt_node
	instance structure for red–black binary search tree node
typedef union a_rbt	a_rbt
	instance structure for red–black binary search tree root

Functions
a_rbt_node *	a_rbt_parent (a_rbt_node const *node)
	access parent of red–black binary search tree node
a_rbt_node *	a_rbt_init (a_rbt_node *node, a_rbt_node *parent)
	initialize for red–black binary search tree node
void	a_rbt_root (a_rbt *root)
	initialize for red–black binary search tree root
a_rbt_node *	a_rbt_head (a_rbt const *root)
	access head node of red–black binary search tree in-order
a_rbt_node *	a_rbt_tail (a_rbt const *root)
	access tail node of red–black binary search tree in-order
a_rbt_node *	a_rbt_next (a_rbt_node *node)
	access next node of red–black binary search tree node in-order
a_rbt_node *	a_rbt_prev (a_rbt_node *node)
	access prev node of red–black binary search tree node in-order
a_rbt_node *	a_rbt_pre_next (a_rbt_node *node)
	access next node of red–black binary search tree node preorder
a_rbt_node *	a_rbt_pre_prev (a_rbt_node *node)
	access prev node of red–black binary search tree node preorder
a_rbt_node *	a_rbt_post_head (a_rbt const *root)
	access head node of red–black binary search tree postorder
a_rbt_node *	a_rbt_post_tail (a_rbt const *root)
	access tail node of red–black binary search tree postorder
a_rbt_node *	a_rbt_post_next (a_rbt_node *node)
	access next node of red–black binary search tree node postorder
a_rbt_node *	a_rbt_post_prev (a_rbt_node *node)
	access prev node of red–black binary search tree node postorder
a_rbt_node *	a_rbt_tear (a_rbt *root, a_rbt_node **next)
	tear a node from red–black binary search tree
a_rbt_node *	a_rbt_search (a_rbt const *root, void const *ctx, int(*cmp)(void const *, void const *))
	search specified content from red–black binary search tree
a_rbt_node *	a_rbt_insert (a_rbt *root, a_rbt_node *node, int(*cmp)(void const *, void const *))
	insert specified node into red–black binary search tree
void	a_rbt_insert_adjust (a_rbt *root, a_rbt_node *node)
	rebalance the tree after insertion of the specified node
void	a_rbt_remove (a_rbt *root, a_rbt_node *node)
	remove specified node from red–black binary search tree

Detailed Description

red–black self-balancing binary search tree