/* * Code example for CP264 Data Structures II * AVL tree insert and delete operations, using recursive algorithms, * adapted from http://www.geeksforgeeks.org/avl-tree-set-2-deletion/ * HBF */ #include #include // define AVL tree node typedef struct node { int key; int height; struct node *left; struct node *right; } tnode; tnode *new_node(int key); void print_preorder(tnode *root); void print_tree(tnode *root, int prelen); tnode *insert(tnode *root, int key); tnode *delete(tnode *root, int key); tnode *get_smallest_node(tnode* root); int max(int a, int b); int height(tnode *root); tnode *rotate_right(tnode *y); tnode *rotate_left(tnode *x); int balance_factor(tnode *n); /* driver program to test above functions */ int main() { tnode *root = NULL; /* Constructing tree given in the above figure */ root = insert(root, 9); root = insert(root, 5); root = insert(root, 10); root = insert(root, 0); root = insert(root, 6); root = insert(root, 11); root = insert(root, -1); root = insert(root, 1); root = insert(root, 2); /* The constructed AVL Tree would be 9 / \ 1 10 / \ \ 0 5 11 / / \ -1 2 6 */ print_tree(root, 0); printf("\nPreorder traversal of the constructed AVL tree is \n"); print_preorder(root); root = delete(root, 10); /* The AVL Tree after deletion of 10 1 / \ 0 9 / / \ -1 5 11 / \ 2 6 */ printf("\nafter deletion of 10\n"); print_tree(root, 0); printf("\nPreorder traversal after deletion of 10 \n"); print_preorder(root); return 0; } // A utility function to get maximum of two integers int max(int a, int b) { return (a > b)? a : b; } // A utility function to get height of the tree int height(tnode *root) { if (root == NULL) return 0; else return root->height; } tnode *new_node(int key) { tnode* node = (tnode*) malloc(sizeof(tnode)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; return(node); } tnode *rotate_right(tnode *y) { tnode *x = y->left; tnode *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->height = max(height(y->left), height(y->right))+1; x->height = max(height(x->left), height(x->right))+1; // Return new root return x; } tnode *rotate_left(tnode *x) { tnode *y = x->right; tnode *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->height = max(height(x->left), height(x->right))+1; y->height = max(height(y->left), height(y->right))+1; // Return new root return y; } int balance_factor(tnode *np) { if (np == NULL) return 0; return height(np->left) - height(np->right); } tnode *insert(tnode *root, int key) { /* 1. Perform the normal BST rotation */ if (root == NULL) return(new_node(key)); if (key < root->key) root->left = insert(root->left, key); else if (key > root->key) root->right = insert(root->right, key); else // Equal keys not allowed return root; /* 2. Update height of this ancestor node */ root->height = 1 + max(height(root->left), height(root->right)); /* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */ int bf = balance_factor(root); // If this node becomes unbalanced, then there are 4 cases // Case 1 if (bf == 2 && balance_factor(root->left) >= 0) { return rotate_right(root); } // Case 2 if (bf == 2 && balance_factor(root->left) < 0) { root->left = rotate_left(root->left); return rotate_right(root); } // Case 3 if (bf == -2 && balance_factor(root->right) <= 0) return rotate_left(root); // Case 4 if (bf == -2 && balance_factor(root->right) > 0) { root->right = rotate_right(root->right); return rotate_left(root); } return root; } tnode *get_smallest_node(tnode *root) { tnode *tnp = root; while (tnp->left != NULL) tnp = tnp->left; return tnp; } tnode *delete(tnode* root, int key) { // STEP 1: PERFORM STANDARD BST DELETE if (root == NULL) return root; if ( key < root->key ) root->left = delete(root->left, key); else if( key > root->key ) root->right = delete(root->right, key); else // key == root->key { // node with only one child or no child if( (root->left == NULL) || (root->right == NULL) ) { tnode *temp = root->left ? root->left : root->right; // No child case if (temp == NULL) { temp = root; root = NULL; } else // One child case { *root = *temp; // Copy the contents of } // the non-empty child free(temp); } else { // node with two children: Get the inorder // successor (smallest in the right subtree) tnode* temp = get_smallest_node(root->right); // Copy the inorder successor's data to this node root->key = temp->key; // Delete the inorder successor root->right = delete(root->right, temp->key); } } // If the tree had only one node then return if (root == NULL) return root; // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE root->height = 1 + max(height(root->left), height(root->right)); // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to // check whether this node became unbalanced) int bf = balance_factor(root); // If this node becomes unbalanced, then there are 4 cases // Case 1 if (bf == 2 && balance_factor(root->left) >= 0) { return rotate_right(root); } // Case 2 if (bf == 2 && balance_factor(root->left) < 0) { root->left = rotate_left(root->left); return rotate_right(root); } // Case 3 if (bf== -2 && balance_factor(root->right) <= 0) return rotate_left(root); // Case 4 if (bf == -2 && balance_factor(root->right) > 0) { root->right = rotate_right(root->right); return rotate_left(root); } return root; } void print_preorder(tnode *root) { if(root != NULL) { printf("%d ", root->key); print_preorder(root->left); print_preorder(root->right); } } void print_tree(tnode *root, int prelen) { int i; if (root != NULL) { for (i = 0; i < prelen; i++) printf("%c", ' '); printf("%s", "|___"); printf("%d\n", root->key); print_tree(root->right, prelen + 4); print_tree(root->left, prelen + 4); } } /* |___9 |___10 |___11 |___1 |___5 |___6 |___2 |___0 |___-1 Preorder traversal of the constructed AVL tree is 9 1 0 -1 5 2 6 10 11 after deletion of 10 |___1 |___9 |___11 |___5 |___6 |___2 |___0 |___-1 Preorder traversal after deletion of 10 1 0 -1 9 5 2 6 11 */