Ошибка AVL Tree (in C)

Question

Я узнал дерево AVL от Анализ структур данных и алгоритмов в C, я набрал код сам, и его функция вставки не может работать хорошо.

Я проверил эти функции со многими данными. Некоторые узлы не могут быть вставлены и некоторые узлы вставлены случайным образом. Я не имею в виду.

Вот часть моего кода:

AVLTree.h:

/* Data structures model */ 
typedef int data_type; 
typedef struct avlnode { 
    data_type data; 
    int height; 
    struct avlnode *lchild; 
    struct avlnode *rchild; 
} AvlNode; 
typedef AvlNode AvlTree; 

/* Function Prototypes including init, find(custom/min/max) and insert */ 
AvlTree *AVL_create(data_type value); 
AvlNode *AVL_find(AvlTree *tree, data_type value); 
AvlNode *AVL_find_min(AvlTree *tree); 
AvlTree *AVL_find_max(AvlTree *tree); 
AvlTree *AVL_insert(AvlTree *tree, data_type value); 
#define MAX_HEIGHT(x,y) (x > y) ? x : y 

AVLTree.c

/* Static function to get the height of a node in the tree */ 
static int height(AvlNode *node) { 
    return (node == NULL) ? -1 : node->height; 
} 

/* Tree init func with a valued root node */ 
AvlTree *AVL_create(data_type value) { 
    AvlTree *newtree; 
    newtree = (AvlTree *)malloc(sizeof(AvlTree)); 
    if (newtree == NULL) 
     return NULL; 

    newtree->lchild = NULL; 
    newtree->rchild = NULL; 
    newtree->height = 0; 
    newtree->data = value; 
    return newtree; 
} 

/* Node search functions. In fact I use BST search functions here */ 
/* I'm not sure could them run well here in AVL tree */ 

AvlNode *AVL_find(AvlTree *tree, data_type value) { 
    AvlTree *temptree = tree; 
    if (temptree == NULL) 
     return NULL; 
    if (value < temptree->data) 
     return AVL_find(tree->lchild, value); 
    else if (value > temptree->data) 
     return AVL_find(tree->rchild, value); 
    else 
     return temptree; 
} 
AvlNode *AVL_find_min(AvlTree *tree) { 
    AvlTree *temptree = tree; 
    if (temptree != NULL) { 
     while (temptree->lchild != NULL) 
      temptree = temptree->lchild; 
    } 
    return temptree; 
} 
AvlTree *AVL_find_max(AvlTree *tree) { 
    AvlTree *temptree = tree; 
    if (temptree != NULL) { 
     while (temptree->rchild != NULL) 
      temptree = temptree->rchild; 
    } 
    return temptree; 
} 


AvlTree *AVL_insert(AvlTree *tree, data_type value) { 
    AvlTree *temptree = tree; 

    if (temptree == NULL) { 
     temptree = (AvlNode *)malloc(sizeof(AvlNode)); 
     if (temptree == NULL) 
      return NULL; 
     else { 
      temptree->data = value; 
      temptree->height = 0; 
      temptree->lchild = NULL; 
      temptree->rchild = NULL; 
     } 
    } 
    else if (value < temptree->data) { 
     temptree->lchild = AVL_insert(temptree->lchild, value); 
     if (height(temptree->lchild) - height(temptree->rchild) == 2) { 
      if (value < temptree->lchild->data) 
       temptree = single_rotate_with_left(temptree); 
      else 
       temptree = double_rotate_with_right_left(temptree); 
     } 
    } 
    else if (value > temptree->data) { 
     temptree->rchild = AVL_insert(temptree->rchild, value); 
     if (height(temptree->rchild) - height(temptree->lchild) == 2) { 
      if (value > temptree->rchild->data) 
       temptree = single_rotate_with_right(temptree); 
      else 
       temptree = double_rotate_with_left_right(temptree); 
     } 
    } 
    temptree->height = MAX_HEIGHT(height(temptree->lchild), height(temptree->rchild)) + 1; 
    return temptree; 
} 

main.c

#include "AVLTree.h" 

int main() { 
    AvlTree *newtree = AVL_create(50); 

    AVL_insert(newtree, 70); 
    AVL_insert(newtree, 80); 
    AVL_insert(newtree, 90); 

    for (int i = -5; i < 20; i++) { 
     AVL_insert(newtree, i * i * i); 
    } 

    printf("root node: %d\n", newtree->data); 
    printf("left of root node: %d\n", newtree->lchild->data); 
    printf("findmin: %d\n", AVL_find_min(newtree)->data); 
    printf("findmax: %d\n", AVL_find_max(newtree)->data); 
    return 0; 
} 

Answer 1

Я попробовал ваш программы и отключить перебалансировку (см. ниже где). Затем он работает правильно, распечатав:

root node: 50 
left of root node: -125 
findmin: -125 
findmax: 6859 

Что является правильным, я думаю.

Так что я думаю, что проблема в одной из ваших функций вращения.

Если вы не можете найти эту проблему, пожалуйста, сообщите нам об этом.

else if (value < temptree->data) { 
    temptree->lchild = AVL_insert(temptree->lchild, value); 
    /*if (height(temptree->lchild) - height(temptree->rchild) == 2) { 
     if (value < temptree->lchild->data) 
      temptree = single_rotate_with_left(temptree); 
     else 
      temptree = double_rotate_with_right_left(temptree); 
    }*/ 
} 
else if (value > temptree->data) { 
    temptree->rchild = AVL_insert(temptree->rchild, value); 
    /*if (height(temptree->rchild) - height(temptree->lchild) == 2) { 
     if (value > temptree->rchild->data) 
      temptree = single_rotate_with_right(temptree); 
     else 
      temptree = double_rotate_with_left_right(temptree); 
    }*/ 
}