c - AVL 树插入(在 C 中)失败

Question

我从Data Structures and Algorithms Analysis in C学了AVL tree，自己敲代码，插入功能不太好用。

我用很多数据检查了这些功能。有些节点无法插入，有些节点随机插入。未分类，我是说。

这是我的部分代码:

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

AVL树.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;
}

主.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);
    }*/
}