| avl_check | avl_insert | avl_place | avl_zap |
| avl_delete | avl_item_at_position | avl_position | fprint_avltree_mem |
| avl_find | avl_largest | avl_size | p_avl |
| avl_height | avl_nth_item | avl_smallest | p_avltree_mem |
void avl_check(Avl_node p, Ordertype (*compare) (void *, void *));Check that each node of an AVL tree has the following properties: (1) "size" and "height" fields are correct; (2) heights of the two children differ by at most 1. In addition, check that the inorder traversal of the whole tree really is in order.
Avl_node avl_delete(Avl_node p, void *item, Ordertype (*compare) (void *, void *));Delete an item from an AVL tree and return the updated tree. If the item is not in the tree (that is, if the comparison function does not return SAME_AS for any item in the tree), a fatal error occurs.
void *avl_find(Avl_node p, void *item, Ordertype (*compare) (void *, void *));Look for an item in an AVL tree. That is, look for an item for which the comparison function returns SAME_AS. If it is found, return the item in the tree; otherwise return NULL;
int avl_height(Avl_node p);Return the height of an AVL tree. Leaves have height 1.
Avl_node avl_insert(Avl_node p, void *item, Ordertype (*compare) (void *, void *));Insert an item into an AVL tree, and return the updated tree. The item is an arbitrary pointer, and the caller gives a function that takes two pointers and compares two items. The comparison function must return LESS_THAN, SAME_AS, or GREATER_THAN.
If the item is already in the tree (that is, if the comparison function return SAME_AS for any item already in the tree), a fatal error occurs.
void *avl_item_at_position(Avl_node p, double pos);Given an AVL tree and a position pos, 0.0 < pos <= 1.0, return the item at that position. If the tree is empty, or if pos is out of range, NULL is returned. The index (counting from 1) of the returned item is ceiling(pos * p->size).
void *avl_largest(Avl_node p);Return the largest (rightmost) item in an AVL tree.
void *avl_nth_item(Avl_node p, int n);Return the n-th item (counting from 1) in an AVL tree. If n is out of range, NULL is returned.
int avl_place(Avl_node p, void *item, Ordertype (*compare) (void *, void *));How far (counting from 1) from the beginning of the tree is the item. If the item is not already in the tree, this function says how far it would be if it were inserted first.
double avl_position(Avl_node p, void *item, Ordertype (*compare) (void *, void *));Return x, 0 < x <= 1, telling the position of the item in the tree. The last item always has position 1.0. The first item in a tree of size 10 has position 0.1.
int avl_size(Avl_node p);Return the number of nodes in an AVL tree.
void *avl_smallest(Avl_node p);Return the smallest (leftmost) item in an AVL tree.
void avl_zap(Avl_node p);Free an entire AVL tree. This does not affect any of the data to which the tree refers.
void fprint_avltree_mem(FILE *fp, BOOL heading);This routine prints (to FILE *fp) memory usage statistics for data types associated with the avltree package. The Boolean argument heading tells whether to print a heading on the table.
void p_avl(Avl_node p, int level);Print an AVL tree to stdout. The pointers to the items are printed as integers.
void p_avltree_mem();This routine prints (to stdout) memory usage statistics for data types associated with the avltree package.
typedef struct avl_node * Avl_node;
The items that are stored in the tree are simply pointers, which are assumed to contain the keys and data.
The caller supplies a comparison function, for example
Ordertype compare(void *v1, void *v2)
or
Ordertype compare(struct my_data *p1, struct my_data *p2)
that is assumed to return LESS_THAN, GREATER_THAN, or SAME_AS.
Aside from the ordinary "insert", "find", and "delete" operations, there is a "position" operation that tells where an item is in w.r.t. the inorder traversal of the tree, and an operation that finds the item at a given position.