Introduction
This post elaborates how we can delete any node in a binary search tree and maintain its binary search tree property.Problem statement
Given a number K and a binary search tree, delete the node with value K and also maintain the binary search tree property.Analysis
First problem is to locate the the node. Once the node is located, there are three cases to be considered before we delete the node.
If the given node is leaf node. Straight forward, delete the node.
For example, tree is like given below and we need to delete 4.
It would be deletion of node 4 and setting the left child of 6 as NULL.
Case 2 :
If the node is not leaf node and there is right sub tree to it. In this we would replace the deleted node by the in-order successor of the node in BST. Free the in-order successor node.
Let’s say in the above tree we need to delete 15. Node 15 has a right sub tree. We would first find the in-order successor of the node 15 and replace node 15 with that element, in this case, it is 17. And then we will free the node 17. Output will look like this.
Case 3:
If the node is not leaf but does not have right sub tree, then we link the parent of the given node with the left child of the node.
Let’s consider we need to delete 17 now. Since the node as left sub tree, we need to connect the parent of the node to the left sub tree of the node. So now node 10’s right child will be 13. Note that here we cannot replace 17 with 13 and delete 13 as 13 might have its own children.
Output will be
Complete code
void delete_node(Node *root, int K, Node *parent){
if(!root)
return ;
if(root->value == K){
//Case 1. If the node is leaf node
if(!root->left && !root->right){
if(parent && parent->left == root){
parent->left = NULL;
}
if(parent && parent->right == root){
parent->right = NULL;
}
free(root);
return;
}
//Case 2. If there is right sub tree
if(root->right){
Node * temp =
inorder_success_mod(root, root->value);
if(temp){
root->value = temp->value;
free(temp);
}
return;
}
if(root->left){
if(parent && parent->left == root){
parent->left = root->left;
}
if(parent && parent->right == root){
parent->right = root->left;
}
free(root);
return;
}
}
if(root->value > K){
delete_node(root->left, K, root);
}
else{
delete_node(root->right, K, root);
} return ;
}
Node *inorder_success_mod(Node *root, int K){
Node * successor = NULL;
Node *current = root;
Node *prev = NULL;
if(!root)
return NULL;
while(current->value != K){
if(current->value >K){
successor = current;
prev = current;
current= current->left;
}
else{
prev = current;
current = current->right;
}
}
if(current && current->right){
successor = find_minimum_mod(current->right, &prev);
}
if(prev && prev->right == successor)
prev->right = NULL;
else if(prev && prev->left == successor)
prev->left = NULL;
return successor;
}
Node * find_minimum(Node *root){
if(!root)
return NULL;
while(root->left){
root = root->left;
}
return root;
}
Execution
This execution is based on following tree:
Enter the number : 12
In-order before deletion : 10, 12, 20, 30, 37, 40, 45,
Since 30 is greater than 12, moving to left sub-tree
Since 20 is greater than 12, moving to left sub-tree
Since 10 is less than 12, moving to right sub-tree
Case 1 :Deleting 12
In-order after deletion : 10, 20, 30, 37, 40, 45,
Enter the number : 20
In-order before deletion : 10, 12, 20, 30, 37, 40, 45,
Since 30 is greater than 20, moving to left sub-tree
Case 3 : Deleting 20
In-order after deletion : 10, 12, 30, 37, 40, 45,
Enter the number : 30
In-order before deletion : 10, 12, 20, 30, 37, 40, 45,
Case 2 : Deleting 37
In-order after deletion : 10, 12, 20, 37, 40, 45,
Complexity analysis
To locate any node in a BST is O(logN) given that tree is not completely skewed where the complexity becomes O(N). Once we locate the node, finding in-order successor is the costliest operation among three cases which can be done in O(logN). Hence the complexity of of overall algorithm will be O(logN).
0 comments:
Post a Comment