AVL树左右旋转C

Question

我需要在AVL树上实现左右旋转

结构是：

typedef struct tree mynode;   // 
struct tree{                    // tree node struct
int value;
int key;
char color;
struct tree *left;
struct tree *right;
};

我的问题是，在正确旋转之后，当我尝试访问 node->left 时，程序因分段错误而崩溃。我认为旋转很好，但我觉得如果它不保存指针......我的意思是我做了旋转但它没有保存在左子树上。右旋：

mynode* rightRotate(mynode* root)
{
    mynode*tmp=(mynode*) malloc(sizeof(mynode));
    tmp->value=root->value;
    tmp->key=root->left->key;
    tmp->left=NULL;
    tmp->right=NULL;
    root->value=root->left->value;

    if(root->right==NULL)
      tmp->right=NULL;
    else if (root->right!=NULL)
      tmp->right=root->right;
    else printf("Error with right Rot\n");
    if (root->left->right==NULL)
      tmp->left=NULL;
    else if  (root->left->right!=NULL)
      tmp->left=root->left->right;
    else printf("Error with right Rot\n");
    root->right=tmp;

    mynode*tmp2;
    tmp2=root->left;
    root->left=root->left->left;
    free(tmp2); //freed old node
    printf("Rotation completed\n");
    return root;
}

我使用下面的函数只是为了检查前 3 个插入，我想要一个包含两个子树的树，这就是为什么它检查左边或右边是 NULL。

右旋转调用者：

mynode* checkRotate(mynode*root)
{
    if(root->left==NULL) 
    {
        printf("Left rotate\n");
        root=leftRotate(root);
        return root; //to ensure parent-parent exists
    }
    else if (root->right==NULL) 
    {
        printf("Right rotate\n");
        root=rightRotate(root);
        return root; //to ensure parent-parent exists
    }
    else return NULL;
    return root;
}

调用者：

...some code...
root=checkRotate(root);
right->left->color=RED;//crashes here
...some code...

显然左旋转在检查右子树而不是左子树时也有同样的问题。

编辑：新右旋：

void rightRotate(mynode*root,mynode*son)
{
    if (son==NULL)
    {
        printf("Cannot rotate, son is null\n");
        return;
    }
    else 
    {
        if(son->left==NULL) 
        {
            printf("No left child, returning\n");
            return;
        }
        else 
        {
            mynode* F = son;
            mynode* D = son->left;
            if(son->left->right==NULL)
                son->left=NULL;
            else if (son->left != NULL)
                son->left = son->left->right;
            else {
                printf("Weird in right rotate\n");
            }
            D->right=son;
            if(root->right==son)
            {
                root->right=D;
                return ;
            }
            else if (root->left==son)
            {
                root->left=D;
                return ;
            }
            else 
            {
                printf("Error while setting new son in right balance\n");
                return ;
            }
            printf("Generic error in right balance\n");
            return;
        }
    }
}

Answer 1

这是一张显示右旋转所需更改的图片：

旋转是通过用绿色连接替换红色连接来完成的。

顶部的连接可能来自树中更高的节点（F 是该节点的左侧 child 或右侧 child）。或者它是来自树的根指针的连接（如果 F 是根节点）。为了简单起见，rightRotate 的第一个参数应该是 指向节点 的指针。这样，指向 F 的指针并不重要，代码只是将该指针更新为指向 D.

在下面的代码中，第一行验证参数是否有效。第一个参数（指向指向 F 的指针）不能为 NULL。此外，F 和 D 都必须存在。

断言用于检查参数以简化调试。无效参数表示调用代码中存在问题。 assert 将导致调试器在该行停止（如果参数无效）。在调用堆栈中上升一级允许检查调用代码。

请注意，节点 E 是可选的，即 D 可能没有权限 child。如果 E 不存在，则 D->right 为 NULL，代码会将 F->left 设置为 NULL。 E.

不需要特殊处理

代码如下所示：

void rightRotate(mynode **parentPtr, mynode *child)
{
    // make sure the arguments are valid for a right rotation
    assert(parentPtr != NULL && child != NULL && child->left != NULL);

    // save the three node addresses involved in the rotation
    mynode *F = child;
    mynode *D = F->left;
    mynode *E = D->right;

    // perform the rotation
    *parentPtr = D;
    D->right = F;
    F->left = E;
}

AVL树左右旋转C

AVL Tree left and right rotation C

c

tree

binary-search-tree

avl-tree