LibRCG  3.1.1
treemap.h File Reference

Implementation of an AVL tree (self-balancing binary search tree). More...

Go to the source code of this file.

Data Structures

struct  STreeNode
 Tree node structure. More...
 
struct  STreeMap
 Tree structure. More...
 

Typedefs

typedef STreeNodeTreeNode
 Tree node definition. More...
 
typedef STreeMapTreeMap
 Tree definition. More...
 

Enumerations

enum  BFactor { L, E, R }
 Type that defines the balance factor of a tree. More...
 

Functions

TreeMap newTree (int(*keyComp)(void *, void *))
 Creates a tree. More...
 
int treeSetKComp (TreeMap tree, int(*keyComp)(void *, void *))
 Sets the comparison function of this tree. More...
 
void treeDelete (TreeMap tree)
 Deletes a tree. More...
 
int treeInsert (TreeMap tree, void *key, void *value, int replace)
 Associates a value to a key in a tree. More...
 
int treeRemove (TreeMap tree, void *key, void **value, void(*del)(void *))
 Removes the mapping for a key from a tree. More...
 
int treeGet (TreeMap tree, void *key, void **value)
 Provides the mapping for a key from a tree. More...
 
int treeIsBalanced (TreeMap tree)
 Checks if a tree is balanced. More...
 
int treeHeight (TreeMap tree)
 Returns the height of a tree. More...
 
int treeSize (TreeMap tree)
 Returns the number of elements present in a tree. More...
 
int treeInOrder (TreeMap tree, void(*fun)(void *, void *))
 Applies a function to the elements of an tree (inorder traversal). More...
 
int treePreOrder (TreeMap tree, void(*fun)(void *, void *))
 Applies a function to the elements of an tree (preorder traversal). More...
 
int treePostOrder (TreeMap tree, void(*fun)(void *, void *))
 Applies a function to the elements of an tree (postorder traversal). More...
 
Iterator treeKeys (TreeMap tree)
 Creates an iterator from the keys of a tree. More...
 
Iterator treeValues (TreeMap tree)
 Creates an iterator from the values of a tree. More...
 

Detailed Description

Implementation of an AVL tree (self-balancing binary search tree).

Provides functions to create and manipulate an AVL tree.

To use this tree you have to provide the following function for the date type used for keys:

int keyComp(void* key1,void* key2) Compares two keys (used by treeInsert, treeRemove, and treeGet). It should return 0 if key1 is equal to key2, a value less than 0 if key1 is less than key2, and a value greater than 0 if key1 is greater than 0. This function can be changed using function treeSetKComp.

int keyComp(void* key1,void* key2)
{
if(key1&&key2) return strcmp((char*)key1,(char*)key2);
else return 0;
}
Author
Rui Carlos Gonçalves
Version
3.0
Date
07/2012

Definition in file treemap.h.

Typedef Documentation

typedef STreeMap* TreeMap

Tree definition.

Definition at line 80 of file treemap.h.

typedef STreeNode* TreeNode

Tree node definition.

Definition at line 62 of file treemap.h.

Enumeration Type Documentation

enum BFactor

Type that defines the balance factor of a tree.

Definition at line 38 of file treemap.h.

Function Documentation

TreeMap newTree ( int(*)(void *, void *)  keyComp)

Creates a tree.

Parameters
keyCompthe comparison function
Returns
NULL if an error occurred
the new tree otherwise

Definition at line 273 of file treemap.c.

void treeDelete ( TreeMap  tree)

Deletes a tree.

Attention
This function only free the memory used by the tree. It does not free the memory used by elements the tree contains.
Parameters
treethe tree to be deleted

Definition at line 318 of file treemap.c.

int treeGet ( TreeMap  tree,
void *  key,
void **  value 
)

Provides the mapping for a key from a tree.

If there is no mapping for the specified key, it will be put the value NULL at value. However, the NULL value may also say that the mapping for the specified key was NULL. Check the returned value in order to know whether the key was in the tree.

Attention
This function puts at value a pointer to the mapping of the specified key. Changes to this value will affect the value in the tree.
Parameters
treethe tree
keykey whose mapping is to be provided
valuepointer where the mapping value will be put
Returns
0 if there was a mapping for the specified key
1 otherwise

Definition at line 550 of file treemap.c.

int treeHeight ( TreeMap  tree)

Returns the height of a tree.

Parameters
treethe tree
Returns
the height of the tree

Definition at line 622 of file treemap.c.

int treeInOrder ( TreeMap  tree,
void(*)(void *, void *)  fun 
)

Applies a function to the elements of an tree (inorder traversal).

The function to be applied must be of type void fun(void*,void*).

Parameters
treethe tree
funthe function to be applied
Returns
0 if the array was not empty
1 otherwise

Definition at line 654 of file treemap.c.

int treeInsert ( TreeMap  tree,
void *  key,
void *  value,
int  replace 
)

Associates a value to a key in a tree.

If the key already had a value, the replace argument specifies whether the new element should be added (it will be added only if replace!=0).

Parameters
treethe tree
keythe key
valuethe value to be inserted
replacespecifies whether an old value shall be replaced
Returns
0 if the value was inserted
1 if the key already had a value
2 if an error occurred

Definition at line 413 of file treemap.c.

int treeIsBalanced ( TreeMap  tree)

Checks if a tree is balanced.

A tree is balanced if, for each node of the tree, the difference between the height of the left subtree and the height of right subtree is not greater than 1.

Parameters
treethe tree
Returns
0 if the tree is not balanced
1 otherwise

Definition at line 593 of file treemap.c.

Iterator treeKeys ( TreeMap  tree)

Creates an iterator from the keys of a tree.

See Also
Iterator
Parameters
treethe tree
Returns
NULL if an error occurred
the iterator otherwise

Definition at line 745 of file treemap.c.

int treePostOrder ( TreeMap  tree,
void(*)(void *, void *)  fun 
)

Applies a function to the elements of an tree (postorder traversal).

The function to be applied must be of type void fun(void*,void*).

Parameters
treethe tree
funthe function to be applied
Returns
0 if the array was not empty
1 otherwise

Definition at line 711 of file treemap.c.

int treePreOrder ( TreeMap  tree,
void(*)(void *, void *)  fun 
)

Applies a function to the elements of an tree (preorder traversal).

The function to be applied must be of type void fun(void*,void*).

Parameters
treethe tree
funthe function to be applied
Returns
0 if the array was not empty
1 otherwise

Definition at line 683 of file treemap.c.

int treeRemove ( TreeMap  tree,
void *  key,
void **  value,
void(*)(void *)  del 
)

Removes the mapping for a key from a tree.

Provides the value of the removed element if the value of elem is not NULL.

Attention
This function does not free the memory used by the removed element. To free the memory used by its key, you have to provide the argument del.
Parameters
treethe tree
keykey whose mapping is to be removed
valuepointer where the removed element shall be put (or NULL)
delfunction to free the memory used by the key (or NULL)
Returns
0 if an element was removed from the specified position
1 otherwise

Definition at line 539 of file treemap.c.

int treeSetKComp ( TreeMap  tree,
int(*)(void *, void *)  keyComp 
)

Sets the comparison function of this tree.

Parameters
treethe tree
keyCompthe new comparison function
Returns
1 if keyComp was equal to NULL (no change was made)
0 otherwise

Definition at line 291 of file treemap.c.

int treeSize ( TreeMap  tree)

Returns the number of elements present in a tree.

Parameters
treethe tree
Returns
the number of elements present in the tree.

Definition at line 629 of file treemap.c.

Iterator treeValues ( TreeMap  tree)

Creates an iterator from the values of a tree.

See Also
Iterator
Parameters
treethe tree
Returns
NULL if an error occurred
the iterator otherwise

Definition at line 783 of file treemap.c.

LibRCG © 2004-2015   Rui Carlos Gonçalves