arbre AVL, c, la mise en œuvre de rotation

Question

code ici: http://pastebin.com/VAdc67bE

Il y a un problème dans la fonction rotacao_esquerda. Il s'agit d'une rotation d'un arbre AVL.

Comment le réparer?

Answer 1

Il y a plusieurs façons de résoudre ce problème:

• insérer de grandes quantités d'printf instructions de débogage tout au long de votre code et l'exécuter, en examinant la sortie.
• exécutez votre code dans un débogueur, simple pas à pas et l'examen des variables après chaque étape.
• poser une question vague et ouverte ici sur SO et essayer de nous faire tous le travail pour vous.

Seulement deux de ces options vous fera un meilleur développeur et moins susceptibles de nous embêter à l'avenir :-)

Ce que vous devriez essayer de faire d'abord est de réduire le problème vers le bas. Tous les rapports de problème (ici sur SO et dans le monde réel) doivent contenir:

• ce que vous faisiez (en détail) qui a causé le problème.
• ce que vous attendiez.
• ce qui s'est passé réellement.

Quelque chose de moins est un utilisateur ne respectant pas leur fin de l'aubaine.

---

AVL *rotacao_direita(AVL *no) { 
    AVL *temp; 
    temp = no->esq; 
    no->esq = temp->dir; 
    if (temp->dir != NULL) 
     temp->dir->pai = no; 
    temp->dir = no; 
    temp->pai = no->pai; 
    no->pai->dir = temp; 
    no->pai = temp; 
    no->fb = 0; 
    return temp; 
} 

D'accord, c'est votre fonction et il semble que vous voulez tourner à droite par le nœud no (A ci-dessous). Et, selon votre commentaire: pai = père, dir = droite et esq = gauche.

X 
    \ 
    A 
/\ 
B C 
/\/\ 

si vous vous retrouvez avec quelque chose comme:

X 
    \ 
    B 
/\ 
    A 
    /\ 
     C 

Je vois un problème possible immédiatement. Vous essayez de modifier le pointeur parent de ce noeud afin qu'il pointe vers le noeud pivoté B.

Mais vous modifiez no->pai->dir qui est le droit nœud de X. Que se passe-t-il si l'arbre est structuré comme suit?

 X 
    /\ 
    A Y 
/\ 
B C 
/\/\ 

Si vous essayez de tourner à travers le noeud A de cet arbre avec votre code, vous allez compromettre sérieusement le sous-arbre Y.

A partir d'un bureau-vérification rapide, je pense que vous pouvez commencer par changer:

no->pai->dir = temp; 

à:

if (no->pai->esq == no) 
    no->pai->esq = temp; 
else 
    no->pai->dir = temp; 

qui devrait changer le pointeur correct dans le parent. Gardez à l'esprit que je n'ai pas vérifié un grand nombre d'arbres possibles, seulement celui-ci:

 _____X_____ 
    /   \ 
    __A__   Y 
/ \ 
    B  C 
/\ /\ 
D E F G 

avec le traversal en ordre de DBEAFCGXY, qui, si vous faites tourner à travers A avec le changement de code que j'ai donné, vous obtenez:

 _____X_____ 
    /   \ 
    __B__   Y 
/ \ 
    D  A 
     /\ 
     E C 
     /\ 
      F G 

qui semble correcte (afinde DBEAFGCXY, le même que précédemment).

Ainsi, la ligne de fond, essayez celui-ci:

AVL *rotacao_direita(AVL *no) { 
    AVL *temp; 
    temp = no->esq; 
    no->esq = temp->dir; 
    if (temp->dir != NULL) 
     temp->dir->pai = no; 
    temp->dir = no; 
    temp->pai = no->pai; 
    if (no->pai->esq == no) 
     no->pai->esq = temp; 
    else 
     no->pai->dir = temp; 
    no->pai = temp; 
    no->fb = 0; 
    return temp; 
} 

et voir comment ça se passe.

---

Diogo, je vais vous laisser du code pour jouer avec ce que je voulais dire. Regardez sur le code suivant. Il crée essentiellement une structure fictive et la vide puis exécute votre routine de rotation sur elle. Vous pouvez voir à partir de la sortie que l'arbre résultant est faux.

Ensuite, il recrée l'arborescence d'origine et exécute la fonction de rotation fixe, produisant ce que je crois être le résultat correct. N'hésitez pas à utiliser la fonction dumpAvl dans vos efforts de débogage si vous avez d'autres problèmes. Il sort un arbre relativement bien formaté avec un nœud suivi de nœuds enfants indentés (< pour la gauche et > pour la droite).

#include <stdio.h> 
#include <string.h> 

typedef struct AVL { 
    struct AVL *pai, *esq, *dir; 
    char chr; int fb; 
} AVL; 

 

AVL *rotacao_direita(AVL *no) { 
    AVL *temp; 
    temp = no->esq; 
    no->esq = temp->dir; 
    if (temp->dir != NULL) 
     temp->dir->pai = no; 
    temp->dir = no; 
    temp->pai = no->pai; 
    no->pai->dir = temp; 
    no->pai = temp; 
    no->fb = 0; 
    return temp; 
} 

 

AVL *rotacao_direita_fixed(AVL *no) { 
    AVL *temp; 
    temp = no->esq; 
    no->esq = temp->dir; 
    if (temp->dir != NULL) 
     temp->dir->pai = no; 
    temp->dir = no; 
    temp->pai = no->pai; 
    if (no->pai->esq == no) 
     no->pai->esq = temp; 
    else 
     no->pai->dir = temp; 
    no->pai = temp; 
    no->fb = 0; 
    return temp; 
} 

 

static AVL *newNode (AVL *pai, char which, AVL *esq, AVL *dir, char chr) { 
    AVL *node = malloc (sizeof (AVL)); 
    node->pai = pai; 
    node->esq = esq; 
    node->dir = dir; 
    node->chr = chr; 
    if (pai != NULL) { 
     if (which == '<') { 
      node->pai->esq = node; 
     } else { 
      node->pai->dir = node; 
     } 
    } 
    return node; 
} 

 

static void dumpAvl (char *desc, AVL *node, int spc, char which) { 
    int i; 
    if (desc != NULL) { 
     printf ("%s:\n", desc); 
     for (i = 0; i < strlen (desc); i++) 
      printf ("-"); 
     printf ("-\n"); 
    } 
    for (i = 0; i < spc; i++) printf (" "); 
    if (node == NULL) { 
     printf ("%c#\n", which); 
    } else { 
     printf ("%c%c\n", which, node->chr); 
     if ((node->esq != NULL) || (node->dir != NULL)) { 
      dumpAvl (NULL, node->esq, spc+2, '<'); 
      dumpAvl (NULL, node->dir, spc+2, '>'); 
     } 
    } 
    if (spc == 0) 
     printf ("==================================================\n"); 
} 

 

static AVL *setupTree (void) { 
    AVL *root = newNode (NULL, '-', NULL, NULL, 'X'); 

    AVL *node = newNode (root, '<', NULL, NULL, 'A'); 
    node = newNode (root, '>', NULL, NULL, 'Y'); 

    node = newNode (root->esq, '<', NULL, NULL, 'B'); 
    node = newNode (root->esq, '>', NULL, NULL, 'C'); 

    node = newNode (root->esq->esq, '<', NULL, NULL, 'D'); 
    node = newNode (root->esq->esq, '>', NULL, NULL, 'E'); 

    node = newNode (root->esq->dir, '<', NULL, NULL, 'F'); 
    node = newNode (root->esq->dir, '>', NULL, NULL, 'G'); 

    return root; 
} 

 

int main (void) { 
    AVL *root, *junk; 

    root = setupTree(); 
    dumpAvl ("Original code", root, 0, '-'); 
    junk = rotacao_direita (root->esq); 
    dumpAvl (NULL, root, 0, '-'); 

    root = setupTree(); 
    dumpAvl ("Fixed code", root, 0, '-'); 
    junk = rotacao_direita_fixed (root->esq); 
    dumpAvl (NULL, root, 0, '-'); 

    return 0; 
} 

Lorsque vous exécutez cela, il produit ce qui suit. Vous pouvez voir le code original a plusieurs copies de certains des sous-arbres en raison du fait que le code supposait que le point de roration serait toujours sur le côté droit de son parent. Le code fixe ne fait pas cette hypothèse.

Original code: 
-------------- 
-X 
    <A 
    <B 
     <D 
     >E 
    >C 
     <F 
     >G 
    >Y 
================================================== 
-X 
    <A 
    <E 
    >C 
     <F 
     >G 
    >B 
    <D 
    >A 
     <E 
     >C 
     <F 
     >G 
================================================== 

 

Fixed code: 
----------- 
-X 
    <A 
    <B 
     <D 
     >E 
    >C 
     <F 
     >G 
    >Y 
================================================== 
-X 
    <B 
    <D 
    >A 
     <E 
     >C 
     <F 
     >G 
    >Y 
==================================================