Balanced binary tree. More...

This graph shows which files directly or indirectly include this file:

Macros
#define	AVL_TREE_NULL ((void *) 0)
	A null AVLTreeValue. More...

Typedefs
typedef struct _AVLTree	AVLTree
	An AVL tree balanced binary tree. More...

typedef void *	AVLTreeKey
	A key for an AVLTree. More...

typedef void *	AVLTreeValue
	A value stored in an AVLTree. More...

typedef struct _AVLTreeNode	AVLTreeNode
	A node in an AVL tree. More...

typedef int(*	AVLTreeCompareFunc) (AVLTreeValue value1, AVLTreeValue value2)
	Type of function used to compare keys in an AVL tree. More...

Enumerations
enum	AVLTreeNodeSide { AVL_TREE_NODE_LEFT = 0, AVL_TREE_NODE_RIGHT = 1 }
	An AVLTreeNode can have left and right children. More...

Functions
AVLTree *	avl_tree_new (AVLTreeCompareFunc compare_func)
	Create a new AVL tree. More...

void	avl_tree_free (AVLTree *tree)
	Destroy an AVL tree. More...

AVLTreeNode *	avl_tree_insert (AVLTree *tree, AVLTreeKey key, AVLTreeValue value)
	Insert a new key-value pair into an AVL tree. More...

void	avl_tree_remove_node (AVLTree tree, AVLTreeNode node)
	Remove a node from a tree. More...

int	avl_tree_remove (AVLTree *tree, AVLTreeKey key)
	Remove an entry from a tree, specifying the key of the node to remove. More...

AVLTreeNode *	avl_tree_lookup_node (AVLTree *tree, AVLTreeKey key)
	Search an AVL tree for a node with a particular key. More...

AVLTreeValue	avl_tree_lookup (AVLTree *tree, AVLTreeKey key)
	Search an AVL tree for a value corresponding to a particular key. More...

AVLTreeNode *	avl_tree_root_node (AVLTree *tree)
	Find the root node of a tree. More...

AVLTreeKey	avl_tree_node_key (AVLTreeNode *node)
	Retrieve the key for a given tree node. More...

AVLTreeValue	avl_tree_node_value (AVLTreeNode *node)
	Retrieve the value at a given tree node. More...

AVLTreeNode *	avl_tree_node_child (AVLTreeNode *node, AVLTreeNodeSide side)
	Find the child of a given tree node. More...

AVLTreeNode *	avl_tree_node_parent (AVLTreeNode *node)
	Find the parent node of a given tree node. More...

int	avl_tree_subtree_height (AVLTreeNode *node)
	Find the height of a subtree. More...

AVLTreeValue *	avl_tree_to_array (AVLTree *tree)
	Convert the keys in an AVL tree into a C array. More...

int	avl_tree_num_entries (AVLTree *tree)
	Retrieve the number of entries in the tree. More...

Detailed Description

Balanced binary tree.

The AVL tree structure is a balanced binary tree which stores a collection of nodes (see AVLTreeNode). Each node has a key and a value associated with it. The nodes are sorted within the tree based on the order of their keys. Modifications to the tree are constructed such that the tree remains balanced at all times (there are always roughly equal numbers of nodes on either side of the tree).

Balanced binary trees have several uses. They can be used as a mapping (searching for a value based on its key), or as a set of keys which is always ordered.

To create a new AVL tree, use avl_tree_new. To destroy an AVL tree, use avl_tree_free.

To insert a new key-value pair into an AVL tree, use avl_tree_insert. To remove an entry from an AVL tree, use avl_tree_remove or avl_tree_remove_node.

To search an AVL tree, use avl_tree_lookup or avl_tree_lookup_node.

Tree nodes can be queried using the avl_tree_node_child, avl_tree_node_parent, avl_tree_node_key and avl_tree_node_value functions.

Definition in file avl-tree.h.

Macro Definition Documentation

◆ AVL_TREE_NULL

#define AVL_TREE_NULL ((void *) 0)

A null AVLTreeValue.

Definition at line 86 of file avl-tree.h.

Typedef Documentation

◆ AVLTree

typedef struct _AVLTree AVLTree

An AVL tree balanced binary tree.

See also: avl_tree_new

Definition at line 1 of file avl-tree.h.

◆ AVLTreeCompareFunc

typedef int(* AVLTreeCompareFunc) (AVLTreeValue value1, AVLTreeValue value2)

Type of function used to compare keys in an AVL tree.

Parameters

value1	The first key.
value2	The second key.

Returns: A negative number if value1 should be sorted before value2, a positive number if value2 should be sorted before value1, zero if the two keys are equal.

Definition at line 119 of file avl-tree.h.

◆ AVLTreeKey

typedef void* AVLTreeKey

A key for an AVLTree.

Definition at line 73 of file avl-tree.h.

◆ AVLTreeNode

typedef struct _AVLTreeNode AVLTreeNode

A node in an AVL tree.

See also: avl_tree_node_left_child; avl_tree_node_right_child; avl_tree_node_parent; avl_tree_node_key; avl_tree_node_value

Definition at line 79 of file avl-tree.h.

◆ AVLTreeValue

typedef void* AVLTreeValue

A value stored in an AVLTree.

Definition at line 79 of file avl-tree.h.

Enumeration Type Documentation

◆ AVLTreeNodeSide

enum AVLTreeNodeSide

An AVLTreeNode can have left and right children.

Enumerator
AVL_TREE_NODE_LEFT
AVL_TREE_NODE_RIGHT

Definition at line 103 of file avl-tree.h.

              {
     AVL_TREE_NODE_LEFT = 0,
     AVL_TREE_NODE_RIGHT = 1
 } AVLTreeNodeSide;

Function Documentation

◆ avl_tree_free()

void avl_tree_free ( AVLTree * tree )

Destroy an AVL tree.

Parameters

tree	The tree to destroy.

◆ avl_tree_insert()

AVLTreeNode* avl_tree_insert	(	AVLTree *	tree,
		AVLTreeKey	key,
		AVLTreeValue	value
	)

Insert a new key-value pair into an AVL tree.

Parameters

tree	The tree.
key	The key to insert.
value	The value to insert.

Returns: The newly created tree node containing the key and value, or NULL if it was not possible to allocate the new memory.

◆ avl_tree_lookup()

AVLTreeValue avl_tree_lookup	(	AVLTree *	tree,
		AVLTreeKey	key
	)

Search an AVL tree for a value corresponding to a particular key.

This uses the tree as a mapping. Note that this performs identically to avl_tree_lookup_node, except that the value at the node is returned rather than the node itself.

Parameters

tree	The AVL tree to search.
key	The key to search for.

Returns: The value associated with the given key, or AVL_TREE_NULL if no entry with the given key is found.

◆ avl_tree_lookup_node()

AVLTreeNode* avl_tree_lookup_node	(	AVLTree *	tree,
		AVLTreeKey	key
	)

Search an AVL tree for a node with a particular key.

This uses the tree as a mapping.

Parameters

tree	The AVL tree to search.
key	The key to search for.

Returns: The tree node containing the given key, or NULL if no entry with the given key is found.

◆ avl_tree_new()

AVLTree* avl_tree_new ( AVLTreeCompareFunc compare_func )

Create a new AVL tree.

Parameters

compare_func Function to use when comparing keys in the tree.

Returns: A new AVL tree, or NULL if it was not possible to allocate the memory.

◆ avl_tree_node_child()

AVLTreeNode* avl_tree_node_child	(	AVLTreeNode *	node,
		AVLTreeNodeSide	side
	)

Find the child of a given tree node.

Parameters

node	The tree node.
side	Which child node to get (left or right)

Returns: The child of the tree node, or NULL if the node has no child on the given side.

◆ avl_tree_node_key()

AVLTreeKey avl_tree_node_key ( AVLTreeNode * node )

Retrieve the key for a given tree node.

Parameters

node	The tree node.

Returns: The key to the given node.

◆ avl_tree_node_parent()

AVLTreeNode* avl_tree_node_parent ( AVLTreeNode * node )

Find the parent node of a given tree node.

Parameters

node	The tree node.

Returns: The parent node of the tree node, or NULL if this is the root node.

◆ avl_tree_node_value()

AVLTreeValue avl_tree_node_value ( AVLTreeNode * node )

Retrieve the value at a given tree node.

Parameters

node	The tree node.

Returns: The value at the given node.

◆ avl_tree_num_entries()

int avl_tree_num_entries ( AVLTree * tree )

Retrieve the number of entries in the tree.

Parameters

tree The tree.

Returns: The number of key-value pairs stored in the tree.

◆ avl_tree_remove()

int avl_tree_remove	(	AVLTree *	tree,
		AVLTreeKey	key
	)

Remove an entry from a tree, specifying the key of the node to remove.

Parameters

tree	The tree.
key	The key of the node to remove.

Returns: Zero (false) if no node with the specified key was found in the tree, non-zero (true) if a node with the specified key was removed.

◆ avl_tree_remove_node()

void avl_tree_remove_node	(	AVLTree *	tree,
		AVLTreeNode *	node
	)

Remove a node from a tree.

Parameters

tree	The tree.
node	The node to remove

◆ avl_tree_root_node()

AVLTreeNode* avl_tree_root_node ( AVLTree * tree )

Find the root node of a tree.

Parameters

tree The tree.

Returns: The root node of the tree, or NULL if the tree is empty.

◆ avl_tree_subtree_height()

int avl_tree_subtree_height ( AVLTreeNode * node )

Find the height of a subtree.

Parameters

node	The root node of the subtree.

Returns: The height of the subtree.

◆ avl_tree_to_array()

AVLTreeValue* avl_tree_to_array ( AVLTree * tree )

Convert the keys in an AVL tree into a C array.

This allows the tree to be used as an ordered set.

Parameters

tree The tree.

Returns: A newly allocated C array containing all the keys in the tree, in order. The length of the array is equal to the number of entries in the tree (see avl_tree_num_entries).

Macros

Typedefs

Enumerations

Functions

Detailed Description

Macro Definition Documentation

◆ AVL_TREE_NULL

Typedef Documentation

◆ AVLTree

◆ AVLTreeCompareFunc

◆ AVLTreeKey

◆ AVLTreeNode

◆ AVLTreeValue

Enumeration Type Documentation

◆ AVLTreeNodeSide

Function Documentation

◆ avl_tree_free()

◆ avl_tree_insert()

◆ avl_tree_lookup()

◆ avl_tree_lookup_node()

◆ avl_tree_new()

◆ avl_tree_node_child()

◆ avl_tree_node_key()

◆ avl_tree_node_parent()

◆ avl_tree_node_value()

◆ avl_tree_num_entries()

◆ avl_tree_remove()

◆ avl_tree_remove_node()

◆ avl_tree_root_node()

◆ avl_tree_subtree_height()

◆ avl_tree_to_array()