/cvmfs/atlas.cern.ch/repo/sw/ASG/AnalysisBase/2.4.30/CxxUtils/CxxUtils/libcalg/avl-tree.h File Reference

Balanced binary tree. More...

Go to the source code of this file.

Defines

#define AVL_TREE_NULL   ((void *) 0)

Typedefs

typedef struct _AVLTree AVLTree
typedef void * AVLTreeKey
typedef void * AVLTreeValue
typedef struct _AVLTreeNode AVLTreeNode
typedef int(* AVLTreeCompareFunc )(AVLTreeValue value1, AVLTreeValue value2)

Enumerations

enum  AVLTreeNodeSide { AVL_TREE_NODE_LEFT = 0, AVL_TREE_NODE_RIGHT = 1 }

Functions

AVLTree * avl_tree_new (AVLTreeCompareFunc compare_func)
void avl_tree_free (AVLTree *tree)
AVLTreeNode * avl_tree_insert (AVLTree *tree, AVLTreeKey key, AVLTreeValue value)
void avl_tree_remove_node (AVLTree *tree, AVLTreeNode *node)
int avl_tree_remove (AVLTree *tree, AVLTreeKey key)
AVLTreeNode * avl_tree_lookup_node (AVLTree *tree, AVLTreeKey key)
AVLTreeValue avl_tree_lookup (AVLTree *tree, AVLTreeKey key)
AVLTreeNode * avl_tree_root_node (AVLTree *tree)
AVLTreeKey avl_tree_node_key (AVLTreeNode *node)
AVLTreeValue avl_tree_node_value (AVLTreeNode *node)
AVLTreeNode * avl_tree_node_child (AVLTreeNode *node, AVLTreeNodeSide side)
AVLTreeNode * avl_tree_node_parent (AVLTreeNode *node)
int avl_tree_subtree_height (AVLTreeNode *node)
AVLTreeValue * avl_tree_to_array (AVLTree *tree)
int avl_tree_num_entries (AVLTree *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.

Define Documentation

#define AVL_TREE_NULL   ((void *) 0)

A null AVLTreeValue.

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 void* AVLTreeKey

A key for an AVLTree.

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
typedef void* AVLTreeValue

A value stored in an AVLTree.

Enumeration Type Documentation

enum AVLTreeNodeSide

An AVLTreeNode can have left and right children.

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).
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Generated on 15 Apr 2017 for RootCore Packages by  doxygen 1.6.1