AVL binary search tree

Collaboration diagram for AVL binary search tree:

Data Structures
struct	a_avl_node
	instance structure for AVL binary search tree node More...
union	a_avl
	instance structure for AVL binary search tree root More...

Macros
#define	A_AVL_ROOT   {A_NULL}
#define	a_avl_entry(ptr, type, member)
	access the struct for this entry
#define	a_avl_foreach(cur, root)
	iterate over a AVL binary search tree in-order
#define	a_avl_foreach_reverse(cur, root)
	iterate over a AVL binary search tree in-order reverse
#define	a_avl_pre_foreach(cur, root)
	iterate over a AVL binary search tree preorder
#define	a_avl_pre_foreach_reverse(cur, root)
	iterate over a AVL binary search tree preorder reverse
#define	a_avl_post_foreach(cur, root)
	iterate over a AVL binary search tree postorder
#define	a_avl_post_foreach_reverse(cur, root)
	iterate over a AVL binary search tree postorder reverse
#define	a_avl_fortear(cur, next, root)
	tear a AVL binary search tree using postorder traversal

Typedefs
typedef struct a_avl_node	a_avl_node
	instance structure for AVL binary search tree node
typedef union a_avl	a_avl
	instance structure for AVL binary search tree root

Functions
a_avl_node *	a_avl_parent (a_avl_node const *node)
	access parent of AVL binary search tree node
a_avl_node *	a_avl_init (a_avl_node *node, a_avl_node *parent)
	initialize for AVL binary search tree node
void	a_avl_root (a_avl *root)
	initialize for AVL binary search tree root
a_avl_node *	a_avl_head (a_avl const *root)
	access head node of AVL binary search tree in-order
a_avl_node *	a_avl_tail (a_avl const *root)
	access tail node of AVL binary search tree in-order
a_avl_node *	a_avl_next (a_avl_node *node)
	access next node of AVL binary search tree node in-order
a_avl_node *	a_avl_prev (a_avl_node *node)
	access prev node of AVL binary search tree node in-order
a_avl_node *	a_avl_pre_next (a_avl_node *node)
	access next node of AVL binary search tree node preorder
a_avl_node *	a_avl_pre_prev (a_avl_node *node)
	access prev node of AVL binary search tree node preorder
a_avl_node *	a_avl_post_head (a_avl const *root)
	access head node of AVL binary search tree postorder
a_avl_node *	a_avl_post_tail (a_avl const *root)
	access tail node of AVL binary search tree postorder
a_avl_node *	a_avl_post_next (a_avl_node *node)
	access next node of AVL binary search tree node postorder
a_avl_node *	a_avl_post_prev (a_avl_node *node)
	access prev node of AVL binary search tree node postorder
a_avl_node *	a_avl_tear (a_avl *root, a_avl_node **next)
	tear a node from AVL binary search tree
a_avl_node *	a_avl_search (a_avl const *root, void const *ctx, int(*cmp)(void const *, void const *))
	search specified content from AVL binary search tree
a_avl_node *	a_avl_insert (a_avl *root, a_avl_node *node, int(*cmp)(void const *, void const *))
	insert specified node into AVL binary search tree
void	a_avl_insert_adjust (a_avl *root, a_avl_node *node)
	rebalance the tree after insertion of the specified node
void	a_avl_remove (a_avl *root, a_avl_node *node)
	remove specified node from AVL binary search tree

Detailed Description

Macro Definition Documentation

a_avl_entry

#define a_avl_entry	(		ptr,
			type,
			member )

Value:

a_container_of(ptr, type, member)

access the struct for this entry

Parameters

ptr	the &a_avl_node pointer
type	the type of the struct this is embedded in
member	the name of the a_avl_node within the struct

a_avl_foreach

#define a_avl_foreach	(		cur,
			root )

Value:

    for (a_avl_node *cur = a_avl_head(root); cur; cur = a_avl_next(cur))

iterate over a AVL binary search tree in-order

typedef struct
{
    a_avl_node node;
} T;
a_avl root = A_AVL_ROOT;
a_avl_foreach(cur, &root)
{
    T *it = a_avl_entry(cur, T, node);
}

Parameters

cur	the &a_avl_node to use as a loop counter
root	AVL binary search tree root

a_avl_foreach_reverse

#define a_avl_foreach_reverse	(		cur,
			root )

Value:

    for (a_avl_node *cur = a_avl_tail(root); cur; cur = a_avl_prev(cur))

iterate over a AVL binary search tree in-order reverse

typedef struct
{
    a_avl_node node;
} T;
a_avl root = A_AVL_ROOT;
a_avl_foreach_reverse(cur, &root)
{
    T *it = a_avl_entry(cur, T, node);
}

Parameters

cur	the &a_avl_node to use as a loop counter
root	AVL binary search tree root

a_avl_fortear

#define a_avl_fortear	(		cur,
			next,
			root )

Value:

    for (a_avl_node *next = A_NULL, *cur = a_avl_tear(root, &next); cur; cur = a_avl_tear(root, &next))

tear a AVL binary search tree using postorder traversal

typedef struct
{
    a_avl_node node;
} T;
a_avl root = A_AVL_ROOT;
a_avl_fortear(cur, next, &root)
{
    T *it = a_avl_entry(cur, T, node);
}

Parameters

cur	the &a_avl_node to use as a loop counter
next	the &a_avl_node to use as next node
root	AVL binary search tree root

a_avl_post_foreach

#define a_avl_post_foreach	(		cur,
			root )

Value:

    for (a_avl_node *cur = a_avl_post_head(root); cur; cur = a_avl_post_next(cur))

iterate over a AVL binary search tree postorder

typedef struct
{
    a_avl_node node;
} T;
a_avl root = A_AVL_ROOT;
a_avl_post_foreach(cur, &root)
{
    T *it = a_avl_entry(cur, T, node);
}

Parameters

cur	the &a_avl_node to use as a loop counter
root	AVL binary search tree root

a_avl_post_foreach_reverse

#define a_avl_post_foreach_reverse	(		cur,
			root )

Value:

    for (a_avl_node *cur = a_avl_post_tail(root); cur; cur = a_avl_post_prev(cur))

iterate over a AVL binary search tree postorder reverse

typedef struct
{
    a_avl_node node;
} T;
a_avl root = A_AVL_ROOT;
a_avl_post_foreach_reverse(cur, &root)
{
    T *it = a_avl_entry(cur, T, node);
}

Parameters

cur	the &a_avl_node to use as a loop counter
root	AVL binary search tree root

a_avl_pre_foreach

#define a_avl_pre_foreach	(		cur,
			root )

Value:

    for (a_avl_node *cur = (root)->node; cur; cur = a_avl_pre_next(cur))

iterate over a AVL binary search tree preorder

typedef struct
{
    a_avl_node node;
} T;
a_avl root = A_AVL_ROOT;
a_avl_pre_foreach(cur, &root)
{
    T *it = a_avl_entry(cur, T, node);
}

Parameters

cur	the &a_avl_node to use as a loop counter
root	AVL binary search tree root

a_avl_pre_foreach_reverse

#define a_avl_pre_foreach_reverse	(		cur,
			root )

Value:

    for (a_avl_node *cur = (root)->node; cur; cur = a_avl_pre_prev(cur))

iterate over a AVL binary search tree preorder reverse

typedef struct
{
    a_avl_node node;
} T;
a_avl root = A_AVL_ROOT;
a_avl_pre_foreach_reverse(cur, &root)
{
    T *it = a_avl_entry(cur, T, node);
}

Parameters

cur	the &a_avl_node to use as a loop counter
root	AVL binary search tree root

Function Documentation

a_avl_head()

a_avl_node * a_avl_head

(

a_avl const *

root

)

access head node of AVL binary search tree in-order

Parameters

[in]

root

AVL binary search tree root

Returns

head node or null

a_avl_init()

a_avl_node * a_avl_init	(	a_avl_node *	node,
		a_avl_node *	parent )

initialize for AVL binary search tree node

Parameters

[in]	node	node to be initialized
[in]	parent	node parent

Returns

initialized node

a_avl_insert()

a_avl_node * a_avl_insert	(	a_avl *	root,
		a_avl_node *	node,
		int(*	cmp )(void const *, void const *) )

insert specified node into AVL binary search tree

Parameters

[in]	root	AVL binary search tree root
[in]	node	specified tree node
[in]	cmp	a 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_avl_insert_adjust()

void a_avl_insert_adjust	(	a_avl *	root,
		a_avl_node *	node )

rebalance the tree after insertion of the specified node

Parameters

[in]	root	AVL binary search tree root
[in]	node	insert tree node

a_avl_next()

a_avl_node * a_avl_next

(

a_avl_node *

node

)

access next node of AVL binary search tree node in-order

Parameters

[in]

node

AVL binary search tree node

Returns

next node or null

a_avl_parent()

a_avl_node * a_avl_parent

(

a_avl_node const *

node

)

access parent of AVL binary search tree node

Parameters

[in]

node

points to AVL binary search tree node

Returns

a pointer to the parent of the specified AVL tree node, or null if it is already the root of the tree.

a_avl_post_head()

a_avl_node * a_avl_post_head

(

a_avl const *

root

)

access head node of AVL binary search tree postorder

Parameters

[in]

root

AVL binary search tree root

Returns

head node or null

a_avl_post_next()

a_avl_node * a_avl_post_next

(

a_avl_node *

node

)

access next node of AVL binary search tree node postorder

Parameters

[in]

node

AVL binary search tree node

Returns

next node or null

a_avl_post_prev()

a_avl_node * a_avl_post_prev

(

a_avl_node *

node

)

access prev node of AVL binary search tree node postorder

Parameters

[in]

node

AVL binary search tree node

Returns

prev node or null

a_avl_post_tail()

a_avl_node * a_avl_post_tail

(

a_avl const *

root

)

access tail node of AVL binary search tree postorder

Parameters

[in]

root

AVL binary search tree root

Returns

tail node or null

a_avl_pre_next()

a_avl_node * a_avl_pre_next

(

a_avl_node *

node

)

access next node of AVL binary search tree node preorder

Parameters

[in]

node

AVL binary search tree node

Returns

next node or null

a_avl_pre_prev()

a_avl_node * a_avl_pre_prev

(

a_avl_node *

node

)

access prev node of AVL binary search tree node preorder

Parameters

[in]

node

AVL binary search tree node

Returns

prev node or null

a_avl_prev()

a_avl_node * a_avl_prev

(

a_avl_node *

node

)

access prev node of AVL binary search tree node in-order

Parameters

[in]

node

AVL binary search tree node

Returns

prev node or null

a_avl_remove()

void a_avl_remove	(	a_avl *	root,
		a_avl_node *	node )

remove specified node from AVL binary search tree

Parameters

[in]	root	AVL binary search tree root
[in]	node	specified tree node

a_avl_root()

void a_avl_root

(

a_avl *

root

)

initialize for AVL binary search tree root

Parameters

[in,out]

root

AVL binary search tree root

a_avl_search()

a_avl_node * a_avl_search	(	a_avl const *	root,
		void const *	ctx,
		int(*	cmp )(void const *, void const *) )

search specified content from AVL binary search tree

Parameters

[in]	root	AVL binary search tree root
[in]	ctx	specified content
[in]	cmp	a 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_avl_tail()

a_avl_node * a_avl_tail

(

a_avl const *

root

)

access tail node of AVL binary search tree in-order

Parameters

[in]

root

AVL binary search tree root

Returns

tail node or null

a_avl_tear()

a_avl_node * a_avl_tear	(	a_avl *	root,
		a_avl_node **	next )

tear a node from AVL binary search tree

Parameters

[in]	root	AVL binary search tree root
[in,out]	next	input starting node or, if null, root node. output next node or null.

Returns

teared node or null