I met a problem while trying to rotate an AVL tree in C

Question

I'm having some trouble while trying to rotate an AVL tree. I've been digging in the web the whole day and I think my code should work. I don't know why but when I test my function I lose the subtrees that should've been rotated.

Can I get any help?

Here's the code:

static void cbst__rotation_right(cbst **pp) {
    cbst *p = LEFT(*pp);
    LEFT(*pp) = RIGHT(p);
    RIGHT(p) = *pp;
    *pp=p;
    cbst__update_height(*pp);
    
}
    
static void cbst__rotation_left(cbst **pp) {
  cbst *p = RIGHT(*pp);
  RIGHT(*pp) = LEFT(p);
  LEFT(p) = *pp;
  *pp= p;
  cbst__update_height(*pp);
}

static void cbst__rotation_left_right(cbst **pp) {
  cbst__rotation_left(&LEFT(*pp));
  cbst__rotation_right(pp);
}

static void cbst__rotation_right_left(cbst **pp) {
  cbst__rotation_right(&RIGHT(*pp));
  cbst__rotation_left(pp);
}

And here's the function which balances the tree:


    static void cbst__balancing(cbst **pp) {
      if ((*pp) == NULL) {
        return;
      }
      cbst__update_height(*pp);
      if (cbst_balance(*pp) <= 1 && cbst_balance(*pp) >= (-1)) {
        return;
      }
      if (cbst__balance(*pp) == 2) {
        if (cbst__balance(LEFT(*pp)) == (-1)) {
          cbst__rotation_left_right(pp);
        }
        if (cbst__balance(LEFT(*pp)) == 1) {
          cbst__rotation_right(pp);
        }
        if (cbst_balance(LEFT(*pp)) != 1 && cbst_balance(LEFT(*pp)) != (-1)) {
          cbst__balancing(&LEFT(*pp));
        }
      }
      if (cbst__balance(*pp) == (-2)) {
        if (cbst__balance(RIGHT(*pp)) == +1) {
          cbst__rotation_right_left(pp);
        }
        if (cbst__balance(RIGHT(*pp)) == (-1)) {
          cbst__rotation_left(pp);
        }
        if (cbst_balance(RIGHT(*pp)) != 1 && cbst_balance(RIGHT(*pp)) != (-1)) {
          cbst__balancing(&RIGHT(*pp));
        }
      }
      cbst__balancing(pp);
    }

NB: cbst__balance is a function which returns the weight of a tree given as an input.

I don't see the case handled where a double rotation is needed? — trincot, Dec 28 '21 at 20:44
i actually wrote the functions of double rotation ( and just edited the post adding them), but i thought i won't actually need them to balance a tree, am i wrong ? — Khalil Makhloufi, Dec 28 '21 at 20:58
You do need them. It depends on the balance factor of the child. There are really 4 cases to distinguish, and 2 of them need a double rotation. See [Wikipedia](https://en.wikipedia.org/wiki/AVL_tree#Rebalancing) — trincot, Dec 28 '21 at 21:01
thank you for your answer, i've edited the code and added the two cases where a double rotation is needed, but the problem stays the same, and its in the two rotation functions( rotate right and rotate left). — Khalil Makhloufi, Dec 28 '21 at 21:44
Can you edit the question and add the driver code, with a sample tree created and the problem occurring, so it is reproducible? — trincot, Dec 28 '21 at 21:53
In `rotation_right` and `rotation_left` you seem to be swapping **two** connections. To be correct, you need to break and make **three** connections. — user3386109, Dec 28 '21 at 22:28
https://stackoverflow.com/questions/64701660/avl-tree-left-and-right-rotation-c/64722268#64722268 — user3386109, Dec 28 '21 at 22:37
I finally managed to make the code work, the problem wasn't even in my rotations, but in the function that is rebalancing the tree, as you told me there were 4 cases, one for each rotation. the code has been edited. thank you. — Khalil Makhloufi, Dec 30 '21 at 21:08

I met a problem while trying to rotate an AVL tree in C

0 Answers0