Дерево AVL в критике C

Я создал дерево AVL на C и закодировал основные функции вставки, удаления и поиска. Мне бы хотелось критиковать мою реализацию, особенно в части кода вставки и удаления. Кроме того, я думаю, что мог бы использовать на одну переменную меньше в структуре узла, поскольку вам не нужна высота как для левого, так и для правого поддерева, вместо этого вам просто нужно знать их баланс, но на данный момент реализация содержит высоту для левое и правое поддерево.

TL; DR – критика моей реализации дерева AVL, особенно в части кода вставки и удаления.

#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("nnn");

   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;
}

Это make-файл, который я использую

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

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

clean:
        rm *.o program

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *