Deleting in an AVL Tree
- Perform the same steps as deleting in a binary search tree.
- After that, assign new height to the node.
- Check the balance factor of the node.
- According to the balance of the node and it's left/right child, perform rotation in order to balance the balance the tree
struct Node *deleteNode(struct Node *ptr , int key) {
// If there's no node to be deleted
if (ptr == NULL)
return NULL;
// If the node is a leaf node
if (ptr -> left == NULL && ptr -> right == NULL) {
// If it's the root node, make root NULL after deletion
if (ptr == root)
root = NULL;
// Free the memory
free(ptr);
return NULL;
}
// If value to be deleted is lesser, go to left subtree
if (key < ptr -> data)
ptr -> left = deleteNode(ptr -> left, key);
// If value to be deleted is greater, go to right subtree
else if (key > ptr -> data)
ptr -> right = deleteNode(ptr -> right, key);
// Deleting the node once it's found
else {
// Delete from the subtree which has greater height
if (nodeHeight(ptr -> left) > nodeHeight(ptr -> right)) {
// Find the inorder predecessor for left subtree
struct Node *inPre = inorderPredecessor(ptr -> left);
ptr -> data = inPre -> data;
ptr -> left = deleteNode(ptr -> left, inPre -> data);
} else {
// Find the inorder successor for right subtree
struct Node *inSuc = inorderSuccessor(ptr -> right);
ptr -> data = inSuc -> data;
ptr -> right = deleteNode(ptr -> right, inSuc -> data);
}
}
// Set new height
ptr->height = nodeHeight(ptr);
// Rotate as per balance factor
if(balanceFactor(ptr) == 2 && balanceFactor(ptr -> left) == 1)
return LLRotation(ptr); //L 1 Rotation
else if(balanceFactor(ptr) == 2 && balanceFactor(ptr -> left)==-1)
return LRRotation(ptr); //L -1 Rotation
else if(balanceFactor(ptr) == 2 && balanceFactor(ptr -> left) == 0)
return LLRotation(ptr); //L 0 Rotation
else if(balanceFactor(ptr) == 2 && balanceFactor(ptr -> right) == 1)
return RRRotation(ptr); //R 1 Rotation
else if(balanceFactor(ptr) == 2 && balanceFactor(ptr -> right) == -1)
return RLRotation(ptr); //R-1 Rotation
else if(balanceFactor(ptr) == 2 && balanceFactor(ptr -> right) == 0)
return RRRotation(ptr); //R 0 Rotation
return ptr;
}
Utility Functions :
// Node height function
int nodeHeight(struct Node *ptr) {
int leftHeight, rightHeight;
leftHeight = ptr && ptr -> left ? ptr -> left -> height : 0;
rightHeight = ptr && ptr -> right ? ptr -> right -> height : 0;
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// Balance factor function
int balanceFactor(struct Node *ptr) {
int leftHeight, rightHeight;
leftHeight = ptr && ptr -> left ? ptr -> left -> height : 0;
rightHeight = ptr && ptr -> right ? ptr -> right -> height : 0;
return leftHeight - rightHeight;
}
// LL Rotation
struct Node *LLRotation(struct Node *ptr) {
struct Node *ptrL = ptr -> left;
struct Node *ptrLR = ptrL -> right;
ptrL -> right = ptr;
ptr -> left = ptrLR;
ptr -> height = nodeHeight(ptr);
ptrL -> height = nodeHeight(ptr -> left);
if (ptr == root)
root = ptrL;
return ptrL;
}
// LR Rotation
struct Node *LRRotation(struct Node *ptr) {
struct Node *ptrL = ptr -> left;
struct Node *ptrLR = ptrL -> right;
ptrL -> right = ptrLR -> left;
ptr -> left = ptrLR -> right;
ptrLR -> left = ptrL;
ptrLR -> right = ptr;
ptr -> height = nodeHeight(ptr);
ptrL -> height = nodeHeight(ptrL);
ptrLR -> height = nodeHeight(ptrLR);
if (ptr == root)
root = ptrLR;
return ptrLR;
}
// RR Rotation
struct Node *RRRotation(struct Node *ptr) {
struct Node *ptrR = ptr -> right;
struct Node *ptrRL = ptrR -> left;
ptrR -> left = ptr;
ptr -> right = ptrRL;
ptr -> height = nodeHeight(ptr);
ptrR -> height = nodeHeight(ptr -> right);
if (ptr == root)
root = ptrR;
return ptrR;
}
// RL Rotation
struct Node *RLRotation(struct Node *ptr) {
struct Node *ptrR = ptr -> right;
struct Node *ptrRL = ptrR -> left;
ptrR -> left = ptrRL -> right;
ptr -> right = ptrRL -> left;
ptrRL -> left = ptr;
ptrRL -> right = ptrR;
ptr -> height = nodeHeight(ptr);
ptrR -> height = nodeHeight(ptrR);
ptrRL -> height = nodeHeight(ptrRL);
if (ptr == root)
root = ptrRL;
return ptrRL;
}
Contributed by Nitin Ranganath
Last modified 3yr ago