Deletion Operation on Binary Search Tree - Part 1| | Mr.Srinivas

hi everyone welcome to nourish technologies this is Ramos so in the last session we discussed how to insert an element in a binary search tree now in this session we'll discuss so deletion operation on binary search tree okay deletion in a binary search tree deletion in binary search tree how can we delete and what are the chances to delete so first suppose here some of the nodes I am writing some of the nodes 5050 and here it is a 60 here it is 70 here it is a 55 so 40 and next 130 this is so first one so what are the chances to delete means first one is a deleting a leaf node delete a leaf node having no children delete a leaf node having no children how to delete it for example this is the node is a leaf node there is no left children left is a null and there is no right children right is a null how to delete means are very simple directly so we can delete this one how delete this one we can free just here it is it to the parent node left side we should write it as a null then automatically link will be disconnected so that we can free this one so deleting a leaf node having no children is very easy no left children no right children this is the first one and second one second one suppose 50 30 20 and here it is 60 70 and here it is 65 deletion of a node leaf node leaf node having one child single child chances day single jet that is this is the target this is I want to delete how to delete this node if you want to delete this node so we need to connect this node to this one so where we have to connect so that is also important here after deleting this node after deleting this node 65 we need to connect to right left child of 70 left child of 70 is a 65 should be connected to right side to this parent this is a parent right this is the current you want to delete this current clearly I am writing this is parent and this is current node that what you want to delete current to left current to left will be stored in to pair into right right side because 65 is a greater value than 16 so that is parent to right so actually so much code is there that I explained very clearly programmatically but this is only just theoretically how many possibilities are there in the deletion of a particular node from the binary search tree okay so node is having no children node is having a single child so suppose I want to delete a node is having two child two children right again how many possibilities are there see how to delete a node is having two children again here it is a so many chances for example so 50 40 30 here it is 60 70 here it is 80 here it is 65 65 and remember one thing and so many options are they for example here it is a select 6262 here it is a 6767 and here it is a 90 and here it is a 95 here it is a 85 and here it is a 75 so many options are there suppose if you want to delete a node is having two children left children is present and right children is present if two children's are present this is a target target deleting a node having having two children two children then after deletion of this 70 so with which node we need to replace 65 or 80 it is not a 65 and it is not a 80 why right after deleting this node suppose if you write a 65 here observe this 65 if you write here 67 is connected left side to 65 that is violation of a binary search tree insertion rule greater values always a right side lesser values always a left side so then which with which value we have to replace with which node we have to replace very simple two options you have either highest value in a right subtree I mean left subtree this is a left subtree highest value highest value here what is the highest value in the left subtree 67 or a list value in a right sub-tree list value in a right subtree what is the list value is a seventy-five seventy-five is a list value whenever you are deleting a node is having two children deleted node deleted node replaced with either highest value in a left subtree or least value list value in a right subtree in a right subtree stew options so then only binary search tree rules will be satisfied so then only binary search tree rules will be satisfied either highest value in a left subtree 67 suppose after deleting 70 if you place a 67 this delete one now happy because 67 see lesser value 65-62 right and suppose I am not replacing with the 70 I am not replacing with the 67 67 as usual it is place in the right subtree list value what is the least value 75 75 I am replacing happy so 75 lesser value 65 60 to 67 left side right side 80 90 85 95 these are okay so this is simply how to delete a node is having two children one is a left children and second one is a right child okay so now I'll explain how to delete a leaf node so first I will draw the diagram right nodes diagram and then I will explain now we are writing in the form of nodes some of the nodes we are writing some of the values like 50 60 55 here it is a 40 30 35 so connections thousand node addresses these are the node values so left children is the two thousand is connected right children is present three thousand is connected left children is there five thousand is connected and here it is a left children is there four thousand connected and this one this one here it is a six thousand six thousand so we are connecting simply six thousand here we are connecting so null value null null remaining all our null locations now I want to delete a node having no children two things you have to understand so whatever the node you want to delete the target target this is current current is a six thousand six thousand next this is it should be pointing by parent parent is a four thousand so how can we find out a parent node current node right in case of insertion we discussed very clearly and how to search with the help of parent and current also that I will explain okay here suppose I want to delete this node very simple to the parent whether it is connected to left side or right side you have to check is connected to left child left side or right side nothing but if if current is current is water 6000 current is equals to is equals to pair into two right means what is this connected to right side here into pair into right then what we have to write so deletion of this one means 6000 is pointing here you have to write a null value now here null value pair into right equals to null air into right equals to null or else if current is equals to parent to right condition false so what is the situation look at this suppose just considered this is parent parent is a 3000 and this is current current is a 5000 now current is connected to parent to left side right so now current is connected to parent to right is failed in this case so parent will after that is else block directly parent to left is equals to null pair into left we need to store null in the if block this one in place of 6000 it will place null it will stop pointing in case of this one here it is in a else block null value will be placed to parent to left here it is null will place null and it will be deleted it will be deleted now finally we need to delete this one because no one is pointing very simple just free of current free of current so whenever you write a free of current then automatically this node will be deleted this node will be deleted so this is a simple logic how to delete right a node is having no children okay here it is first we need to check current is connected to parent or right side or we're into left side if it is connected to parent to right side make parent to right equals to null or parent to left equals to null why strict rule if you want to delete any node right so first we should delete all the connections which are pointing to that node from anywhere in all the locations you have to place null so then only we can call a free function on that okay and how to delete a node is having a single child a node is having the two children that we will see in the next session okay for more videos please subscribe to nourish id channel thank you

Channel: Naresh i Technologies

Views: 131,840

Keywords: Data Structures, Srinivas, Naresh IT, Learn Data Structures, Hands on Data Structures Training, Data Structures Demo, Online Data Structures Training, Data Structures Tutorial Videos, Data Structures Overview, Data Structures Interview Questions

Id: fEb__4Te_gk

Length: 14min 37sec (877 seconds)

Published: Thu Oct 20 2016