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.