AVL Tree Insertion

gistfile1.txt

/* Node is defined as :
typedef struct node
{
    int val;
    struct node* left;
    struct node* right;
    int ht;
} node; */

node * new_node (int val)
{
    node * n = new node;
    n->val = val;
    n->ht = 0;
    n->left = n->right = NULL;
    return n;
}

int ht(node * root)
{
    if(root) {
        return 1 + max(ht(root->left), ht(root->right));
    }
    return -1;
}

void update(node * root)
{
    if(root) {
        root->ht = 1 + max(ht(root->left), ht(root->right));
    }
}

node * lrot(node * root)
{
    node * newParent = root->right;
    root->right = newParent->left;
    newParent->left = root;
    update(newParent);
    update(root);
    return newParent;
}

node * rrot(node * root)
{
    node * newParent = root->left;
    root->left = newParent->right;
    newParent->right = root;
    update(newParent);
    update(root);
    return newParent;
}

node * LLC(node * root)
{
    return rrot(root);
}

node * LRC(node * root)
{
    root->left = lrot(root->left);
    return LLC(root);
}

node * RRC(node * root)
{
    return lrot(root);
}

node * RLC(node * root)
{
    root->right = rrot(root->right);
    return RRC(root);
}

node * balance(node * root)
{
    int bf = ht(root->right) - ht(root->left);
    if(bf == -2 && root->left != NULL) {
        bf = ht(root->left->right) - ht(root->left->left);
        if(bf <= 0) {
            return LLC(root); 
        } else {
            return LRC(root);
        }
    } else if(bf == 2 && root->right != NULL) {
        bf = ht(root->right->right) - ht(root->right->left);
        if(bf >= 0) {
            return RRC(root);
        } else {
            return RLC(root);           
        }
    }
    return root;
}

node * insert(node * root, int val)
{
    if(root == NULL) {
        return new_node(val);
    }
    if(root->val > val)
        root->left = insert(root->left, val);
    else if(root->val < val)
        root->right = insert(root->right, val);
    update(root);
    return balance(root);
}