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.

page revision: 7, last edited: 02 May 2010 20:03