DATA STRUCTURES
AND ALGORITHMS
IMPLEMENTATION OF TREES &
BINARY SEARCH TREE
➢1
DELETION IN BST
When we delete a node, we need to consider how
we take care of the children of the deleted node.
This has to be done such that the property of the
search tree is maintained.
➢2
IMPLEMENTING A BST
Deleteion
➢To delete a node x from a BST, we have three cases:
✓x is leaf
✓x has one child
✓x has two children
➢3
IMPLEMENTING A BST
CASE 1:
▪ x is a leaf
Simply make the appropriate pointer in x’s parent a null pointer
75
60 80
x 58 65 92
➢4
IMPLEMENTING A BST
➢Make the left pointer of x’s parent null
➢Free x
75
60 80
x 58 65 92
➢5
IMPLEMENTING A BST
CASE II:
▪ x is has one child
Set the appropriate pointer in x’s parent to point to this child
75
60 80
58 65 x 92
62
➢6
IMPLEMENTING A BST
75
60 80
58 65 x 92
62
➢7
IMPLEMENTING A BST
CASE III:
▪ x has two children
✓Replace the value stored in node x by its inorder successor.
✓Delete this successor
➢8
IMPLEMENTING A BST
G
F J x
A
H O
I M P
xSucc K N
L ➢9
IMPLEMENTING A BST
G
F K x
A
H O
I M P
xSucc K N
L ➢10
IMPLEMENTING A BST
G
F K x
A
H O
I M P
xSucc K N
L ➢11
DELETION CODE
void DeleteNode(Node* temp, int num){
if (temp==NULL)
cout<<"Number not Found";
else if((temp->data == num)){ //node found
Node *parent, *min ;
int number;
// if number is found at a leaf node
if((temp->left == NULL) && (temp->right == NULL)){
parent=GetParent(root, temp->data);
if(parent->left == temp)
parent->left= NULL;
else if (parent->right == temp)
parent->right = NULL;
delete temp;
}
➢12
SCENARIO: if(temp->left != NULL)
Temp could be a right son Temp could be a left son
75 75
parent 60 80 parent 60 80
58 65 temp 92 temp 58 65 92
62 52
if(parent->left == temp)
parent->left = temp->left;
if (parent->right == temp)
➢13
parent->right = temp->left;
// if node to be deleted has one child
else if(((temp->left == NULL) && (temp->right != NULL)) ||
((temp->left != NULL) && (temp->right == NULL))){
parent = GetParent(root, temp->data);
if(temp->left != NULL){
if(parent->left == temp)
parent->left = temp->left;
else if (parent->right == temp)
parent->right = temp->left;
}
➢14
}
SCENARIO: if(temp->right != NULL)
Temp could be a right son Temp could be a left son
75 75
parent 60 80 parent 60 80
58 65 temp 92 temp 58 65 92
66 59
if(parent->left == temp)
parent->left = temp->right;
if (parent->right == temp)
➢15
parent->right = temp->right;
// if node to be deleted has one child
else if(((temp->left == NULL) && (temp->right != NULL)) ||
((temp->left != NULL) && (temp->right == NULL))){
parent = GetParent(root, temp->data);
if(temp->left != NULL){
if(parent->left == temp)
parent->left = temp->left;
else if (parent->right == temp)
parent->right = temp->left;
}
else if(temp->right != NULL){
if(parent->left == temp)
parent->left = temp->right;
else if (parent->right == temp)
parent->right = temp->right;
}
delete temp; ➢16
}
//if node to be deleted has two children
else if((temp->LTree != NULL) && (temp->RTree != NULL))
{
min = FindMin(temp->RTree);//will return the min. node found in
Rtree
number = min->data;
DeleteNode(temp->RTree, min->data); //calling to itself
recursively
temp->data= number;
}
} // end node found
else if (num < temp->data)
DeleteNode(temp->LTree, num); //calling to itself
recursively
else //if (num > temp->data)
DeleteNode(temp->RTree, num); //calling to itself recursively
➢17
}
