The AVLTREE implementation of LibDS is a true type AVL Tree (i.e. it supports all operations in 1.44*log n time). It currently supports storage of void pointers and no duplicate values. You can store duplicates by managing that yourself. It supports any type of key on which the comparison operators "greater than", "smaller than" and "equal to" can be applied. Key versatility is achieved by using a user-supplied comparison function. The tree uses string keys of variable length, and strcmp() per default. The tree can store pointers to keys, or make own copies, which can be useful in certain cases, such as when filling with data from the same dynamic pool.
This implementation keeps all data in virtual memory.
Makes a default AVL tree. Uses variable length C-strings as keys and strcmp() as compare function. This one is likely to be used the most.
AVLTREE avlNewTree(AVLKEYCOMPFUN f,int copy_keys,int key_size)
Makes an AVLTREE with f as comparison function. It has the type
AVLKEYCOMPFUN,
which is defined as int (*AVLKEYCOMPFUN)(DSKEY,DSKEY). The argument
copy_keys
instruct LibDS to make copies of the keys and use those instead of the
pointers to the keys you pass it. It is useful in case where the pointer
you pass is always the same but the values it contains are different. If
LibDS needs to copy the keys and unless the keys are simple C-strings (i.e.
NULL-terminated strings) (in which case LibDS can determine the size of
the key itself), then key_size must be set to the actual size of
the keys. Copying keys is not necessary if the key pointers are never the
same.
Closes the given tree. This effectively means that all the nodes and the memory associated with them is released. If keys have been copied, then they are freed here as well. The data stored with each node is not touched.
void avlCloseWithFunction(AVLTREE tr, void (*fun)(void*))
Closes the tree. The effect is the same as avlClose(), only this time as each node is visited to be freed, the function fun will be applied to the data stored in the node. By passing your own version of fun you can do things with the data before the tree is closed.
NOTE: the order in which the nodes are visited is undefined (i.e. it might be pre-,post- or in-order). The idea is to use avlCloseWithFunction() only for cleaning up purposes where the exact order in which the nodes are visited is not important.
Adds the data to the tree tr. The data has the key key.
Both functions return -1 on failure, which only happens when a duplicate
key has been found. If the key was not found in the tree, then a
new node holding the data is added to the tree. On success 0 is returned.
Adding an item sets the currency of the tree to the position in the
tree where the newly created item has been inserted.
Removes the data with the given key. If the key is found, then the actual
data is returned. If the key is not found (i.e. no such item is present
in the tree), NULL is returned.
Removing does not change the currency of the tree, unless the
item that was removed was the current item. In this case the currency is
lost.
void * avlCut(AVLTREE tr)
Removes the current element from the tree. Returns the data stored with that element. If no current element is present, this function fails. Upon failure, NULL is returned. The currency in the tree is lost, just as with avlRemove() above.
The functionality to retrieve data from the tree is quite extensive. Whenever void* is returned, it will contain the data requested, or NULL if the data was not found (i.e. the tree did not contain that item).
NOTE: storing NULL in the tree will return NULL whenever that item is requested. Whether or not that is an error will not be immediately obvious.
void* avlFind(AVLTREE tr,const DSKEY key)
Find the data with the given key and returns it. The currency of the tree is set to this data item.
void* avlFirst(AVLTREE tr)
void* avlMinimum(AVLTREE tr)
Returns the first item in the tree. The currency is set to the first item in the tree if present.
void* avlLast(AVLTREE tr)
void* avlMaximum(AVLTREE tr)
Returns the last item in the tree. The currency is set to the last item in the tree if present.
void* avlNext(AVLTREE tr)
Returns the next item in the tree. "Next" is defined as the item after the current item in alphabetical order. By convention, if there's no current item, the first item in the tree is returned.
void* avlPrev(AVLTREE tr)
Returns the previous item in the tree. "Previous" is defined as the item before the current item in alphabetical order. By convention, if there's no current item, the last item in the tree is returned.
void* avlCurrent(AVLTREE tr)
Returns the current item in the tree. If no item is current, NULL is returned.
int avlSetCurrent(AVLTREE tr,const DSKEY key)
Sets the item that matches the given key as the current item in the tree. If no such item was found the currency remains unchanged and -1 is returned to indicate failure, otherwise 0 is returned to indicate success.
void avlClearCurrent(AVLTREE tr)
Clears the current item in the tree. When this function returns the
tree has no current item. This function always succeeds.
This function returns the height of the tree (its
depth in fact). Since the tree is an AVL tree the depth should be no larger
than
1.44 log n (n being the total number
of nodes in the tree).
int avlTotalNodes(AVLTREE tr)
int avlSize(AVLTREE tr)
Returns the total number of nodes currently in the tree.
int avlCheck(AVLTREE tr)
This one performs a basic check to see if the tree still conforms to the AVL properties, which are that given a node in the tree, the heights of its left and right children should not differ by more that one, and both children are themselves also AVL trees. The function exits the program with some statistics about the errors found. I can't see why you would want to run this function, unless you want to double-check that this implementation does actually conform to the AVL properties.
There's a few functions that allow sequential access to all the nodes in the tree.
void avlWalk(AVLTREE tr,void (*fun)(void *),int type)
This function performs a walk on the tree, calling
the function fun at each node with that node's data as argument.
If type is
AVLInWalk, then the walk is an in-order walk of the tree.
If type is AVLPreWalk, the walk is a pre-order walk,
and if type is AVLPostWalk, then the walk is a post-order
walk.
void avlWalkAscending(AVLTREE tr,void (*fun)(void *))
This function visits all the nodes in the tree
according to their lexicographical order, starting at the lowest key. The
function
fun is called at each node with the node's
data as argument. Note that you can do the same as follows:
for (data = avlFirst(tr); data; data = avlNext(tr))
process(data);
void avlWalkDescending(AVLTREE tr,void (*fun)(void *))
This function does the same as avlWalkAscending(), but starts at the highest key and works its way down to the lowest. The same effect can be achieved through:
for (data = avlLast(tr); data; data = avlPrev(tr))
process(data);
void* avlUpdateData(AVLTREE tr,DSKEY key,void *new_data)
This function finds the data item identified by
the key argument and replaces it with the new data given. The old data
is returned, unless the key was not found in the tree, in which case NULL
is returned.
There's a whole family of functions that work on AVLNODEs instead
of the data in the tree, but I advise you not to use them even though they
do the same things as the functions given above. I can't think of a reason
why they should be exported at all. In any case, I won't document them
here.
Wed Jun 8 10:10:46 CEST 2005