Deletion in Threaded Binary Tree
Now lets see deletion of threaded binary tree;
For deletion we have to consider three cases:
CASE-1 : Node to be deleted is a leaf node.
CASE-2 : Node to be deleted has only one child.
CASE-3 : Node to be deleted has two children
Lets discuss each case in detail
CASE-1 : Node to be deleted is a leaf node
Again we have two cases :
CASE-A If the leaf Node is to be deleted is left child of its parent then after deletion, left pointer of parent should become a thread pointing to its predecessor of the parent Node after deletion.
CASE-B If the leaf Node to be deleted is right child of its parent then after deletion, right pointer of parent should become a thread pointing to its successor.
C++ Program for case-1 deletion
struct Node* Case_1(struct Node* root , struct Node* par ,struct Node* ptr )
{
if (par == NULL)
root = NULL;
else if (ptr == par->left) {
par->lthread = true;
par->left = ptr->left;
}
else {
par->rthread = true;
par->right = ptr->right;
}
free(ptr);
return root;
}
CASE-2 Node to be deleted has only one child
If Node to be deleted has left subtree, then after deletion right thread of its predecessor should point to its successor.
If Node to be deleted has right subtree, then after deletion left thread of its successor should point to its prredecessor.
C++ program for case-2 deletion
struct Node* Case_2( struct Node* root, struct Node* par, struct Node* ptr )
{
struct Node* child;
if (ptr->lthread == false)
child = ptr->left;
else
child = ptr->right;
if (par == NULL)
root = child;
else if (ptr == par->left)
par->left = child;
else
par->right = child;
Node* s = inordersuccessor (ptr);
Node* p = inorderpedecessor (ptr);
if (ptr->lthread == false)
p->right = s;
else {
if (ptr->rthread == false)
s->left = p;
}
free(ptr);
return root;
};
CASE-3 Node to be deleted has 2 Children
We find inorder successor of Node ptr (Node to be deleted) and then copy the information of this successor into Node ptr. After this inorder successor Node is deleted using either Case A or Case B.
C++ Program for Case-3 deletion
struct Node* Case_3(struct Node* root, struct Node* par, struct Node* ptr)
{
struct Node* parsucc = ptr;
struct Node* succ = ptr->right;
while (succ->left != NULL) {
parsucc = succ;
succ = succ->left;
}
ptr->data = succ->data;
if (succ->lthread == true && succ->rthread == true)
root = Case_1(root, parsucc, succ);
else
root = Case_2(root, parsucc, succ);
return root; }
Now , first we have to find the node in the tree and then different cases are applied to the node to be deleted
C++ program for finding key node and then calling different function to delete that node
struct Node* delete_Node( struct Node *root, int key)
{
struct Node *parent= NULL;
struct Node *ptr= root;
bool found = false;
while( ptr != NULL)
{
if(ptr -> data == key )
{
found = true;
break;
}
parent = ptr;
if ( key < ptr -> data)
{
if(ptr -> lthread == false)
ptr = ptr -> left;
else
break;
}
else
{
if( ptr -> rthread == false)
ptr = ptr -> right;
else
break;
}
}
if( found == false)
cout<<"Data is not present in the tree\n";
else{
if(ptr -> lthread == false && ptr -> rthread == false )
root= Case_3(root, parent, ptr);
else if(ptr -> lthread == true && ptr -> rthread == false )
root= Case_2(root, parent, ptr);
else if(ptr -> lthread == false && ptr -> rthread == true )
root= Case_2(root, parent, ptr);
else if(ptr -> lthread == true && ptr -> rthread == true )
root= Case_1(root, parent, ptr);
}
}
Comments