Simple unoptimized AVL tree implementation in C89
This is a C89 library to provide an AVL tree implementation for when you don't have one present in your run-time system already. It emphasizes the following:
It has the following additional functionality:
It has been used in:
/* Map string names to malloc()'d blocks. */
avl_tree_t tree;
/* Cast strcmp to avoid warnings; avl_comparator_t takes two void *
arguments, strcmp wants two const char *s.
free() is used as the key destructor. */
avl_initialize(&tree, (avl_comparator_t)strcmp, free);
for(int i = 0; i < 100; i ++) {
const char *name = get_next_name();
/* avl_insert will return the old data if something already exists with
the specified key, and call the key destructor on the new key. */
avl_insert(&tree, strdup(name), malloc(sizeof(record_t)));
}
/* Can now search at will. strcmp will be used to compare keys. */
record_t *data = avl_search(&tree, "Ebenezer Scrooge");
/* Will return NULL if not found.
Also returns NULL if that's what the key maps to. */
data = avl_search(&tree, some_string());
/* Let's get rid of some things. */
/* avl_remove will call free() on the key (since we specified it as a key
destructor) but won't touch the data, it'll just return what it found
at that key, if anything, or NULL otherwise. Since free(NULL) is a
no-op...*/
free(avl_remove(&tree, "James Bond"));
free(avl_remove(&tree, "Alfred E. Neuman"));
/* Now it's time to get rid of the entire tree. The second argument is a
function to be called on each node in order to clean up what the
relevant pointers reference; we'll just use a built-in function here
that frees both the keys and the data they point to. */
avl_destroy(&tree, avl_free_data);