liba 0.1.15
An algorithm library based on C/C++
Loading...
Searching...
No Matches
red–black binary search tree
Collaboration diagram for red–black binary search tree:

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_reverse(cur, root)
 iterate over a red–black binary search tree in-order reverse
 
#define a_rbt_pre_foreach(cur, root)
 iterate over a red–black binary search tree preorder
 
#define a_rbt_pre_foreach_reverse(cur, root)
 iterate over a red–black binary search tree preorder reverse
 
#define a_rbt_post_foreach(cur, root)
 iterate over a red–black binary search tree postorder
 
#define a_rbt_post_foreach_reverse(cur, root)
 iterate over a red–black binary search tree postorder reverse
 
#define a_rbt_fortear(cur, next, root)
 tear a red–black binary search tree using postorder traversal
 

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_nodea_rbt_parent (a_rbt_node const *node)
 access parent of red–black binary search tree node
 
a_rbt_nodea_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_nodea_rbt_head (a_rbt const *root)
 access head node of red–black binary search tree in-order
 
a_rbt_nodea_rbt_tail (a_rbt const *root)
 access tail node of red–black binary search tree in-order
 
a_rbt_nodea_rbt_next (a_rbt_node *node)
 access next node of red–black binary search tree node in-order
 
a_rbt_nodea_rbt_prev (a_rbt_node *node)
 access prev node of red–black binary search tree node in-order
 
a_rbt_nodea_rbt_pre_next (a_rbt_node *node)
 access next node of red–black binary search tree node preorder
 
a_rbt_nodea_rbt_pre_prev (a_rbt_node *node)
 access prev node of red–black binary search tree node preorder
 
a_rbt_nodea_rbt_post_head (a_rbt const *root)
 access head node of red–black binary search tree postorder
 
a_rbt_nodea_rbt_post_tail (a_rbt const *root)
 access tail node of red–black binary search tree postorder
 
a_rbt_nodea_rbt_post_next (a_rbt_node *node)
 access next node of red–black binary search tree node postorder
 
a_rbt_nodea_rbt_post_prev (a_rbt_node *node)
 access prev node of red–black binary search tree node postorder
 
a_rbt_nodea_rbt_tear (a_rbt *root, a_rbt_node **next)
 tear a node from red–black binary search tree
 
a_rbt_nodea_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_nodea_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

Macro Definition Documentation

◆ a_rbt_entry

#define a_rbt_entry ( ptr,
type,
member )
Value:
a_container_of(ptr, type, member)
#define a_container_of(ptr, type, member)
container of a structure member
Definition a.h:888

access the struct for this entry

Parameters
ptrthe &a_rbt_node pointer
typethe type of the struct this is embedded in
memberthe name of the a_rbt_node within the struct

◆ a_rbt_foreach

#define a_rbt_foreach ( cur,
root )
Value:
for (a_rbt_node *cur = a_rbt_head(root); cur; cur = a_rbt_next(cur))
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_next(a_rbt_node *node)
access next node of red–black binary search tree node in-order
instance structure for red–black binary search tree node
Definition rbt.h:25

iterate over a red–black binary search tree in-order

typedef struct
{
a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
a_rbt_foreach(cur, &root)
{
T *it = a_rbt_entry(cur, T, node);
}
#define a_rbt_entry(ptr, type, member)
access the struct for this entry
Definition rbt.h:219
#define a_rbt_foreach(cur, root)
iterate over a red–black binary search tree in-order
Definition rbt.h:237
instance structure for red–black binary search tree root
Definition rbt.h:78
Parameters
curthe &a_rbt_node to use as a loop counter
rootred–black binary search tree root

◆ a_rbt_foreach_reverse

#define a_rbt_foreach_reverse ( cur,
root )
Value:
for (a_rbt_node *cur = a_rbt_tail(root); cur; cur = a_rbt_prev(cur))
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_tail(a_rbt const *root)
access tail node of red–black binary search tree in-order

iterate over a red–black binary search tree in-order reverse

typedef struct
{
a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
{
T *it = a_rbt_entry(cur, T, node);
}
#define a_rbt_foreach_reverse(cur, root)
iterate over a red–black binary search tree in-order reverse
Definition rbt.h:256
Parameters
curthe &a_rbt_node to use as a loop counter
rootred–black binary search tree root

◆ a_rbt_fortear

#define a_rbt_fortear ( cur,
next,
root )
Value:
for (a_rbt_node *next = A_NULL, *cur = a_rbt_tear(root, &next); cur; cur = a_rbt_tear(root, &next))
a_rbt_node * a_rbt_tear(a_rbt *root, a_rbt_node **next)
tear a node from red–black binary search tree

tear a red–black binary search tree using postorder traversal

typedef struct
{
a_rbt_node node;
} T;
a_rbt root = A_AVL_ROOT;
a_rbt_fortear(cur, next, &root)
{
T *it = a_rbt_entry(cur, T, node);
}
#define a_rbt_fortear(cur, next, root)
tear a red–black binary search tree using postorder traversal
Definition rbt.h:352
Parameters
curthe &a_rbt_node to use as a loop counter
nextthe &a_rbt_node to use as next node
rootred–black binary search tree root

◆ a_rbt_post_foreach

#define a_rbt_post_foreach ( cur,
root )
Value:
for (a_rbt_node *cur = a_rbt_post_head(root); cur; cur = a_rbt_post_next(cur))
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_next(a_rbt_node *node)
access next node of red–black binary search tree node postorder

iterate over a red–black binary search tree postorder

typedef struct
{
a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
a_rbt_post_foreach(cur, &root)
{
T *it = a_rbt_entry(cur, T, node);
}
#define a_rbt_post_foreach(cur, root)
iterate over a red–black binary search tree postorder
Definition rbt.h:313
Parameters
curthe &a_rbt_node to use as a loop counter
rootred–black binary search tree root

◆ a_rbt_post_foreach_reverse

#define a_rbt_post_foreach_reverse ( cur,
root )
Value:
for (a_rbt_node *cur = a_rbt_post_tail(root); cur; cur = a_rbt_post_prev(cur))
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_post_tail(a_rbt const *root)
access tail node of red–black binary search tree postorder

iterate over a red–black binary search tree postorder reverse

typedef struct
{
a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
{
T *it = a_rbt_entry(cur, T, node);
}
#define a_rbt_post_foreach_reverse(cur, root)
iterate over a red–black binary search tree postorder reverse
Definition rbt.h:332
Parameters
curthe &a_rbt_node to use as a loop counter
rootred–black binary search tree root

◆ a_rbt_pre_foreach

#define a_rbt_pre_foreach ( cur,
root )
Value:
for (a_rbt_node *cur = (root)->node; cur; cur = a_rbt_pre_next(cur))
a_rbt_node * a_rbt_pre_next(a_rbt_node *node)
access next node of red–black binary search tree node preorder

iterate over a red–black binary search tree preorder

typedef struct
{
a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
a_rbt_pre_foreach(cur, &root)
{
T *it = a_rbt_entry(cur, T, node);
}
#define a_rbt_pre_foreach(cur, root)
iterate over a red–black binary search tree preorder
Definition rbt.h:275
Parameters
curthe &a_rbt_node to use as a loop counter
rootred–black binary search tree root

◆ a_rbt_pre_foreach_reverse

#define a_rbt_pre_foreach_reverse ( cur,
root )
Value:
for (a_rbt_node *cur = (root)->node; cur; cur = a_rbt_pre_prev(cur))
a_rbt_node * a_rbt_pre_prev(a_rbt_node *node)
access prev node of red–black binary search tree node preorder

iterate over a red–black binary search tree preorder reverse

typedef struct
{
a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
{
T *it = a_rbt_entry(cur, T, node);
}
#define a_rbt_pre_foreach_reverse(cur, root)
iterate over a red–black binary search tree preorder reverse
Definition rbt.h:294
Parameters
curthe &a_rbt_node to use as a loop counter
rootred–black binary search tree root

Function Documentation

◆ a_rbt_head()

a_rbt_node * a_rbt_head ( a_rbt const * root)

access head node of red–black binary search tree in-order

Parameters
[in]rootred–black binary search tree root
Returns
head node or null

◆ a_rbt_init()

a_rbt_node * a_rbt_init ( a_rbt_node * node,
a_rbt_node * parent )

initialize for red–black binary search tree node

Parameters
[in]nodenode to be initialized
[in]parentnode parent
Returns
initialized node

◆ a_rbt_insert()

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

Parameters
[in]rootred–black binary search tree root
[in]nodespecified tree node
[in]cmpa function that compares two nodes
  • cmp(lhs,rhs)==0 *lhs is equivalent to *rhs
  • cmp(lhs,rhs)<0 *lhs goes before *rhs
  • cmp(lhs,rhs)>0 *lhs goes after *rhs
Returns
null or duplicate node

◆ a_rbt_insert_adjust()

void a_rbt_insert_adjust ( a_rbt * root,
a_rbt_node * node )

rebalance the tree after insertion of the specified node

Parameters
[in]rootred–black binary search tree root
[in]nodeinsert tree node

◆ a_rbt_next()

a_rbt_node * a_rbt_next ( a_rbt_node * node)

access next node of red–black binary search tree node in-order

Parameters
[in]nodered–black binary search tree node
Returns
next node or null

◆ a_rbt_parent()

a_rbt_node * a_rbt_parent ( a_rbt_node const * node)

access parent of red–black binary search tree node

Parameters
[in]nodepoints to red–black binary search tree node
Returns
a pointer to the parent of the specified red–black tree node, or null if it is already the root of the tree.

◆ a_rbt_post_head()

a_rbt_node * a_rbt_post_head ( a_rbt const * root)

access head node of red–black binary search tree postorder

Parameters
[in]rootred–black binary search tree root
Returns
head node or null

◆ a_rbt_post_next()

a_rbt_node * a_rbt_post_next ( a_rbt_node * node)

access next node of red–black binary search tree node postorder

Parameters
[in]nodered–black binary search tree node
Returns
next node or null

◆ a_rbt_post_prev()

a_rbt_node * a_rbt_post_prev ( a_rbt_node * node)

access prev node of red–black binary search tree node postorder

Parameters
[in]nodered–black binary search tree node
Returns
prev node or null

◆ a_rbt_post_tail()

a_rbt_node * a_rbt_post_tail ( a_rbt const * root)

access tail node of red–black binary search tree postorder

Parameters
[in]rootred–black binary search tree root
Returns
tail node or null

◆ a_rbt_pre_next()

a_rbt_node * a_rbt_pre_next ( a_rbt_node * node)

access next node of red–black binary search tree node preorder

Parameters
[in]nodered–black binary search tree node
Returns
next node or null

◆ a_rbt_pre_prev()

a_rbt_node * a_rbt_pre_prev ( a_rbt_node * node)

access prev node of red–black binary search tree node preorder

Parameters
[in]nodered–black binary search tree node
Returns
prev node or null

◆ a_rbt_prev()

a_rbt_node * a_rbt_prev ( a_rbt_node * node)

access prev node of red–black binary search tree node in-order

Parameters
[in]nodered–black binary search tree node
Returns
prev node or null

◆ a_rbt_remove()

void a_rbt_remove ( a_rbt * root,
a_rbt_node * node )

remove specified node from red–black binary search tree

Parameters
[in]rootred–black binary search tree root
[in]nodespecified tree node

◆ a_rbt_root()

void a_rbt_root ( a_rbt * root)

initialize for red–black binary search tree root

Parameters
[in,out]rootred–black binary search tree root

◆ a_rbt_search()

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

Parameters
[in]rootred–black binary search tree root
[in]ctxspecified content
[in]cmpa function that compares two nodes
  • cmp(lhs,rhs)==0 *lhs is equivalent to *rhs
  • cmp(lhs,rhs)<0 *lhs goes before *rhs
  • cmp(lhs,rhs)>0 *lhs goes after *rhs
Returns
specified node or null

◆ a_rbt_tail()

a_rbt_node * a_rbt_tail ( a_rbt const * root)

access tail node of red–black binary search tree in-order

Parameters
[in]rootred–black binary search tree root
Returns
tail node or null

◆ a_rbt_tear()

a_rbt_node * a_rbt_tear ( a_rbt * root,
a_rbt_node ** next )

tear a node from red–black binary search tree

Parameters
[in]rootred–black binary search tree root
[in,out]nextinput starting node or, if null, root node. output next node or null.
Returns
teared node or null