AVL tree

Collaboration diagram for AVL tree:

Data Structures
struct	avl
	A single node of an AVL tree. More...

Macros
#define	AVL_EMPTY_NODE   ((avl_t){0})
	Create an empty AVL node, with no child nor parent.

Typedefs
typedef int(*	avl_compare_t) (const avl_t *left, const avl_t *right)
	Comparison function used during AVL tree operations. More...

Functions
static ssize_t	avl_height (const avl_t *avl)
	Returns the height of an AVL tree.
static bool	avl_is_root (const avl_t *avl)
	Returns hether the given AVL node is the root of a tree.
const avl_t *	avl_search (avl_t *root, avl_t *value, avl_compare_t)
	Search a value inside an AVL tree. More...
avl_t *	avl_insert (avl_t **root, avl_t *new, avl_compare_t)
	Insert a new node inside an AVL tree. More...
avl_t *	avl_remove (avl_t **root, avl_t *value, avl_compare_t)
	Remove a value from an AVL tree. More...
void	avl_print (avl_t *root, void(*print)(const avl_t *))
	Print the content of an AVL tree. More...
const avl_t *	avl_min (const avl_t *root)
	Find the minimum value inside an AVL tree. More...
const avl_t *	avl_max (const avl_t *root)
	Find the maximum value inside an AVL tree. More...

Detailed Description

AVL

An AVL tree is a self-balancing BST where the difference between heights of left and right subtrees for any node cannot be more than one.

see: https://en.wikipedia.org/wiki/AVL_tree

Design

This library is designed to be used with intrusive structs. As such, it does NOT allocate nor free any memory whatsoever.

This design is highly inspired by linux's intrusive linked lists: https://www.data-structures-in-practice.com/intrusive-linked-lists/

Typedef Documentation

avl_compare_t

typedef int(* avl_compare_t) (const avl_t *left, const avl_t *right)

It performs an arbitrary comparison between 2 AVL nodes.

Returns

0 if both are equal equal, -1 if left is lower, 1 if its greater.

Function Documentation

avl_insert()

avl_t * avl_insert	(	avl_t **	root,
		avl_t *	new,
		avl_compare_t	compare
	)

Parameters

root	The root of the AVL tree
new	The new node to insert inside the tree
compare	The comparison function used for this tree

Note

value is passed as the left parameter of comparison

Returns

The newly inserted node

avl_max()

const avl_t * avl_max

(

const avl_t *

root

)

Parameters

root	The root of the tree

Returns

The maximum value's node, NULL if tree is empty

avl_min()

const avl_t * avl_min

(

const avl_t *

root

)

Parameters

root	The root of the tree

Returns

The minimum value's node, NULL if tree is empty

avl_print()

void avl_print	(	avl_t *	root,
		void(*)(const avl_t *)	print
	)

The AVL is printed in an in-order depth-first way.

Warning

This function visits the tree recursively, this means a higher stack usage. Be careful when you use it, more particularily inside the kernel.

Parameters

root	The root of the AVL tree
print	The function used to print the content of a node

avl_remove()

avl_t * avl_remove	(	avl_t **	root,
		avl_t *	value,
		avl_compare_t	compare
	)

Parameters

root	The root of the AVL tree
value	The value to remove from the AVL tree
compare	The comparison function used for this tree

Note

value is passed as the left parameter of comparison

Returns

The removed value if any, else NULL

avl_search()

const avl_t * avl_search	(	avl_t *	root,
		avl_t *	value,
		avl_compare_t	compare
	)

Parameters

root	The root of the AVL tree
value	The value to find
compare	The comparison function used for this AVL tree

Returns

The found node if any, else NULL

Value must be of the AVL type to be used with the comparison function. But its content need not necessarily be complete, as long as it has the necesary content to perform the comparison operation.

Note

value is passed as the left parameter of comparison