AVL tree, c, rotation implementation

Question

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

There's a problem in function rotacao_esquerda. This is a rotation of a AVL tree.

How to fix it?

Answer 1

There are a number of ways to fix this problem:

• insert copious quantities of printf debug statements throughout your code and run it, examining the output.
• run your code within a debugger, single stepping and examining variables after each step.
• ask an open-ended, vague question here on SO and try to get us to do all the work for you.

Only two of those options will make you a better developer and less likely to annoy us in future :-)

What you should try to do first is to narrow the problem down. All problem reports (here on SO and in the real world) should contain:

• what you were doing (in great detail) that caused the problem.
• what you expected to happen.
• what actually happened.

Anything less is a user not keeping up their end of the bargain.

---

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;
}

Okay, that's your function and it appears you want to rotate right through the no (A below) node. And, as per your comment: pai = father, dir = right and esq = left.

 X
  \
   A
  / \
 B   C
/ \ / \

so you end up with something like:

 X
  \
   B
  / \
     A
    / \
       C

I see one immediate possible problem. You're trying to change the parent pointer of that node so that it points to the rotated node B.

But you're changing no->pai->dir which is the right node of X. What happens if the tree is structured as follows?

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

If you try to rotate through the A node of that tree with your code, you're going to seriously compromise the Y sub-tree.

From a cursory desk-check, I think you can start by changing:

no->pai->dir = temp;

to:

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

which should change the correct pointer in the parent. Keep in mind I haven't checked a large number of possible trees, just this one:

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

with the in-order traversal of DBEAFCGXY, which, if you rotate right through A with the code change I gave, you get:

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

which looks about right (inorder DBEAFGCXY, the same as before).

So, bottom line, try this one:

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;
}

and see how it goes.

---

Diogo, I'll leave you some code to play with to illustrate what I meant. Look over the following code. It basically creates a dummy structure and dumps it out then runs your rotate routine on it. You can see from the output that the resultant tree is wrong.

It then recreates the original tree and runs the fixed rotate function, producing what I believe to be the correct result.

Feel free to use the dumpAvl function in your debugging efforts if you have further problems. It outputs a relatively nicely formatted tree with a node followed by indented child nodes (< for the left and > for the right).

#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;
}

When you run this, it produces the following. You can see the original code has multiple copies of some of the sub-trees due to the fact the code assumed the roration point would always be on the right side of its parent. The fixed code does not make that assumption.

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
==================================================