LibDS: AVL TREE

AVL TREE

Here's the most authoritative documentation on the AVL Tree implementation used in LibDS. Ignore any other files that might claim the same.

Introduction

An AVL tree is a data structure that is very well suited to storing data that supports ordering, such as names, or other miscellaneous things. Due to the fact that it is a balanced tree, very fast access to the data is supported, including inserting, deleting, finding, determining the next, previous, smallest and largest value, etc... Should you wish to learn more, a host of books on data structures discuss these and other sundry features of binary trees, as well as provide some rigorous proofs of the properties.

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.

Initialization

AVLTREE avlMake(void)

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.

Closing

void avlClose(AVLTREE tr)

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.

Adding

int avlAdd(AVLTREE tr,const DSKEY key,void *data)
int avlInsert(AVLTREE tr,const DSKEY key,void *data)

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.

Deleting

void* avlRemove(AVLTREE tr,const DSKEY key)

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.

Fetching

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.

Tree Parameters

int avlHeight(AVLTREE tr)

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.

Advanced functionality

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.

Obscure functionality

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.

Fri Dec 14 15:50:22 EST 2001