AVL Tree in C Criticism

Question

I have made an AVL tree in C and coded the basic functionality of insertion, deletion, and search. I would love some criticism on my implementation especially on the insertion and deletion section of the code. Furthermore I think I could have used one less variable in the Node structure as you do not need a height for both the left and the right sub-tree instead you just need to know their balance, but for now the implementation contains the height for the left and right sub-tree.

TLDR - Criticism on my implementation of the AVL Tree especially the insertion and deletion section of the code.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#define MAX(x, y) (x < y ? y : x)

struct Node
{
   void *data;
   int32_t max_height_left;
   struct Node *left;
   int32_t max_height_right;
   struct Node *right;
};

struct AVL_Tree
{
   struct Node *root;
   size_t size_of_data;
   int32_t (*compare)(const void *, const void *);
   void (*print)(const void *);
};

int32_t create_tree(struct AVL_Tree **tree, const size_t size_of_data, int32_t (*compare)(const void *, const void *), void (*print)(const void *))
{
   *tree = malloc(sizeof(**tree));
   if(*tree == NULL)
   {
      return -1;
   }
   (*tree)->size_of_data = size_of_data;
   (*tree)->compare = compare;
   (*tree)->print = print;
   return 0;
}

static struct Node * left_rotate(struct Node *node)
{
   struct Node *temp;
   temp = node->right;

   node->right = temp->left;
   node->max_height_right = temp->max_height_left;

   temp->left = node;
   temp->max_height_left = MAX(node->max_height_left, node->max_height_right) + 1;
   return temp;
}

static struct Node * right_rotate(struct Node *node)
{
   struct Node *temp;
   temp = node->left;

   node->left = temp->right;
   node->max_height_left = temp->max_height_right;

   temp->right = node;
   temp->max_height_right = MAX(node->max_height_left, node->max_height_right) + 1;
   return temp;
}

static struct Node * insert_data_helper(struct Node *node, const void *data, int32_t (*compare)(const void *, const void *), const size_t size_of_data)
{
   struct Node *temp;
   int32_t results;
   if(node == NULL)
   {
      /*allocate all the memory*/
      temp = malloc(sizeof(*temp));
      if(temp == NULL)
      {
         return NULL;
      }
      temp->data = malloc(size_of_data);
      if(temp->data == NULL)
      {
         free(temp);
         return NULL;
      }

      /*set all the vars*/
      memcpy(temp->data, data, size_of_data);
      temp->left = temp->right = NULL;
      temp->max_height_left = temp->max_height_right = 0;
      return temp;
   }

   results = compare(data, node->data);
   if(results < 0)
   {
      node->left = insert_data_helper(node->left, data, compare, size_of_data);

      /*get the greater of the two heights from the left sub tree*/
      node->max_height_left = MAX(node->left->max_height_left, node->left->max_height_right) + 1;

      if(node->max_height_left - node->max_height_right > 1)
      {
         if(node->left->max_height_left - node->left->max_height_right <= -1)
         {
            node->left = left_rotate(node->left);
         }
         node = right_rotate(node);
      }
   }
   else if(results > 0)
   {
      node->right = insert_data_helper(node->right, data, compare, size_of_data);

      /*get the greater of the two heights from the right sub tree*/
      node->max_height_right = MAX(node->right->max_height_left, node->right->max_height_right) + 1;

      if(node->max_height_left - node->max_height_right < -1)
      {
         if(node->right->max_height_left - node->right->max_height_right >= 1)
         {
            node->right = right_rotate(node->right);
         }
         node = left_rotate(node);
      }
   }

   return node;
}

void insert_data(struct AVL_Tree *tree, const void *data)
{
   tree->root = insert_data_helper(tree->root, data, tree->compare, tree->size_of_data);
}

static struct Node * get_lowest_value_node(struct Node *node)
{
   if(node == NULL)
   {
      return NULL;
   }
   else if(node->left == NULL)
   {
      return node;
   }

   return get_lowest_value_node(node->left);
}

/*delete data*/
static struct Node * delete_data_helper(struct Node *node, const void *data, int32_t (*compare)(const void *, const void *), const size_t size_of_data)
{
   struct Node *temp;
   int32_t results;

   if(node == NULL)
   {
      return NULL;
   }

   results = compare(data, node->data);
   if(results < 0)
   {
      node->left = delete_data_helper(node->left, data, compare, size_of_data);
      node->max_height_left = node->left == NULL ? 0 : MAX(node->left->max_height_left, node->left->max_height_right) + 1;

      if(node->max_height_left - node->max_height_right < -1)
      {
         if(node->right != NULL && node->right->max_height_left - node->right->max_height_right >= 1)
         {
            node->right = right_rotate(node->right);
         }
         node = left_rotate(node);
      }
   }
   else if(results > 0)
   {
      node->right = delete_data_helper(node->right, data, compare, size_of_data);
      node->max_height_right = node->right == NULL ? 0 : MAX(node->right->max_height_left, node->right->max_height_right) + 1;

      if(node->max_height_left - node->max_height_right > 1)
      {
         if(node->left != NULL && node->left->max_height_left - node->left->max_height_right <= -1)
         {
            node->left = left_rotate(node->left);
         }
         node = right_rotate(node);
      }
   }
   else
   {
      if(node->left == NULL)
      {
         temp = node->right;
         free(node->data);
         free(node);
         return temp;
      }
      else if(node->right == NULL)
      {
         temp = node->left;
         free(node->data);
         free(node);
         return temp;
      }
      else
      {
         /*has two branches. get the lowest value from the right branch*/
         temp = get_lowest_value_node(node->right);
         memcpy(node->data, temp->data, size_of_data);

         /*now delete the value that was copies from the right branch*/
         node->right = delete_data_helper(node->right, temp->data, compare, size_of_data);
         node->max_height_right = node->right == NULL ? 0 : MAX(node->right->max_height_left, node->right->max_height_right) + 1;

         if(node->max_height_left - node->max_height_right > 1)
         {
            if(node->left != NULL && node->left->max_height_left - node->left->max_height_right <= -1)
            {
               node->left = left_rotate(node->left);
            }
            node = right_rotate(node);
         }
      }
   }

   return node;
}

void delete_data(struct AVL_Tree *tree, const void *data)
{
   tree->root = delete_data_helper(tree->root, data, tree->compare, tree->size_of_data);
}

static int8_t contains_data_helper(struct Node *node, const void *data, int32_t (*compare)(const void *, const void *))
{
   int32_t results;
   if(node == NULL)
   {
      return -1;
   }

   results = compare(data, node->data);
   if(results < 0)
   {
      return contains_data_helper(node->left, data, compare);
   }
   else if(results > 0)
   {
      return contains_data_helper(node->right, data, compare);
   }

   return 0;
}

int8_t contains_data(struct AVL_Tree *tree, const void *data)
{
   return contains_data_helper(tree->root, data, tree->compare);
}

static void free_tree_helper(struct Node *node)
{
   if(node == NULL)
   {
      return;
   }

   free_tree_helper(node->left);
   free_tree_helper(node->right);

   free(node->data);
   free(node);
}

void free_tree(struct AVL_Tree *tree)
{
   free_tree_helper(tree->root);
}

static void pre_order_helper(struct Node *node, void (*print)(const void *))
{
   if(node == NULL)
   {
      return;
   }
   print(node->data);
   printf("(left = %d, right = %d, balance = %d)\n", node->max_height_left, node->max_height_right, node->max_height_left - node->max_height_right);
   pre_order_helper(node->left, print);
   pre_order_helper(node->right, print);
}

void pre_order(struct AVL_Tree *tree)
{
   pre_order_helper(tree->root, tree->print);
}

static void in_order_helper(struct Node *node, void (*print)(const void *))
{
   if(node == NULL)
   {
      return;
   }
   in_order_helper(node->left, print);
   print(node->data);
   printf("(left = %d, right = %d, balance = %d)\n", node->max_height_left, node->max_height_right, node->max_height_left - node->max_height_right);
   in_order_helper(node->right, print);
}

void in_order(struct AVL_Tree *tree)
{
   in_order_helper(tree->root, tree->print);
}

static void post_order_helper(struct Node *node, void (*print)(const void *))
{
   if(node == NULL)
   {
      return;
   }
   post_order_helper(node->left, print);
   post_order_helper(node->right, print);
   print(node->data);
   printf("(left = %d, right = %d, balance = %d)\n", node->max_height_left, node->max_height_right, node->max_height_left - node->max_height_right);
}

void post_order(struct AVL_Tree *tree)
{
   post_order_helper(tree->root, tree->print);
}

/*user code*/

void print_data(const void *ptr)
{
   const int *ptr_temp = ptr;
   printf("%d ", *ptr_temp);
}

int compare(const void *ptr1, const void *ptr2)
{
   const int *ptr1_temp, *ptr2_temp;
   ptr1_temp = ptr1;
   ptr2_temp = ptr2;

   if(*ptr1_temp < *ptr2_temp)
   {
      return -1;
   }
   else if(*ptr1_temp > *ptr2_temp)
   {
      return 1;
   }
   return 0;
}

int main(void)
{
   struct AVL_Tree *tree;
   int i;

   /*array is used to insert data into the tree*/
   int array[] = {1, 2, 3};

   create_tree(&tree, sizeof(array[0]), &compare, &print_data);

   for(i = 0; i < sizeof(array) / sizeof(array[0]); i++)
   {
      insert_data(tree, (array + i));
   }

   pre_order(tree);
   printf("\n\n\n");

   i = 3;
   delete_data(tree, &i);

   pre_order(tree);

   i = 1;
   printf("\n(Contains the value %d) = %d(0 == yes, -1 == no)\n", i, contains_data(tree, &i));

   free_tree(tree);
   return 0;
}

This is the make file I use

program: BBST.o
        gcc *.o -o program

BBST.o: BBST.c
        gcc -g -c -Wall -pedantic BBST.c

clean:
        rm *.o program

Answer 1

Height

The usually AVL tree needs to only record the height difference or balance factor: [-1, 0, 1]. Instead of 2 int32_t. A signed char will do. Given struct alignment issue, might as well use a single int.

Naming

Instead of global names all over the name space as with:

struct Node
struct AVL_Tree
create_tree()
insert_data()
delete_data()
free_tree()
...

How about a uniform style and prefix?

struct AVL_Node
struct AVL_Tree
AVL_create()
AVL_insert()
AVL_delete()
AVL_free()
AVL_...

AVL.h

I'd really like to see AVL.c, AVL.h, main.c for a clear demarcation of what is seen by the public and what is private.

Fixed width types

Rather than int32_t, consider an int. int32_t is excessively wide for small applications.

C2X ordering

Consider the order of parameters in function declarations should be arranged such that the size of an array appears before the array.
Wrap long lines.

// static struct Node * insert_data_helper(struct Node *node, const void *data, int32_t (*compare)(const void *, const void *), const size_t size_of_data);
static struct Node *insert_data_helper(size_t size, struct Node *node, void *data, 
    int32_t (*compare)(const void *, const void *));

Allocate to the referenced object

Good use of *tree = malloc(sizeof(**tree));

Minor: Unneeded else

if (node == NULL) {
  return NULL;
}
// else if(node->left == NULL) {
if (node->left == NULL) {
  return node;
}

Also in contains_data_helper().

Good to tolerate delete_data_helper(NULL, ...)

Also free_tree_helper(NULL).

Consider a return value on the helper function

Instead of void (*f)(const void *), how about int (*f)(const void *) that returns early when the return value is non-zero.

static int helper(struct Node *node, int (*foo)(const void *)) {
   if(node == NULL) {
      return 0;
   }
   int retval = helper(node->left, print);
   if (retval) {
     return retval;
   }
   retval = foo(node->data);
   if (retval) {
     return retval;
   }
   return helper(node->right, foo);
}

I'd even consider passing in a state.

static int helper(struct Node *node, 
    int (*foo)(void * state, const void *), void *state);

---

Criticism on my implementation of the AVL Tree especially the insertion and deletion section of the code.

A better than usual AVL code.
Good to properly free(temp); on insertion failure.