struct node { int key ; int h; node *left; node *root; node *right; }; int h(struct node* x) { if (x == NULL) return 0; return x->h; } int balanceavl(struct node *n) { if (n == NULL) return 0; return (h(n->left) , h(n->right)); } node* rightrotate(struct node *y) { struct node *x = y->left; struct node *z = x->right; x->right = y; y->left = z; y->h = max(h(y->left), h(y->right))+1; x->h = max(h(x->left), h(x->right))+1; return x; } node* leftrotate(struct node *x) { struct node *y = x->right; struct node *z = y->left; y->left = x; x->right = z; y->h = max(h(y->left), h(y->right))+1; x->h = max(h(x->left), h(x->right))+1; return y; } struct node *remove(struct node *root, int key) { struct node *remove_node; if (root == NULL) { return root; } if ( key < root->key) { root->left = remove(root->left, key); } else if ( key > root->key) { root->right = remove(root->right,key); } else { if ((root->left == NULL) && (root->right != NULL)){ remove_node = root->right; *root = *remove_node; free(remove_node); // this is for free-ing the memory } else if ((root->right == NULL) && (root->left != NULL)){ remove_node = root->left; *root = *remove_node; free(remove_node); } else if ((root->right == NULL) && (root->left == NULL)){ remove_node = root; root = NULL; } else { remove_node = successor(root); root->key = remove_node->key; root->right = remove(root->right, remove_node->key); } } if (root == NULL) { return root; //lr if (balanceavl(root) == 2){ if (balanceavl(root->left) == -1) { root->left = leftrotate(root->left); return rightrotate(root); //ll } else if (balanceavl(root->left) == 1) { return rightrotate(root); } } //rr if (balanceavl(root) == -2) { if (balanceavl(root->right) == -1) { return leftrotate(root); } //rl else if (balanceavl(root->right) == 1) { root->right = rightrotate(root->right); return leftrotate(root); } } } return root; }
node* successor(struct node *x)
var
This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)