LibRCG  3.1.1
treemap.c File Reference

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

Go to the source code of this file.

Functions

static TreeNode leftRotate (TreeNode tree)
 Rotates a tree to left. More...
 
static TreeNode rightRotate (TreeNode tree)
 Rotates a tree to right. More...
 
static TreeNode leftBalance (TreeNode tree)
 Rebalances a tree that is balanced to the left as result of an insertion operation. More...
 
static TreeNode rightBalance (TreeNode tree)
 Rebalances a tree that is balanced to the right as result of an insertion operation. More...
 
static TreeNode rLeftBalance (TreeNode tree, int *h)
 Rebalances a tree that is balanced to the left as result of a remotion operation. More...
 
static TreeNode rRightBalance (TreeNode tree, int *h)
 Rebalances a tree that is balanced to the right as result of a remotion operation. More...
 
static TreeNode upperLeft (TreeNode tree)
 Returns the node with the greatest key on the left subtree of a tree. More...
 
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...
 
static void treeDelAux (TreeNode tree)
 Deletes a node of a tree and all of its children nodes. More...
 
void treeDelete (TreeMap tree)
 Deletes a tree. More...
 
static TreeNode treeInsAux (TreeNode tree, void *key, void *val, int replace, int *h, int(*comp)(void *, void *))
 Insertion auxiliary function. More...
 
int treeInsert (TreeMap tree, void *key, void *val, int replace)
 Associates a value to a key in a tree. More...
 
static TreeNode treeRemAux (TreeNode tree, void *key, void **value, void(*del)(void *), int *h, int(*comp)(void *, void *))
 Remotion auxiliary function. 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 treeIsBalancedAux (TreeNode tree)
 Checks if a tree is balanced. More...
 
int treeIsBalanced (TreeMap tree)
 Checks if a tree is balanced. More...
 
static int treeHightAux (TreeNode tree)
 Returns the height of a tree. 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...
 
static void treeInOAux (TreeNode tree, void(*fun)(void *, void *))
 Inorder traversal auxiliary function. More...
 
int treeInOrder (TreeMap tree, void(*fun)(void *, void *))
 Applies a function to the elements of an tree (inorder traversal). More...
 
static void treePreOrderAux (TreeNode tree, void(*fun)(void *, void *))
 Preorder traversal auxiliary function. More...
 
int treePreOrder (TreeMap tree, void(*fun)(void *, void *))
 Applies a function to the elements of an tree (preorder traversal). More...
 
static void treePostOrderAux (TreeNode tree, void(*fun)(void *, void *))
 Postorder traversal auxiliary function. More...
 
int treePostOrder (TreeMap tree, void(*fun)(void *, void *))
 Applies a function to the elements of an tree (postorder traversal). More...
 
static int treeKAux (TreeNode tree, Iterator it)
 Traverses a tree and adds the keys to an iterator. More...
 
Iterator treeKeys (TreeMap tree)
 Creates an iterator from the keys of a tree. More...
 
static int treeVAux (TreeNode tree, Iterator it)
 Traverses a tree and adds the values to an iterator. 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).

Author
Rui Carlos Gonçalves
Version
3.0
Date
07/2012

Definition in file treemap.c.

Function Documentation

static TreeNode leftBalance ( TreeNode  tree)
static

Rebalances a tree that is balanced to the left as result of an insertion operation.

Parameters
treethe root of the tree to rebalance
Returns
the new tree

Definition at line 72 of file treemap.c.

static TreeNode leftRotate ( TreeNode  tree)
static

Rotates a tree to left.

Parameters
treethe root of the tree to rotate
Returns
the new tree

Definition at line 20 of file treemap.c.

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.

static TreeNode rightBalance ( TreeNode  tree)
static

Rebalances a tree that is balanced to the right as result of an insertion operation.

Parameters
treethe root of the tree to rebalance
Returns
the new tree

Definition at line 121 of file treemap.c.

static TreeNode rightRotate ( TreeNode  tree)
static

Rotates a tree to right.

Parameters
treethe root of the tree to rotate
Returns
the new tree

Definition at line 45 of file treemap.c.

static TreeNode rLeftBalance ( TreeNode  tree,
int *  h 
)
static

Rebalances a tree that is balanced to the left as result of a remotion operation.

Parameters
treethe root of the tree to rebalance
hspecifies whether the height of the tree changed
Returns
the new tree

Definition at line 171 of file treemap.c.

static TreeNode rRightBalance ( TreeNode  tree,
int *  h 
)
static

Rebalances a tree that is balanced to the right as result of a remotion operation.

Parameters
treethe root of the tree to rebalance
hspecifies whether the height of the tree changed
Returns
the new tree

Definition at line 219 of file treemap.c.

static void treeDelAux ( TreeNode  tree)
static

Deletes a node of a tree and all of its children nodes.

Parameters
treethe tree

Definition at line 306 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.

static int treeHightAux ( TreeNode  tree)
static

Returns the height of a tree.

Parameters
treethe tree
Returns
the height of the tree

Definition at line 608 of file treemap.c.

static void treeInOAux ( TreeNode  tree,
void(*)(void *, void *)  fun 
)
static

Inorder traversal auxiliary function.

Parameters
treethe tree
funthe function to be applied

Definition at line 642 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.

static TreeNode treeInsAux ( TreeNode  tree,
void *  key,
void *  val,
int  replace,
int *  h,
int(*)(void *, void *)  comp 
)
static

Insertion auxiliary function.

Parameters
treethe tree
keythe key
valthe value to be inserted
replacespecifies whether an old value shall be replaced
hspecifies whether the height of the tree changed (h<0?), and whether an error occurred (h>0?)
compkey comparison function
Returns
new tree

Definition at line 340 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.

int treeIsBalancedAux ( TreeNode  tree)

Checks if a tree is balanced.

Parameters
treethe tree
Returns
-1 is the tree is not balanced
tree height otherwise

Definition at line 577 of file treemap.c.

static int treeKAux ( TreeNode  tree,
Iterator  it 
)
static

Traverses a tree and adds the keys to an iterator.

Parameters
treethe tree
itthe iterator
Returns
1 if an error occurred
0 otherwise

Definition at line 731 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.

static void treePostOrderAux ( TreeNode  tree,
void(*)(void *, void *)  fun 
)
static

Postorder traversal auxiliary function.

Parameters
treethe tree
funthe function to be applied

Definition at line 699 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.

static void treePreOrderAux ( TreeNode  tree,
void(*)(void *, void *)  fun 
)
static

Preorder traversal auxiliary function.

Parameters
treethe tree
funthe function to be applied

Definition at line 671 of file treemap.c.

static TreeNode treeRemAux ( TreeNode  tree,
void *  key,
void **  value,
void(*)(void *)  del,
int *  h,
int(*)(void *, void *)  comp 
)
static

Remotion auxiliary function.

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)
hspecifies whether the height of the tree changed
compkey comparison function
Returns
new tree

Definition at line 438 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.

static int treeVAux ( TreeNode  tree,
Iterator  it 
)
static

Traverses a tree and adds the values to an iterator.

Parameters
treethe tree
itthe iterator
Returns
1 if an error occurred
0 otherwise

Definition at line 769 of file treemap.c.

static TreeNode upperLeft ( TreeNode  tree)
static

Returns the node with the greatest key on the left subtree of a tree.

Parameters
treethe tree
Returns
the node with the greatest key on the left subtree of the tree

Definition at line 265 of file treemap.c.

LibRCG © 2004-2015   Rui Carlos Gonçalves