Функция правого поворота AVL все еще дает старые значения?

Question

Я пишу правое вращение для дерева AVL. В настоящее время я игнорирую часть высоты дерева AVL. Я позабочусь об этом позже. Но просто применяя правое вращение в 5 дает неправильные значения.l->data,ll->data,lll->data по-прежнему дает старые значения (5,3,2 соответственно) даже после выполнения правого поворота. Я использовал дерево AVL:

                                    9(Root)

               5(Left Child)                            13(Right Child)

         3                     7                  11                      17
    2
1

Код C:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>


struct AVLTree
{
  int data;
  struct AVLTree *left;
  struct AVLTree *right;
};




struct AVL *RightRotate1(struct AVLTree *rootop,struct AVLTree *root)
{
    if(root == NULL)
    {
        return NULL;
    }
    if(rootop->data > root->data)
    {
        root->right = RightRotate1(rootop,root->right);
    }
    else if(rootop->data < root->data )
    {
        root->left = RightRotate1(rootop,root->left);
    }
    else
    {
        struct AVLTree *A = rootop->left;
        rootop->left = A->right;
        A->right = rootop;

        return A;
    }
    return root;

}




int main()
{
    struct AVLTree * root = (struct AVLTree *)malloc(sizeof(struct AVLTree));
    root-> data = 9;
    struct AVLTree * l = (struct AVLTree *)malloc(sizeof(struct AVLTree));
    l -> data = 5;
    struct AVLTree * ll = (struct AVLTree *)malloc(sizeof(struct AVLTree));
    ll -> data = 3;
    ll -> left = ll -> right = NULL;
    struct AVLTree * lll = (struct AVLTree *)malloc(sizeof(struct AVLTree));
    lll -> data = 2;
    lll -> left = lll -> right = NULL;
    ll->left = lll;
    struct AVLTree * llll = (struct AVLTree *)malloc(sizeof(struct AVLTree));
    llll -> data = 1;
    llll -> left = llll -> right = NULL;
    lll->left = llll;
    struct AVLTree * lr = (struct AVLTree *)malloc(sizeof(struct AVLTree));
    lr -> data = 7;
    lr -> left = lr -> right = NULL;
    l -> left = ll;
    l -> right = lr;
    struct AVLTree * r = (struct AVLTree *)malloc(sizeof(struct AVLTree));
    r -> data = 13;
    struct AVLTree * rl = (struct AVLTree *)malloc(sizeof(struct AVLTree));
    rl -> data = 11;
    rl -> left = rl -> right = NULL;
    struct AVLTree * rr = (struct AVLTree *)malloc(sizeof(struct AVLTree));
    rr -> data = 17;
    rr -> left = rr -> right = NULL;
    r -> left = rl;
    r -> right = rr;
    root -> left = l;
    root -> right = r;



    root = RightRotate1(l,root);

    printf("Root is %d\n",root->data);
    printf("Root Left is %d\n",root->left->data);
    printf("Root Left Left is %d\n",root->left->left->data);
    printf("Root Left Right is %d\n",root->left->right->data);

    printf("Left is %d\n",l->data);
    printf("Left left is %d\n",ll->data);
    printf("Left right is %d\n",lll->data);


    return 0;
}

Answer 1

Вы все еще получаете старые значения для l, ll, and lll потому что они локальные переменные, определенные в main() и они не получают новые значения после возвращения из RightRotate1(), Только root указатель в main() меняется RightRotate1(), Если вы хотите использовать l, ll, and lll их нужно переназначить, чтобы они указывали на новые места, так как вы повернули дерево.

root = RightRotate1(l,root);
l = root->left;
ll = root->left->left;
lll = root->left->left->left;