The LevAWC Project
 All Data Structures Files Functions Variables Typedefs Enumerations Macros Pages
Macros | Typedefs | Functions
avltree.h File Reference
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <assert.h>

Go to the source code of this file.

Macros

#define AVL_LFT_HEAVY   1
 
#define AVL_BALANCED   0
 
#define AVL_RGT_HEAVY   -1
 

Typedefs

typedef struct AvlTreeNode_ * AvlTreeNode
 
typedef struct AvlTree_ * AvlTree
 

Functions

AvlTree AVLTREEinit (int(*compare)(const void *key1, const void *key2), void(*destroy)(void *data))
 
void AVLTREEdestroy (AvlTree tree)
 
int AVLTREEinsert (AvlTree tree, const void *data)
 
int AVLTREEremove (AvlTree tree, const void *data)
 
int AVLTREElookup (AvlTree tree, void **data)
 
int AVLTREEsize (AvlTree tree)
 
AvlTreeNode AVLTREEroot (AvlTree tree)
 
int AVLTREEis_eob (AvlTreeNode node)
 
int AVLTREEis_leaf (AvlTreeNode node)
 
void * AVLTREEdata (AvlTreeNode node)
 
AvlTreeNode AVLTREEleft (AvlTreeNode node)
 
AvlTreeNode AVLTREEright (AvlTreeNode node)
 
int AVLTREEheight (AvlTree tree)
 
void AVLTREEprint (AvlTree tree, void(*callback)(const void *data))
 
void AVLTREEpreorder (AvlTree tree, void(*callback)(const void *data))
 
void AVLTREEinorder (AvlTree tree, void(*callback)(const void *data))
 
void AVLTREEpostorder (AvlTree tree, void(*callback)(const void *data))
 

Macro Definition Documentation

#define AVL_BALANCED   0

Balance factor for a "balanced" node - in the AVL Tree

Definition at line 43 of file avltree.h.

#define AVL_LFT_HEAVY   1

Balance factor for a "left-heavy" node - in the AVL Tree

Definition at line 38 of file avltree.h.

#define AVL_RGT_HEAVY   -1

Balance factor for a "right-heavy" node - in the AVL Tree

Definition at line 48 of file avltree.h.

Typedef Documentation

typedef struct AvlTree_* AvlTree

Use a typedef - to hide the interior of AvlTree_ - in the implementation file. This is how data hiding can be done in C.

Definition at line 62 of file avltree.h.

typedef struct AvlTreeNode_* AvlTreeNode

Use a typedef - to hide the interior of AvlTreeNode_ - in the implementation file. This is how data hiding can be done in C.

Definition at line 55 of file avltree.h.

Function Documentation

void* AVLTREEdata ( AvlTreeNode  node)

Get a reference to node data

Parameters
[in]node- reference to current node
Returns
Generic reference to node data.

Definition at line 129 of file avltree.c.

void AVLTREEdestroy ( AvlTree  tree)

Destroy the tree

The tree is destroyed - that is, all dynamically allocated memory occupied by the elements - will be destroyed. It is the user-defined callback function destroy, given as an argument to AVLTREEinit(), that is responsible for freeing dynamically allocated element data, when this function is called. If, on the other hand, destroy is set to NULL when AVLTREEinit() is called, all element data will be left untouched after the tree is dismounted and destroyed. When all elements and data have been deallocated - the rest of the tree is freed, too.

Parameters
[in]tree- a reference to current tree.
Returns
Nothing.
See Also
AVLTREEinit()

Definition at line 86 of file avltree.c.

int AVLTREEheight ( AvlTree  tree)

Get the tree height(=nr of levels).

Parameters
[in]tree- reference to current tree
Returns
Tree height - i.e. the max. number of levels in the tree.

Definition at line 144 of file avltree.c.

AvlTree AVLTREEinit ( int(*)(const void *key1, const void *key2)  compare,
void(*)(void *data)  destroy 
)

Initialize the tree

Parameters
[in]compare- a reference to a user-defined function, responsible for comparing node data. This callback function should return a value of -1 if data referenced by key1 is less than data referenced by key2 - or 0 if they are equal - or 1 otherwise. The purpose of this function is to implement node data searching - which is part of functions like AVLTREEinsert(), AVLTREElookup() and AVLTREEremove().
[in]destroy- a reference to a user-defined function, reponsible for freeing node data, when the tree is destroyed. If destroy is set to NULL - then node data will be left untouched upon tree destruction.
Returns
A reference - to a new, empty tree - if dynamic memory allocation for the ADT was successful - or NULL otherwise. Take really good care of this return value, since it will be needed as a parameter in subsequent calls - to the majority of other tree functions in this function interface - i.e. a sort of "handle" to the tree.

Definition at line 71 of file avltree.c.

void AVLTREEinorder ( AvlTree  tree,
void(*)(const void *data)  callback 
)

Traverse the entire tree - in inorder.

Inorder traversal means the following, where recursion is obvious:

As long as we are visiting a valid(=not NULL) node - do:

  1. First - goto the left subtree of the root node - and traverse this subtree in inorder...
  2. ..visit the root node...
  3. ..and finally goto the right subtree - and traverse this subtree, too - in inorder.
Parameters
[in]tree- reference to current tree.
[in]callback- reference to user-defined callback function, that gets read access to element data via its parameter data - to do whatever is relevant. In could be a matter of formatting data for printing on screen, for example.
Returns
Nothing.

Definition at line 161 of file avltree.c.

int AVLTREEinsert ( AvlTree  tree,
const void *  data 
)

Insert a new node, together with data into the tree.

In case a node with data equal to what is referenced by parameter data already exists, the function returns with a value of 1. If not, a new node is created to hold data referenced by parameter data - and this node is inserted according to the rules for a binary search tree - that is, at any given node - all nodes in the left subtree hold data less than data of the new node - and all nodes of the right subtree has data larger than that of the new node. This navigation to find the appropriate place for the new node is accomplished by recursive calls. After the new node is inserted, the balance of ancestor nodes may have been altered. This is checked on the way up through the recursive calls, and adjusted through rotations if the imbalance is reaching (+/-)2 levels at a particular node. The end result is an almost evenly balanced tree when the recursion has unwinded all the way up to the root node.

Parameters
[in]tree- reference to current tree.
[in]data- reference to data to be inserted within the new node. It is the responsability of the caller to ensure, that this memory is valid as long as it is present in the tree.
Returns
Value 0 if insertion was successful.
Value 1, if data already exists in the tree.
Value -1, indicates fatal error.

Definition at line 92 of file avltree.c.

int AVLTREEis_eob ( AvlTreeNode  node)

p Determines whether the parameter node is NULL - i.e. "end-of-branch" - or not

Parameters
[in]node- the node to be tested
Returns
Value 1 if node is the end of a branch in the tree - or 0 otherwise.

Definition at line 119 of file avltree.c.

int AVLTREEis_leaf ( AvlTreeNode  node)

Determines if the the parameter node is a leaf node, i.e. lacks children - or not

Parameters
[in]node- the node to be tested
Returns
Value 1 if node is a leaf - or 0 otherwise.

Definition at line 124 of file avltree.c.

AvlTreeNode AVLTREEleft ( AvlTreeNode  node)

Get a reference to left child node.

Parameters
[in]node- reference to current node
Returns
A reference to left child of parameter node.

Definition at line 134 of file avltree.c.

int AVLTREElookup ( AvlTree  tree,
void **  data 
)

Lookup data in the tree - without removing it.

Determines whether a node, with key data matching the data referenced by the parameter data - is present in the current tree. This 2nd parameter, data, should reference an (external, user-defined) pointer, that points to the search key data. After the call - this referenced, external pointer has been redirected by this function, to point to the data of the node hit - if the call was succesful.

Parameters
[in]tree- reference to current tree.
[in,out]data- a reference to an external pointer, pointing at the data to be searched for - at the call. Upon return - this pointer has been redirected by this function - and points instead to data contained in the node hit - if any.
Returns
Value 0 - if call was successful.
Value -1, if searched node not found.

Definition at line 104 of file avltree.c.

void AVLTREEpostorder ( AvlTree  tree,
void(*)(const void *data)  callback 
)

Traverse the entire tree - in postorder.

Postorder traversal means the following, where recursion is obvious:

As long as we are visiting a valid(=not NULL) node - do:

  1. First - goto the left subtree of the root node - and traverse this subtree in postorder...
  2. ..then goto the right subtree of the root node - and traverse this subtree in postorder...
  3. ..and finally - visit the root node.
    Parameters
    [in]tree- reference to current tree.
    [in]callback- reference to user-defined callback function, that gets read access to element data via its parameter data - to do whatever is relevant. In could be a matter of formatting data for printing on screen, for example.
    Returns
    Nothing.

Definition at line 166 of file avltree.c.

void AVLTREEpreorder ( AvlTree  tree,
void(*)(const void *data)  callback 
)

Traverse the entire tree - in preorder.

Preorder traversal means the following, where recursion is obvious:

As long as we are visiting a valid(=not NULL) node - do:

  1. First - visit the root node...
  2. ..then goto the left subtree of the root node - and traverse this subtree in preorder...
  3. ..and finally goto the right subtree - and traverse this subtree, too - in preorder.
Parameters
[in]tree- reference to current tree.
[in]callback- reference to user-defined callback function, that gets read access to element data via its parameter data - to do whatever is relevant. In could be a matter of formatting data for printing on screen, for example.
Returns
Nothing.

Definition at line 156 of file avltree.c.

void AVLTREEprint ( AvlTree  tree,
void(*)(const void *data)  callback 
)

Print all tree nodes, with their data, on screen.

Parameters
[in]tree- reference to current tree.
[in]callback- reference to user-defined callback function, that gets read access to element data via its parameter data - to do whatever is relevant. In this case it is a matter of formatting data for printing on screen. The printed data should be kept to a minimum (the key value, for example) in order not to clutter the screen. This function is primarily for small trees - and educational/debugging purposes.
Returns
Nothing.

Definition at line 149 of file avltree.c.

int AVLTREEremove ( AvlTree  tree,
const void *  data 
)

Remove/Hide a node - together with its data from the tree.

Removal of a node is implemented as a kind of lazy removal - where a node, if found in the tree, is not physically removed - just hidden. This means, that data in the tree must remain valid even after it is removed. Consequently, the size of the tree does not decrease after removal.

Pros: Simpler, the tree structure is maintained after removal, no rebalancing needed..
Cons: The tree has a certain amount of redundant data, occupied by all hidden nodes. If removals are frequent and numreous, another removal strategy(=physical removal), might be preferred..

Returns
Value 0 - if call was successful.
Value -1, if searched node not found.

Definition at line 99 of file avltree.c.

AvlTreeNode AVLTREEright ( AvlTreeNode  node)

Get a reference to right child node.

Parameters
[in]node- reference to current node
Returns
A reference to right child of parameter node.

Definition at line 139 of file avltree.c.

AvlTreeNode AVLTREEroot ( AvlTree  tree)

Get a reference to the root node of the tree

Parameters
[in]tree- a reference to the current tree
Returns
A reference to the root node of the tree.

Definition at line 114 of file avltree.c.

int AVLTREEsize ( AvlTree  tree)

Get the size of the tree

Parameters
[in]tree- a reference to the current tree
Returns
The size, i.e. the number of nodes in the tree.

Definition at line 109 of file avltree.c.

Generated on Tue Apr 7 2015 09:01:12 for The LevAWC Project by   doxygen 1.8.2