Insert function fails to rotate the nodes with unbalance factor

Question

Why does my insert function, in a C implementation of an AVL tree, fails to rotate the nodes with unbalance factor?

Here is my code:

// AVL Tree Implementation

typedef struct Node{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
    int balanceFactor;
}node;

int max(int a, int b);
int getHeight(node *n);
int getBalanceFactor(node *n);
void insert(node **n, int key);
void rotateLeft(node **n);
void rotateRight(node **n);

// Traversal
// In-Order Traversal
// Pre-Order Traversal
InOrder(node *n){
    if (n != NULL){
        InOrder(n->left);
        printf("%d ", n->key);
        InOrder(n->right);
    }
}

define MAX_SIZE 6

int main(){
    node *root = NULL;

    int a[MAX_SIZE] = {10,9,8,7,6,5};

    int i;
    printf("\n\nInserting items in the Tree...\n\n");
    for(i = 0; i < MAX_SIZE; i++){
        printf("\nInserted: %d",a[i]);
        insert(&root, a[i]);
    }

    printf("\n\nElements in the Tree: ");
    InOrder(root);
    printf("\n\n");
}

int max(int a, int b){
    return (a > b)? a : b;
}

/* Get the height of a Node */
int getHeight(node *n){
    if(n == NULL)
        return 0;
    return n->height;
}

/* Get the Balance Factor of a Node */
int getBalanceFactor(node *n){
    if(n == NULL)
        return 0;
    return (getHeight(n->left)-getHeight(n->right));
}

Insert Function, Rotate Left and Rotate Right

void insert(node **n, int key){
    if(*n == NULL){
        /* Create a New Node */
        *n = (node*)malloc(sizeof(node));
        if(*n != NULL){
            (*n)->key = key;
            (*n)->left = (*n)->right = NULL;
            (*n)->height = 0;
            return;
        } else {
            printf("\nError: Memory Allocation Fail");
            return;
        }
    }

    if (key < (*n)->key){
        insert(&((*n)->left), key);
    }else{
        insert(&((*n)->right), key);
    }

    (*n)->height = max(getHeight((*n)->left), getHeight((*n)->right)) + 1;

    printf("\nHeight of %d is updated to %d",(*n)->key, (*n)->height);

    if(getBalanceFactor(*n) > 1){

        if(getBalanceFactor((*n)->left) < 0)
            rotateLeft(&(*n));

            rotateRight(&(*n));
    }
    else if(getBalanceFactor(*n) < -1){

        if(getBalanceFactor((*n)->right) > 0)
            rotateRight(&(*n));

        rotateLeft(&(*n));
    }
}

void rotateRight(node **n){
    node *lChild, *subtree;

    lChild = (*n)->left;
    subtree = lChild->right;

    // Rotate Right
    printf("\nRotating Right");
    lChild->right = *n;
    (*n)->left = subtree;

    // Update Height
    lChild->height = max(getHeight(lChild->left), getHeight(lChild->right)) + 1;
    (*n)->height = max(getHeight((*n)->left), getHeight((*n)->right)) + 1;
}

void rotateLeft(node **n){
    node *rChild, *subtree;

    rChild = (*n)->right;
    subtree = rChild->left;

    // Rotate Left
    printf("\nRotating Left");
    rChild->left = *n;
    (*n)->right = subtree;

    // Update Height
    rChild->height = max(getHeight(rChild->left), getHeight(rChild->right)) + 1;
    (*n)->height = max(getHeight((*n)->left), getHeight((*n)->right)) + 1;
}

I have fixed this code.

Here is the link: Pastebin

Answer 1

In debugging graph algorithms, sketching what they do often helps. For example, in your right rotation step:

START         -->    lChild->right = *n;  -->    (*n)->left = subtree;
----------------------------------------------------------------------

       *n                   *n                          *n
lChild        -->    lChild               -->    subtree
     subtree              *n                  

You loose lChild..

Answer 2

I figured it out. Thanks for @Philip for pointing this out.

The reason why I lose some items in the tree is because I forgot to assign the value of lChild / rChild to *n in the rotation functions;

This Code:

// Rotate Right
lChild->right = *n;
(*n)->left = subtree;

Should Be:

// Rotate Right
lChild->right = *n;
(*n)->left = subtree;
(*n) = lChild;