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

AVLTreeavl_tree_new (AVLTreeCompareFunc compare_func)
 Create a new AVL tree.
void avl_tree_free (AVLTree *tree)
 Destroy an AVL tree.
AVLTreeNodeavl_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.
AVLTreeNodeavl_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.
AVLTreeNodeavl_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.
AVLTreeNodeavl_tree_node_child (AVLTreeNode *node, AVLTreeNodeSide side)
 Find the child of a given tree node.
AVLTreeNodeavl_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.
AVLTreeValueavl_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).


Generated on Sun Sep 14 03:08:02 2008 for C Algorithms by  doxygen 1.5.5