C语言 AVL树插入改变根

Question

我必须在C中实现AVL树。我编写了下面的insert-Method，但它只会不断更改树的根。

我认为这与我如何遍历树有关。当函数只需要一个节点时，我知道该怎么做，但是对于整个树，我该怎么做呢?

void AVL_insert(AVLTree* avlt, int value){
AVLTree *tree = avlt;
AVLNode *root = avlt->root;
if(tree->root == NULL){
AVLNode *node = calloc(1, sizeof(AVLNode));
node->value = value;
node->height = 0;
tree->root = node;
tree->numberOfNodes = avlt->numberOfNodes+1;
return;
}
else if(value < tree->root->value){
tree->root = root->left;
AVL_insert_value(tree, value);
} 
else if(value > tree->root->value){
tree->root = root->right;
AVL_insert_value(tree, value);
} 
else return;

//..add height, balance tree
}

结构:

struct AVLNode{
struct AVLNode* left;       
struct AVLNode* right;  
struct AVLNode* parent;
int value;
int height;
};
struct AVLTree{
struct AVLNode* root;
int numberOfNodes;
};
typedef struct AVLNode AVLNode;
typedef struct AVLTree AVLTree;

Answer 1

我猜是哪里出了问题

1. 插入到空节点分配根，它的左和右子节点被设置为NULL。

AVLNode *node = calloc(1, sizeof(AVLNode));

calloc()设置节点内容为零。

2. 插入新值。当子节点在递归之前被更新时，根节点被设置为它的左或右子节点。

tree->root = root->left; // root->left is `NULL`

现在，根是NULL。

3. 添加下一个值。根是NULL。转到第一点

结果，一个新值交替地添加到空树或单元素树中。

可能的解决办法:不要更新根节点的子节点。只需在树中插入一个值作为叶子，让重新平衡代码优化树的深度，同时从递归返回。