C中的AVL旋转

Question

当旋转发生时，只有第一次旋转在我的代码中有效，我不明白为什么我认为旋转函数返回错误的节点？大概下面是我的节点和树结构

#define ll unsigned long
typedef struct NODE_s *NODE; //Node structure
typedef struct NODE_s{
NODE right,left;
ll key;
int height;
void *data;
} NODE_t[1];
typedef struct AVL_s *AVL; //Tree structure
typedef struct AVL_s{
NODE root;
} AVL_t[1];

初始化功能

AVL AVL_init(){
AVL t = (AVL)malloc(sizeof(AVL_t));
t->root = NULL;
return t;
}
NODE node_init(ll init_key){
NODE node = (NODE)malloc(sizeof(NODE_t));
node->left = NULL;
node->right = NULL;
node->key = init_key;
node->height = 1;
node->data = NULL;
return node;
}

旋转功能

NODE rightRotate(NODE node){
NODE child  = node->left;
NODE childR = child->right;
child->right = node;
node->left = childR;

node->height = max(height(node->left), height(node->right))+1;
child->height = max(height(child->left), height(child->right))+1;
return child;
}
NODE leftRotate(NODE node)
{
NODE child  = node->right;
NODE childL = child->left;
child->left = node;
node->right = childL;

node->height = max(height(node->left), height(node->right))+1;
child->height = max(height(child->left), height(child->right))+1;
return child;
}

递归插入我认为必须使用两个函数从main发送树然后发送树->插入函数中的根。

NODE insert_rec(NODE node,ll rec_key){
if(rec_key < node->key){
if(node->left == NULL)
node->left = node_init(rec_key);
else
insert_rec(node->left, rec_key);
}else if(rec_key > node->key){
if(node->right == NULL)
node->right = node_init(rec_key);
else
insert_rec(node->right, rec_key);
}else
printf("Duplicate %lu Datan",rec_key);
//If I delete from here to end of functions, it is clearly recursive BST insert and works successfully
node->height = 1 + max(height(node->left),height(node->right));
int balanceFactor = balance(node);
if (balanceFactor > 1 && rec_key < node->left->key) //leftleft
node = rightRotate(node);   //return rightRotate(node) also working
if (balanceFactor < -1 && rec_key > node->right->key) //rightright
node = leftRotate(node);   //return leftRotate(node) also working
if (balanceFactor > 1 && rec_key > node->left->key) //leftright
{
node->left =  leftRotate(node->left);
node = rightRotate(node); 
}
if (balanceFactor < -1 && rec_key < node->right->key) //rightright
{
node->right = rightRotate(node->right);
node = leftRotate(node);
}
return node;
}
void insert(AVL tree,ll key){
if(key == -1){
printf("Invalid data %lun",key);
}
else if(tree->root == NULL){
tree->root = node_init(key);
}
else{
tree->root = insert_rec(tree->root,key);
}
}

int main() {
AVL tree = AVL_init();
insert(tree,111);
}

这是我的源代码，我无法理解我没有看到的内容。如果我把它换成正常的BST，它正在工作，但当旋转发生时，节点会出现在的某个地方

Answer 1

我解决了它。函数insert((进入垃圾桶，并将其放入insert_rec((。如果root=null条件，这只是根检查。

然后主要功能就这样被替换了，

int main() {
AVL tree = AVL_init();
NODE node = tree->root;
insert_rec(node,111);
}

最后，在平衡因子的情况下，我只需要返回函数

return leftRotate(node); //instead of node = leftRotate(node); 

return rightRotate(node); //instead of node = rightRotate(node);

这种视角使处理返回值变得容易​​来自功能