Insert Avl
Tnode* insert(Tnode *root, int item)
{
    if (root == NULL) {
        Tnode *new_root = malloc(sizeof(Tnode));
        if (new_root == NULL) {
            printf("can't allocate memory\n");
        }
        else {
            new_root->data = item;
            new_root->hight = 0;
            new_root->left = new_root->right = NULL;
        }
        return new_root;
    }
    else if (item <= root->data) {         
        root->left = insert(root->left);               // root->left might change after insert node to root->left
        if (Hight(root->left) - Hight(root->right) == 2) {       // after inserting, left and right subtree might be unbalanced
            if (item <= root->left->data)          // item is inserted to root->left->left ==> SRL case
                root = SRL(root);
            else                          // item is inserted to root->left->right ==> DRL case
                root = DRL(root);
        }
    }
    else if (item > root->data) {
        root->right = insert(root->right);
        if (Hight(root->right) - Hight(root->left) == 2) {
            if (item > root->right->data)
                root = SRR(root);
            else
                root = DRR(root);
        }
    }
    root->hight = Max(Hight(root->left), Hight(root->right)) + 1;    // update the hight of root, since subtree might change
    return root;
}
int Hight(Tnode *root)
{
    if (root == NULL)
        return -1;                         // if node == NULL, return hight = -1; hight of leaf node = 0;
    else 
        return root->hight;
}

Note

Insert() requires at most 1 time rebalancing operation, while Delete() might require many times.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License