A node to be deleted can belong to one of the below 4 cases :
Case 1: Node to be deleted is having 2 children
1. By inorder succcessor(leftmost child of right subtree of keynode)
Algorithm
- Find parent of inorder successor of node to be deleted.(keynode)
- Replace keys of inorder successor and node to be deleted.
- Make changes to parent of inorder successor of keynode.
Diagram
Delete 6
6 7
/ \ / \
4 9 ------------> 4 9
/ /
7 8
\
8
1. Inorder successor of 6(node to be deleted) = 7
Parent of inorder successor(7) = 9
2. 7 is left child of 9.
3. Replace keys 7 and 6.
4. Make left pointer of 9 point to right pointer of 7.
2. By inorder predecessor(rightmost child of left subtree of keynode)
Case 2: Node to be deleted is a leaf node(a node having no children)
1.If node to be deleted is left child of its parent then simply make parent’s left child as NULL.
Diagram
Delete 4
6 6
/ \ \
4 9 ------------> 9
4 is left child of its parent.So make left pointer of its parent(6) as NULL.
2.If node to be deleted is right child of its parent then simply make parent’s right child as NULL.
Diagram
Delete 9
6 6
/ \ /
4 9 ------------> 4
9 is right child of its parent.So make right pointer of its parent(6) as NULL.Case 3: Node to be deleted is having only left child
1.If node to be deleted is left child of its parent then simply make node to be deleted’s left child as left child of parent.
Diagram
Diagram
Delete 4
6 6
/ \ / \
4 9 ------------> 3 9
/
3
4 is left child of its parent.So make left pointer of its parent(6)
point to node to be deleted(4)'s left child (3) .
2.If keynode is right child of its parent then simply make node to be deleted’s left child as right child of parent.
Diagram
Diagram
Delete 9
6 6
/ \ / \
4 9 ------------> 4 8
/
8
9 is right child of its parent.So make right pointer of its parent(6)
point to node to be deleted(9) 's left child (8) .
Case 4: Node to be deleted is having only right child
1.If node to be deleted is left child of its parent then simply make node to be deleted’s right child as left child of parent.
Diagram
Delete 4
6 6
/ \ / \
4 9 ------------> 5 9
\
5
4 is left child of its parent.So make left pointer of its parent(6)
point to node to be deleted(9) 's right child (5) .
2.If node to be deleted is right child of its parent then simply make node to be deleted’s right child as right child of parent.
Diagram
Delete 9
6 6
/ \ / \
4 9 ------------> 4 12
\
12
9 is right child of its parent.So make right pointer of its parent(6)
point to node to be deleted(9) 's right child (12) .Code :
Functions used :
- node* search_node_find_parent(node* root,node** par_of_keynode,int key)
- Finds location of keynode and returns it.
- Also finds location of parent of keynode.
node* search_node_find_parent(node* root,node** par_of_keynode,int key)
{
node* keynode = root;
while(key!=keynode->key && keynode!=NULL)
{
while(key<keynode->key && keynode!=NULL)
{
*par_of_keynode = keynode;
keynode = keynode->left;
}
while(key>keynode->key && keynode!=NULL)
{
*par_of_keynode = keynode;
keynode = keynode->right;
}
}
return keynode;
}let key to be deleted = 7
*par_of_keynode = NULL 6<----keynode
/ \
4 9
/
7
6<-----*par_of_keynode
/ \
4 9<------keynode
/
7
6
/ \
4 9<-----*par_of_keynode
/
7<------keynode
Finds location of parent of inorder successor of keynode and returns it.
node* find_parent_of_in_succ(node* keynode)
{
node* par_of_in_succ = keynode,*in_succ = keynode->right;
if(in_succ->left!=NULL)
{
while(in_succ->left!=NULL)
{
par_of_in_succ = in_succ;
in_succ = in_succ->left;
}
}
return par_of_in_succ;
}Let keynode point to 6 (node to be deleted)
6<---keynode,par_of_in_succ 6<----keynode
/ \ / \
4 9<-----in_succ 4 9<-------par_of_in_succ
/ /
7 7<----in_succ
3. node* replace_key(node* root,node* keynode,node* par)
- Replaces keynode’s key with with key of its inorder successor.
- Makes necessary changes to parent of inorder successor.
node* replace_key(node* root,node* keynode,node* par_of_in_succ)
{
node* in_succ;
if(par_of_in_succ == keynode)
{
in_succ = par_of_in_succ->right;
keynode->key = in_succ->key;
par_of_in_succ->right = in_succ->right;
}
else
{
in_succ = par_of_in_succ->left;
keynode->key = in_succ->key;
par_of_in_succ->left = in_succ->right;
}
free(in_succ);
return root;
}
4. node* del(node* root,int key)
- Deletes a node
node* del(node* root)
{
node* keynode,*par_of_in_succ,*par_of_keynode = NULL;int key;
do
{
printf("\n Enter key to delete ");
scanf("%d",&key);
keynode = search_node_find_parent(root,&par_of_keynode,key);
if(keynode == NULL)
printf("\n Key not found");
else
{
if(keynode->left!=NULL && keynode->right!=NULL) //node with 2 children
{
par_of_in_succ = find_parent_of_in_succ(keynode);
replace_key(root,keynode,par_of_in_succ);
}
else if(keynode->left==NULL && keynode->right==NULL) //leaf node
{
if(keynode==par_of_keynode->left)
par_of_keynode->left = NULL;
else if(keynode==par_of_keynode->right)
par_of_keynode->right = NULL;
else
root = NULL;
free(keynode);
}
else if(keynode->right==NULL) //node with left child
{
if(keynode==par_of_keynode->left)
par_of_keynode->left = keynode->left;
else if(keynode==par_of_keynode->right)
par_of_keynode->right = keynode->left;
else
root = keynode->left;
free(keynode);
}
else //node with right child
{
if(keynode==par_of_keynode->left)
par_of_keynode->left = keynode->right;
else if(keynode==par_of_keynode->right)
par_of_keynode->right = keynode->right;
else
root = keynode->right;
free(keynode);
}
printf("\n Key successfully deleted");
}
printf("\n Delete more nodes ? ");
fflush(stdin);
}while(getchar()=='y');
return root;
}
No comments:
Post a Comment