AVL Tree Guide

This guide explains how to use the AVL Tree implementation in libmyrtx effectively.

What is an AVL Tree?

An AVL (Adelson-Velsky and Landis) tree is a self-balancing binary search tree where the difference in height between left and right subtrees (balance factor) is at most 1 for every node. This balancing ensures O(log n) complexity for search, insertion, and deletion operations.

Key features: - Self-balancing binary search tree - O(log n) complexity for search, insert, and delete operations - In-order traversal yields sorted results - Supports efficient range queries and ordered data access

When to Use an AVL Tree

AVL trees are ideal when: - You need ordered data with fast access - Your data requires frequent insertions, deletions, and look-ups - You need to efficiently find the minimum or maximum values - You need to iterate over items in sorted order

They’re particularly useful for: - Implementing ordered dictionaries - Index structures in databases - Range queries (finding all items within a range) - Maintaining sorted data with frequent modifications

Basic Usage

Creating an AVL Tree

You can create an AVL tree using the arena allocator for memory management or with standard malloc/free:

// Using arena allocator (recommended)
myrtx_arena_t arena = {0};
myrtx_arena_init(&arena, 0);
myrtx_avl_tree_t* tree = myrtx_avl_tree_create(&arena, myrtx_avl_compare_strings, NULL);

// Using malloc/free
myrtx_avl_tree_t* tree = myrtx_avl_tree_create(NULL, myrtx_avl_compare_strings, NULL);

The second parameter is a comparison function for the keys. The library provides standard comparison functions for strings and integers:

// For string keys
myrtx_avl_tree_t* string_tree = myrtx_avl_tree_create(&arena, myrtx_avl_compare_strings, NULL);

// For integer keys
myrtx_avl_tree_t* int_tree = myrtx_avl_tree_create(&arena, myrtx_avl_compare_integers, NULL);

Inserting Elements

To insert elements into the tree:

int value = 42;
myrtx_avl_tree_insert(tree, "key", &value, NULL);

If the key already exists, the value is updated and the previous value can be retrieved:

int new_value = 100;
void* old_value;
myrtx_avl_tree_insert(tree, "key", &new_value, &old_value);
// Now old_value points to the previous value (42)

Finding Elements

To find an element by key:

void* found_value;
if (myrtx_avl_tree_find(tree, "key", &found_value)) {
    printf("Value: %d\n", *(int*)found_value);
} else {
    printf("Key not found\n");
}

You can also check if a key exists without retrieving the value:

if (myrtx_avl_tree_contains(tree, "key")) {
    printf("Key exists\n");
}

Removing Elements

To remove an element from the tree:

myrtx_avl_tree_remove(tree, "key", NULL, NULL);

You can also retrieve the removed key and value:

void* removed_key;
void* removed_value;
if (myrtx_avl_tree_remove(tree, "key", &removed_key, &removed_value)) {
    printf("Removed key: %s, value: %d\n", (char*)removed_key, *(int*)removed_value);
}

Traversing the Tree

The AVL tree supports three traversal orders:

// Define a callback function
bool visit_callback(const void* key, void* value, void* user_data) {
    printf("Key: %s, Value: %d\n", (char*)key, *(int*)value);
    return true;  // Return false to stop traversal
}

// In-order traversal (sorted by key)
myrtx_avl_tree_traverse_inorder(tree, visit_callback, NULL);

// Pre-order traversal
myrtx_avl_tree_traverse_preorder(tree, visit_callback, NULL);

// Post-order traversal
myrtx_avl_tree_traverse_postorder(tree, visit_callback, NULL);

Finding Min/Max Elements

To find the minimum or maximum key:

void* min_key;
void* min_value;
if (myrtx_avl_tree_min(tree, &min_key, &min_value)) {
    printf("Min key: %s, value: %d\n", (char*)min_key, *(int*)min_value);
}

void* max_key;
void* max_value;
if (myrtx_avl_tree_max(tree, &max_key, &max_value)) {
    printf("Max key: %s, value: %d\n", (char*)max_key, *(int*)max_value);
}

Advanced Usage

Custom Comparison Functions

For custom key types, you need to provide a comparison function:

typedef struct {
    int x;
    int y;
} Point;

int compare_points(const void* key1, const void* key2, void* user_data) {
    const Point* p1 = (const Point*)key1;
    const Point* p2 = (const Point*)key2;

    // First compare x, then y
    if (p1->x != p2->x) {
        return p1->x - p2->x;
    }
    return p1->y - p2->y;
}

// Create tree with custom comparison
myrtx_avl_tree_t* point_tree = myrtx_avl_tree_create(&arena, compare_points, NULL);

Custom Memory Management

When using the AVL tree without an arena allocator, you need to free the memory manually:

// Define a free callback
void free_callback(void* key, void* value, void* user_data) {
    free(key);
    free(value);
}

// Free the tree and all its elements
myrtx_avl_tree_free(tree, free_callback, NULL);

Performance Considerations

AVL trees maintain a stricter balance than some other self-balancing trees (like Red-Black trees), which makes them:

• Slightly slower for insertions and deletions (due to more rotations)

• Slightly faster for lookup operations (due to more balanced structure)

• Very efficient for ordered traversal

For best performance: - Use arena allocators when appropriate to reduce memory allocation overhead - Choose the right comparison function for your key type - Consider using a hash table instead if you don’t need ordered operations

Common Use Cases

1. Dictionary with Ordered Iteration:

   // Create a dictionary
   myrtx_avl_tree_t* dict = myrtx_avl_tree_create(&arena, myrtx_avl_compare_strings, NULL);
   
   // Insert words
   int value1 = 1;
   int value2 = 2;
   myrtx_avl_tree_insert(dict, "apple", &value1, NULL);
   myrtx_avl_tree_insert(dict, "banana", &value2, NULL);
   
   // Print in alphabetical order
   myrtx_avl_tree_traverse_inorder(dict, visit_callback, NULL);
   

2. Numeric Range Index:

   // Create a tree with numeric keys
   myrtx_avl_tree_t* index = myrtx_avl_tree_create(&arena, myrtx_avl_compare_integers, NULL);
   
   // Insert data
   for (int i = 0; i < 100; i++) {
       int* key = myrtx_arena_alloc(&arena, sizeof(int));
       *key = i;
       myrtx_avl_tree_insert(index, key, data_for_key(i), NULL);
   }
   
   // Find range by traversing from min to threshold
   void* min_key;
   myrtx_avl_tree_min(index, &min_key, NULL);
   // ... then traverse until key > threshold
   

Conclusion

The AVL tree implementation in libmyrtx provides a robust, efficient, and easy-to-use solution for ordered data storage. By following the patterns described in this guide, you can leverage its strengths for a wide range of applications.