avl-tree.h File Reference

Balanced binary tree. More...

Defines
#define	AVL_TREE_NULL   ((void *) 0)
	A null AVLTreeValue.
Typedefs
typedef struct _AVLTree	AVLTree
	An AVL tree balanced binary tree.
typedef void *	AVLTreeKey
	A key for an AVLTree.
typedef void *	AVLTreeValue
	A value stored in an AVLTree.
typedef struct _AVLTreeNode	AVLTreeNode
	A node in an AVL tree.
typedef int(*	AVLTreeCompareFunc )(AVLTreeValue value1, AVLTreeValue value2)
	Type of function used to compare keys in an AVL tree.
Enumerations
enum	AVLTreeNodeSide
	An AVLTreeNode can have left and right children.
Functions
AVLTree *	avl_tree_new (AVLTreeCompareFunc compare_func)
	Create a new AVL tree.
void	avl_tree_free (AVLTree *tree)
	Destroy an AVL tree.
AVLTreeNode *	avl_tree_insert (AVLTree *tree, AVLTreeKey key, AVLTreeValue value)
	Insert a new key-value pair into an AVL tree.
void	avl_tree_remove_node (AVLTree *tree, AVLTreeNode *node)
	Remove a node from a tree.
int	avl_tree_remove (AVLTree *tree, AVLTreeKey key)
	Remove an entry from a tree, specifying the key of the node to remove.
AVLTreeNode *	avl_tree_lookup_node (AVLTree *tree, AVLTreeKey key)
	Search an AVL tree for a node with a particular key.
AVLTreeValue	avl_tree_lookup (AVLTree *tree, AVLTreeKey key)
	Search an AVL tree for a value corresponding to a particular key.
AVLTreeNode *	avl_tree_root_node (AVLTree *tree)
	Find the root node of a tree.
AVLTreeKey	avl_tree_node_key (AVLTreeNode *node)
	Retrieve the key for a given tree node.
AVLTreeValue	avl_tree_node_value (AVLTreeNode *node)
	Retrieve the value at a given tree node.
AVLTreeNode *	avl_tree_node_child (AVLTreeNode *node, AVLTreeNodeSide side)
	Find the child of a given tree node.
AVLTreeNode *	avl_tree_node_parent (AVLTreeNode *node)
	Find the parent node of a given tree node.
int	avl_tree_subtree_height (AVLTreeNode *node)
	Find the height of a subtree.
AVLTreeValue *	avl_tree_to_array (AVLTree *tree)
	Convert the keys in an AVL tree into a C array.
int	avl_tree_num_entries (AVLTree *tree)
	Retrieve the number of entries in the tree.

---

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.

---

Typedef Documentation

typedef struct _AVLTree AVLTree

An AVL tree balanced binary tree.

See also:

avl_tree_new

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.

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

---

Function Documentation

void avl_tree_free

(

AVLTree *

tree

)

Destroy an AVL tree.

Parameters:

tree

The tree to destroy.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

void avl_tree_remove_node	(	AVLTree *	tree,
		AVLTreeNode *	node
	)

Remove a node from a tree.

Parameters:

	tree	The tree.
	node	The node to remove

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.

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.

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).