4.6.2 [New] Optimal Binary Search Tree Successful and Unsuccessful Probability - Dynamic Programming

the topic is optimal binary search tree already I have one video on this but in that video I have just considered successful search probabilities and in this video I will be considering successful search as well as unsuccessful search probability so I will cover it as a very fresh topic so the contents of this video are these first of all I'll explain what does it mean by binary search tree and how do we search how it is useful for searching then what does it mean by cost of searching then next I will explain the probabilities for search what does it mean and also I will explain what is optimal binary search tree and how to know its cost then I will show you the dynamic programming approach for constructing a optimal binary search tree for a given set of keys or given set of elements then that approach I will show you how to derive the formula for dynamic programming then I will take a problem and solve then finally we will see how our optimal binary search tree can be constructed by using dynamic programming approach so in this video I will be deriving everything so here you have to observe and learn how to devise a solution by using dynamic programming approach see most of the students want to learn dynamic programming so for learning practice is important so by picking a few problems if you study them in detail and understand how the solution is given then you can give a solution to any new problem right it's not that somebody is explaining all the problems then you know the solutions it's not like that see if you know the approach for few problems then you take up a new problem and try to solve it by yourself so here I'll give you a complete approach everything I will show you in detail she'll get the clear-cut idea how the approach is taken and you can see the observe the minor details also in this problem alright so this will help you of a lot if you are really interested in dynamic programming and solving challenging problems let us start with the topic here I have a example binary search train this is a binary tree and these are keys the nodes are containing keys right and the keys are arranged such that for any node if you take all the smaller keys are on the left-hand side all the larger keys are on its right-hand side so if you look at this 40 all these keys on the left side of 40 that is 10 20 30 are smaller than 40 and after that on the right hand side these keys are greater than 40 and similarly if you take 60 this 50 is is smaller on the left hand side 70 is greater that's on the right hand side why why we have arranged the keys like this see it gives a advantage for searching how let us see I want to search for 30 how to search start from route this is the route of a node is it 30 no then when I should look for 30 on the left hand side because 30 is smaller than this 40 so definitely it will be on the left hand side go to the left hand side is it 30 no 30 is greater than this one so greater than 20 so definitely it should be on the right hand side because we have erased the keys like that so go to rights ideas thirties funk so in this way we can search for any element for searching for 30 how many comparisons we have done 1 2 3 so the element is found in three comparisons if you check total I have 7 elements and in that 7 element searching for any element that is 30 has taken three comparisons let us observe what about others see if I am searching for a 10 it will take 3 comparisons and for 20 it will take two comparisons and for 40 it will take only one comparison 33 comparison 62 comparison 53 comparison so what is the maximum comparison the maximum comparisons are 3 that is the height of our binary search tree and that also I can call it as levels of binary search tree this is the first level second level and this is the third level so the number of comparisons required for searching any element in a binary search tree depends on number of levels in a binary search tree now let us learn one more thing see we were searching for the keys that are present here so and they were found so this is called as successful search now let us assume I am searching for a key that is nine let us search is it nine no is it nine I should go on the left hand side is it nine nine is smaller than this go on left said is it nine no nine is less than this go on this side there is nothing this is null doesn't end so nine is not found because I have reached till the end of a binary search tree and the key element is not found so if a key element is not found then search is unsuccessful all right then in this also how many comparisons I have done maximum I have done three comparisons I have checked here and here and here so when you are searching in a binary search tree there are two possibilities like the element is found or element is not found let us strive on more element I want to search for key element 47 let us start is it 47 no 47 is greater good right side is it 47 no 47 is smaller than this go to left side is it 47 no 47 is smaller than this go to this side there is nothing and so search is unsuccessful so search will be successful also search may be unsuccessful also right so in both the cases we need to know the amount of comparisons that we are doing and that amount of comparison is nothing but the cost of searching in a binary search tree now one more thing industry if you observe there are circular nodes and these are square nodes I have drawn them in smaller size right so those are square nodes what they are doing here do they have keys no they don't have keys then what they are representing they are representing all those keys that are for unsuccessful search let us see what does it mean see if I am searching for a key that is 11 so 11 11 in smaller levels smaller than this and greater than this it will come this side so 411 it has terminated here then 12 so 12 it is smaller than this smaller than this but greater than this here so it will come on the right-hand side so it will come in here so if I search for the key is from 11 to 19 it will be coming on this side only so I'll just make it as 11 to 19 this is representing this node is representing all the unsuccessful search keys from 11 to 19 then what about this this is representing all the keys from minus infinity to 9 so if you search for any number less than 10 search will terminate here so we will not compare here we'll stop our comparisons here but we'll reach here go to left side null and we'll stop so that you can call it as null Square nodes are nulls also that null is representing all those keys for which search will be unsuccessful then similarly all these are representing not one value the set of keys for which search may be unsuccessful if you see this last one this is repenting representing 71 to positive infinity 71 to positive infinity then once you search greater than 70 in this binary search tree the search will terminate here so we have seen unsuccessful search are also represented as dummy nodes just to show that this is having set of unsuccessful search keys so now we learn one thing that in a binary search tree search may be successful or unsuccessful in both cases we have to perform some comparisons and reach the result that keys found or keys not found so that's all these are the basic things that I was supposed to give you so I have given it now next thing here I have three keys three keys for three keys I have a constructed binary search tree so if you check all these are binary search trees just pause the video and check all these are binary search trees so what I have to say here is that for same set of keys there can be many possible binary search tree if you want to know the count how many are possible here I have given the formula for and the keys like here we have three keys 2 into n C of n then plus divided by n plus 1 then that 3 I have kept here so this is true into 3 this is 2 n means 2 into 3 C 3 by 3 plus 1 so this becomes 6 C 3 by 4 and answer is 5 so you can calculate this so for 3 Keys 5 different binary switches are possible and here are those 5 binary search trees so if you have more keys then more binary search trees are possible now if you observe here the cost of searching like there I have shown you the cost of searching the maximum comparisons were 3 right but here if you observe the maximum comparisons are 3 maximum are 3 maximum are two oh this is better this binary search tree is better so if you search for any key you can get the key in less number of time less amount of time less number of comparison and this is more this is more so the idea is for the same set of keys when you can have multiple binary search trees one of the binary search tree may be giving you best results that is minimum number of comparisons so that's it we prefer that binary search tree so we want a binary search tree which requires less number of comparison for searching any key element so if you look at this example I have a 7 keys I have arranged them like this now how many binary search trees are possible for 7 keys you put 7 here in the formula and calculated so many binary search trees are possible alright and one of the binary search tree I haven't quickly draw it here so if you take 70 as root and 6 has left child and then its left child 50 then its left child 40 then its left child 30 then 20 and 1 so this is also my nearest versity for same set of 7 keys now here if you see how many levels are there 1 2 3 4 5 6 7 levels are there so maximum how many comparisons required for searching any key 7 comparisons sorry so the cost is high so it means that if the hydrophobic search tree is less then the number of comparisons will be less and so height plays an important role for searching right so one thing we learn the height of a binary search tree should be minimum now next I will show you what does it mean by probability that is successful search or unsuccessful search probability I'll discuss about this for explaining successful search and unsuccessful search probabilities I have an example let us look at this see I have four keys right and using those four keys I have drawn different binary search trees also for four keys 14 different binary searches are possible but I did not draw all you can try them all if you want I have taken just three binary search trees now first important thing there are four keys and these black nodes are square no sorry presenting unsuccessful search how many are there one two three four five so if there are four keys there are five square nodes so if there are n keys there will be n plus 1 square nodes yes so there are four keys and four plus 1 that is 5 square nodes now let us talk about probability so for talking about probability I will take an example see if you are assume that you are running a store a shop and you have lot of items to sell right a small shop then how you have arranged the items in your shop few are on the counter right at the entrance point only and few are inside the shelf and some few are deeper inside your shop and some of some of the items you have kept them in stock room right so which items are easily reachable the one that are there in the front counter at the that is sales counter or billing counter that are easily reachable right and the one in the stock room will take time for fetching those items so how do you keep these items so you keep these items because depends on the frequency of their sale so that frequency is nothing but probability of their sale so those items who are having high probability of selling you'll keep them in the on the building counter the items which are having lease probability they are there inside the stock room right so that's how he arrays the items so same way these keys are nothing but the items and we are searching for them right fetching them or looking for them is nothing but searching like suppose you have a lot of items on your sale building down there somebody asks for something then you say huh here is the item so that's what you are searching so you want to arrange them such that they can fetch in less amount of time so the cost of searching should be less and one more thing you are considering here is that our customer is asking for something which you will search and find that no it's not available it's sort of stock so that also you want to consider you want to consider what is the frequency that people are asking for a few things which are not present in the shop so successful search probability as well as unsuccessful search probability right so what is the possibility based on that you will arrange the thing see if somebody some customer is asking and you are going into a stockroom and checking and coming back and saying it's not there so it will take more time right so if the unsuccessful probability is high then such things you assume they are there in the counter near the counter it's not there right quickly you can say check in the stockroom no no I know it's not there because we keep it here only if it's there so that's what so the frequency of successful search and unsuccessful search both are important so I have the keys here so if you see I have given the probabilities both success and search probability and unsuccessful search probability if you sum of all of them I have taken in decimals right point because the final probability should be 1 if you add all these that will be 1 ok so the final probability is 1 so that is distributed among successful so an unsuccessful search for various keys this is the successful search probability for key 10 so let us call this as p1 probably and this is probability - probability 3 probability for that is for the fourth key then unsuccessful search we have one extra let us call this as a q1 for unsuccessful search q2 q3 q4 one is extra so this we call it as q0 so we have started from 0 to 4 right now there are 5 you can say that why do you start from 1 you start from why don't you start from 1 if I start from 1 then I have to give this as 5 so that will be greater than the key for right we have fourth key only so that's why I have started from 0 so 0 to 4 and that is from 1 to 4 so if you look at like once again see this is the probability of searching 10 then what is this the probability of searching anything that is less than 10 so that minus infinity to 9 and this is the successful search probability of searching for T so that is the chances that a customer is coming for a key 40 assume like this then what are the chances that he is coming for anything above 40 so that is from 41 to infinity this 1.05 is the probability so this is not representing just one element it is representing set of elements or set of keys that is representing just a particular key that's it this is about the successful search an unsuccessful search probability now we need to know the cost of searching so for cause I have please here see this is our example 3 and if you take the reverse this is level 1 level 2 and this is 4 is at level 3 so I have taken levels also and for each node that is for key I have taken its probability I have mentioned it that is point 1 point 2 point 1 and point 2 then I have 4 square nodes also I have the probabilities now I want to know the cost of searching based on successful search and unsuccessful search probabilities so let us find out the cost so what is the cost of searching this one it is at level one so just one comparison one into 0.2 plus what is the cost of searching 10 that is 0.1 so and it's at level 2 so it is 2 into into one right then for 30 I will take number of comparisons require I to because it's at level 2 so 2 into 0.1 plus 4 this require 3 comparison so 3 into 0.2 so for successful search keys I have taken this plus I should continue but I will not do there I will do it here plus right now for unsuccessful search point 1 but how many comparison see level 1 level 2 this is not level 3 right don't take it as level 3 because we don't compare we stop here only we stop over a comparison here only and try to go on left side and say key is not there that work that saw its unsuccessful search only 2 comparison so what is the level if you take I should take its level as 3 right so this is along with the 40 and these are at level 4 so we don't take its level but level -1 one less level minus 1 so this is 2 into and its probability is 0.1 plus then this is 2 into point 0 5 plus 2 into 0.15 plus this is for this this is for C actually I should draw them like this I should draw them till here till 40 ok I should draw them here till 40 so this is point 1 and this is 0.5 0.2 0.2 side level 3 they are at level 3 then what about these nodes these are at level 4 so this is so 4 into point zero 5 and Plus this is also 4 into point zero 5 okay see this square know also they are also at some level but we don't consider their level we will consider one lesser than their level so this is the total so what will be the total if I multiply and an ADD this will be equal to oh I have written this as 4 this is actually 3 right so this is 3 into so these are at 4th level these are at fourth level but the number of comparison stops here we have stopped we have to stop here that is level 3 so it should be 3 and if I multiply this and add the result will be 2 point 1 so this is the of searching in this binary search tree by considering successful search probabilities as well as unsuccessful so it's probabilities right where for every key we have taken its level as the number of comparison for unsuccessful search we have taken its level minus one Hotel level minus 1 whatever is level minus 1 so this should be extended till here I have drawn them in small size ok so level minus 1 we take so this how we got the cost now I will not calculate this so you can do it by yourself just remember that this is at level 1 this is at level 2 and these have to be at a level 3 okay these are at level 3 this is level 3 and these are at level 4 so we don't take it for for this we take 3 only for this we don't they get 3 we take 2 only because these are not reachable we are not reaching them we are not comparing there so for this also you find out the cost now let us write on the formula for this cost so how I have found out the cost is cost is 4 Keys 1 2 4 but here 0 is included so let us write 0 also 0 before so what for 0 is because the unsuccessful search probabilities are starting from 0 onwards we write 0 otherwise the keys are studying from 1 only but we write 0 also so this cost is we have multiplied every probability of a key with its level probability of any key is multiplied with level of that key value right so for key I will say a I that is identifier or a elements are ABC I am calling them as keys but let us write it as e or high then plus what about the unsuccessful search probabilities so that also the QI value is multiplied with level of these are called as a square nodes are called as external nodes so let us call it as e I but we don't take its actual level like this level was a 3 but we have taken 2 for this one so this is minus 1 so this level should be one less and this I have to do some mission of all this so let us say this is Sigma where I takes the values starting from 1 to N and here the I value will start from 0 to n right so here it is not 4 it is n let us make it as 4 n so this is from 1 to n that is from 0 to n this is the formula so what I have done I have multiplied the probability with level probability with level so probability with level and unsuccessful search also probability with level probability with level so the probability with level this also I have to sum up this also have to sum up so this is the cost formula for finding the cost of a existing binary search tree already we have a binary search tree and we know the probabilities we want to know the cost so this is the formula all right so now next we'll move to the next step that is we will learn what does it mean by optimal binary search tree C assume that we have the keys here and for every key there is a successful search probability as well as unsuccessful search probabilities these are given then we have to find a binary search tree such that the cost of searching the cost of searching this one here if you remember we got the cost as two point one that should be minimized minimize it means this formula should be minimized yes the formula of cost should be minimum this should be minimum the cost for this one depends on the height of a binary search tree which key is at which level if you observe root is 20 here root is 30 and here it is 40 and here 30 is at a level 2 and here 30 is at level 1 and 30 is at level 3 so I have kept them at different places so if you find the cost you will find the differences in the cost you will not get cost us two point one for this one also and this one also you may get different cost so as I said for four keys 14 binary search trees are possible 14 are possible now we want the best binary search tree for this the cost is minimized for that a tree the cost is minimized means this cost should be minimized so how a tree should be constructed so now I will reframe the statement now a problem of optimal binary search tree is if the keys and their probabilities are given we have to generate a binary search tree generate a binary search tree such that the cost is minimum the cost is minimum this is the problem now what should be the solution see for solution it means for four keys 14 different trees are possible I should draw all 14 trees and find out the cost for each tree then I should select the one which is giving minimum cost they should be the approach but this is very time-consuming you remember for n nodes these many trees are possible to NZ n by n plus 1 so for 4 keys for entries are possible so if I have 40 keys then imagine is it practical that you try all possible binary search trees and find their cost and select the minimum one no it's not possible but is it possible that we find out the best tree without generating all of them may be possible so that's what dynamic programming approach will try to give you a easier faster method for trying out all possible binary search trees and picking up the best one without trying all of them without trying all of them so imagine if you try all how much time it will take so we will try all of them but not directly indirectly so that is the benefit of dynamic programming approach that is the strength of DP that you will try all of them but not directly indirectly so how it can be done in this problem let us learn so I will remove this and I will start explaining about dynamic programming approach for optimal - first tree I have even the formula here now for using this formula for 3 keys just 3 keys that is from 0 to 3 I have taken here then how we can use this formula for a generating optimal binary search T so we have to substitute the values in this formula so let us do this one so from this I will explain you what should be the approach for solving this problem just watch it carefully from 0 to 3 K can take the values from greater than 0 to less than equal to 3 mins ki can take the values 1 & 2 & 3 so I will substitute all of them and from that I should take the minimum so this should be C of 0 to 0 that is K minus 1 so what is K right now 1 so K is 1 means this is 0 plus C of 1 2 3 this is the first substitution comma this is comma now K I will take it as 2 so if I take a K as 2 then this is 0 and K is 2 months 2 minus 1 is 1 then plus C of K is 2 2 then J is 3 here right J is 3 3 this is the second value of K I have taken comma now third value of K I will take that is K should be 3 so it will be K minus 1 that will be 2 so this is C of 0 2 2 plus C of 3 2 3 then this completes all possible K values K values can be 1 2 3 so I have taken this this is for 1 this is for 2 this is for 3 so here you can see the K value write this term is K this this value is K so this is K this is K so this is K minus 1 actually now at last we have to take W of 0 to 3 so whatever the minimum that you get in that we can add that rate of 0 to 3 now from this when I can know the answer for this one C of 0 comma 0 that is cost of 0 comma 0 it will be nothing that will be 0 only and similarly C of 3 comma 3 it will be 0 only what what about this I should know this value I should know this one I should know this one so if I know these values I can substitute them and I can get the minimum then it will give us what should be Roo okay okay and this w of zero to three is nothing but sum of all the probabilities successful as well as unsuccessful altogether right now I should know this right so if I have to find out this one I'll try to expand it here only just watch so if I try to expand here see off one two three this is nothing but a minimum of K takes the values greater than one and less than equal to three so what are the possible values of K K can take the value greater than one means two as well as three so this has to be C of first of all K values 2 so this will be 1 comma 1 plus C of 2 comma 3 and next value is K value I will take it as 3 so this will be C of 1 comma 2 plus C of 3 comma 3 then plus weight of 0 1 comma 3 1 comma 3 1 so from this you can see that just to know this value again if I expand I have to know more values I should know 1 comma 1 and 3 comma 3 also then this is only for this one then I should know this value and this value and this value this value that's 2 to 0 to 2 so so many values I should know if I expand them then they will expand like anything so for finding the cost of 0 to 3 this is the formula in this I don't know these values so I should find out these values and this again can be done using formula again it expands like anything and from this again if I take 2 comma 3 again it will expand like something so if I want these values I should trust know these values so that's that is the point that is the point so it means for knowing the answer for a larger value I should know the value for answer for smaller values first like these are smaller so you can see that this was from 0 to 3 and it became 1 to 3 so it is reducing so if I know first smaller values then we can substitute and get done so then I can get the larger value yes this is what the approach dynamic say takes for solving the problems so if you expand all these formulas and see then what are the values that we need I will list them here so from this basically you need C of 0 0 C of 1 1 C of to do right and C of 3 3 you should know these values you some of them you can see here 0 0 1 1 3 3 2 2 will also come if you expand any one then after that you also should know that is 0 to 1 with a gap of 1 that is C of 1 to 2 and C of 2 to 3 this is a gap of 1 see the difference between these two was 0 now difference is 1 then C of 0 to 2 and C of 1 2 3 the gap differences to here then finally you can know C of 0 2 3 so first find out these from that you can know these from that you can know these values then finally you can know so it means to solve the this formula you should solve this a smaller formula for this formula you should solve this a smaller formula so if you already have smaller values you can substitute and put them back and get that fans final answer that's what we need the values so these values we need so if you observe and say that this is I and this is G difference between I and J is 0 here so J minus is 0 here here J minus I is 1 and here J minus I is 2 and here J minus I is 3 so I should find out the values fit the difference of zero a difference of 1 and difference of 2 and difference of 3 I do because always I will be less than J right always I will be less than J that's why I'm not getting all possible combinations just I am getting this much so if you know these values then you can get done sorry 1 dancer for this one so now we will not be using formula will be filling table and that table we know very well that it is from the formula only so when we solve the problem we will fill the table now one more thing in this one apart from finding the cost we should also know who is giving us minimum means which came out of these three KS which K gives minimum cost from that we will select it as a root so we should monitor that also observe that one also then also in the formula we have weight values so how to know the weight see if you observe if you take weight of 0 comma 2 and weight of 0 comma 3 then what is the difference see these are the weights so if you take 0 comma 2 and Z comma 0 comma 3 what is the difference so what is this Q 0 plus P 1 plus Q 1 plus P 2 plus Q 2 what about this Q 0 plus P 1 plus Q 1 P 2 plus Q 2 plus P 3 plus Q 3 right so if you observe these two then this is same in this one and only p3q trees added so weight of 0 comma 3 can be taken as weight of a 0 comma 2 plus P 3 Q 3 right so it means weight of any I comma J can be taken as weight of I comma this is J minus 1 J minus 1 plus okay J minus 1 plus pj QJ so this is how we can modify the values of W so it means if you form the one of the W value you can know the next value by this Smith hurt right so if you already know 0 comma 2 you can easily find 0 comma 3 so finally I can say that we have to find out cost weight for the formula plus who should be a root so now I have explained you what should be the approach now I will take an example problem and I will solve it let us take a problem and solve it using the formula we have already seen and although I have given you the approach now I will solve this problem and also I will construct a a binary search tree that is optimal binary search tree so let us look at the problem first of all see there are four keys given 10 20 30 40 right and these are successful search probabilities right or firstly second third and fourth key and these are unsuccessful search probabilities that are q' eyes that are studying from zero onwards like one extra unsuccessful search probability will be there so this is zero one two three four actually the probabilities should be in decimal point probability should not be greater than one right these are in decimal point but working with the decimal point will be difficult so actually if you add all of them total is sixteen so if you divide them by sixteen every value by sixteen you will get the actual probability so they are multiplied by 16 to get the integer number so that you can easily calculate them now for solving as I told you the approach I have taken all the values the weight and the cost and the root who should be a root so all these values are filled here and this is 0 0 1 1 two 2 three 3 four 4 difference between I and J is 0 0 1 1 2 2 3 3 4 difference between I and J is 1 & 2 & 3 & 4 I have to fill up this table finally I need the cost for 0 to 4 that is for keys are there so 0 to 4 is here so if I can get this answer then I got dancer IV not using the formula directly but indirectly I am using the formula by filling this tip let us fill up the values so first of all W value I will fill up see W of 0 comma 0 is Q 0 plus nothing is there right zq 0 will be there so it means 0 comma 0 is Q 0 W of 1 comma 1 is Q 1 plus nothing is there one is the last one starting from 1 and ending at 1 so this is just Q 1 so it means this W of 0 comma 0 is this is 2 and this is 3 1 comma 1 is 1 and this is 1 and 1 and this is also 1 okay 2 3 1 1 1 so W values are just first Q values so that is failed and what about the cost cost of 0 comma 0 so cost of 0 comma 0 if you take K takes the values from greater than 0 greater than 0 means fun but less than equal to this 1 so there is no K value possible so these costs are zeros so initial values are all zeros these are all zeros all right so these are all zeros that is filled first row is filled now mixable this one for this first of all I will find out the W values then I will show you cost and the root vanish roofs also I meet them and 0 here now here W of 0 comma 1 so if you remember I have shown you that W of I comma J is nothing but the value of I comma J minus 1 plus PJ and QJ right so W of 0 comma 1 will be W of 0 and J minus 1 is 0 plus P 1 plus Q 1 so this I can obtain this I can obtain from this 1 0 comma 1 I can obtain from 0 comma 0 0 comma 1 I can obtain from 0 comma 0 so this plus P 1 Q 1 these are P 1 Q 1 3 plus 3 6 and this 8 and if I take this for this 1 this is 2 1 comma 2 so P to Q 2 so 3 plus 1 right 3 plus 1 4 5 6 7 this is 7 and this man 2 comma 3 2 comma 2 plus P 3 Q T 1 plus 1 plus 1 total 3 total 3 that is 2 and this is 1 now this 1 3 comma 3 3 comma 4 so 1 plus 4 comma 4 so 1 plus 1 right 2 and that is 1 3 so this is 3 w values I have filled them like this now even I can fill up all these values to W values so let us finish them ok I'll fill up all these values then I will fill up cost of the root so rate we can be already known this is 8 is there then 2 comma 2 have to fill up that is 3 plus 1 4 8 plus 4 is 2 and 7 plus 2 is 9 then 3 plus 2 is 5 then next this one too Plus 3 3 3 3 is 2 so this is 14 and this is 4 comma 4 so 9 plus 2 is 11 and then this one 1 comma 4 then this one is 16 14 plus 2 16 so W values already have filled them by using this formula this formula you can see this is the formula right now I have to find out cost so I should start from here I will find all these cost and I will fill up them all so roots so let us do it let us find C of 0 comma 1 so for that first of all I will write down the formula right so you should look at the formula from that we will do it this is minimum of K takes values greater than I in less than equal to J and this is C of I comma K minus 1 plus C of K 2 J and outside the bracket is W of I J right this is the formula now keeping this formula I will be using that for finding all the values let us start C of 0 comma 1 so here I write C of 0 comma 1 s minimum of K takes the values greater than 0 less than or equal to 1 so what are the possible values of K greater than 0 minus 1 1 2 1 so only one value it can take so this will be C of I s 0 K I said it is 1 so 1 minus 1 is 0 plus C k K's what 1 K is 1 and a j j is what 1 plus so outside the bracket we have plus w of i comma j i comma j is 0 comma 1 0 comma 1 this is what the formula we caught so as there is only one value so that is only the minimum value so let us find out minimum of do I have the C of 0 comma 0 yes it is 0 0 then C of 1 comma 1 yes I have 0 0 plus weight of 0 comma 1 weight of 0 comma 1 as a here we have eight eight then what is the minimum of this zero only so this is zero plus eight is eight so cost of zero comma one as eight first value we got if they observe in this fun only K value one value is possible only one value is possible so here this is becoming zero zero this is becoming one one right now let us try for C of 1 comma 2 1 comma 2 I will find out this fun so what I will do is I will just modify it okay 1 comma 2 this is 1 this is 2 and this is 1 this is 2 K can take the values greater than 1 less than equal to 2 so only 2 it can take then this is C of I I is what 1 K minus 1 2 minus 1 1 C of k k is a 2 2 and c of j j is 2 so this is 1 comma 1 2 comma 2 and a weight of 1 comma 2 weight of 1 comma 2 so C of 1 1 0 C of 2 2 0 minimum of 0 is 0 only right weight of 1 2 is 7 this is not 8 this is 7 this one right now add this what is the result 0 plus 7 is a 7 so I got the same value here so this means that if I try for C of 2 3 also I'll get rate only because there is only 1 K very possible and that we are getting 0 only so this will be same 3 3 I see the time I have observed that it is coming same thing so I have directly written the value so I've saved the time now 1 2 3 4 5 6 values I have to find out next 0 to 2 let us find out 0 to 2 I'll remove this and I'll find out 0 to 2 now what should be the root values here see the minimum value here the minimum K value was 1 here we have taken as 1 K here we have taken as 2 and here 3 here 4 now here in this one you cannot see the difference next level when I find the values for these that time you can find out how we are getting a root value okay so just I have written 1 2 3 4 just leave it okay now let us find out C of 0 comma 2 so this will be little nd C of 0 comma 2 minimum of K takes the values greater than 0 less than or equal to 2 so what are the values K can take 1 and 2 2 values it can take so in this I should take K as 1 as well as a K as 2 2 times I have to try this form so let us take C of 0 comma K as 1 1 and 1 means 1 minus 1 0 plus C of K is 1 1 comma 2 this is I this is J remember this and right now K is 1 we are taking 1 so this I have finished now K as a 2 we will take 2 in this one you substitute 2 2 here C of 0 2 minus 1 is 1 plus C of 2 comma J is 2 2 comma 2 then outside this weight of that is 0 comma 2 so let us substitute the values and see minimum of C 0 0 from here and I got the value C I am finding this one and for this I should know this value that is helping me already know I know the value then I can use it here that's what C of 0 is 0 is 0 C of 1 comma 2 as a77 plus C of 0 comma 1 C of 0 comma 1 is 8 8 plus C of 2 comma 2 2 comma 2 is 0 0 okay then plus weight of 0 comma 2 rate of 0 comma 2 is how much 12 this is 12 so this is minimum of right which is cinnamon 7s minimum what was the value of K here if you remember K I have taken as 1 here kay I have taken a stew here yes Kay as one has given me the minimum value so this is seven and plus 2l so this is 19 and the K value is 1 so I'm filling up was here this is 19 and who should be rude minimum one should be rude so who was minimum K was 1 K is 1 that's it so that's how whoever is giving minimum value that we will take here and most of the dynamic programming problem we do it like this only whichever value is giving minimum that we will take it there now I will not fill up find out these you can follow this formula and you can do it I'll fill up these values then I will find out these three values finally okay these three values so let me remove this and find out C of 0 3 if you want to see the value this value is 22 and this is 8 3 so if you follow this method and get danced and you get those answer I'll remove this and find 0 comma 3 C of 0 comma 3 that is minimum of K takes the values greater than 0 less than or equal to 3 so what are the K values possible first time K value can be 1 or 2 or 3 3 values are possible so if I put one there then it will be C of 0 0 plus C of 1 3 then next is comma next value is C of 0 1 plus C of 2 3 comma C of 0 2 plus C of 3 3 here K value is 1 K values 2 K values 3 I have tried all of them then out of all these whatever the result we get in that I have to add W of 0 3 let us put the values here so I will directly put the value below this 1 this is 0 and 1 comma 3 is how much 12 so this is 12 this 0 comma 1 is 8 and 2 comma 3 2 comma 3 is here that is 3 okay then 0 comma 2 0 comma 2 is 19 and 3 comma 3 is 0 so if I put the radish I'll separately put them here minimum of zero plus 2l s 2 l comma 8 plus 3 that is 11 then 19 okay then plus W of 0 comma 3 0 comma 3 is 14 so out of this which is smaller this one for which value of K 2 so what is balanced 11 plus 14 is 25 so this is 25 who gave 25 which value of K has given 25 the value of K which has given 25 is 2 so write 2 here for saving time I'll leave it you find out whatever the value you get you put it then finally I'll do it for this one so daddy I will write an answer this is 19 comma 2 okay just like this you have to start from 2 onwards not from 1 onwards because this is 1 to 4 so 2 3 4 k value can be 2 3 4 substitute and you can get it now let us try this one C of 0 4 so what are our values K can take case should take the values greater than 0 less than equal to 4 cz this is 0 right if it is 1 greater than 1 okay so whatever the initial value is so K can take the values 1 2 3 and 4 so 4 values are possible so in this formula I should try at all so first will be C of 0 0 plus C off this is even ah so what is the one for right C of 0 1 then this will be 2 4 okay then this is C of 0 2 and C of 3 4 then comma comma C of a 0 3 plus C of 4 for right then plus weight of 0 4 here I have taken the K value as 1 & 2 & 3 & 4 right so let us put the values and get dancer C C 0 0 is a 0 plus C 1 for C 1 comma 4 is 19 so total is 19 this 1 is 19 then C of 0 1 C of 0 1 is 8 see off to 4c off to 4 is 8 so this will be 16 C of 0 to s 19 plus C off or 3/4 C off 3 comma 4 s 3 3 so this is 22 then C of 0 3 s 35 25 plus C of 4 4 is 0 this will be 25 so if I take minimum off right this is how much 19 comma 16 kamat 22 comma 25 and plus weight of 0 for how much it is 16 and which is minimum this one for each value of K we got this as minimum 2 so this K value is true so answer is how much 16 plus 16 32 so answer is 32 32 and what is the root who has given us minimum value K value as 2 has given given us minimum well this is true that's it so he got the table filled by using the formula if you observe we have started from the smaller values when we got a larger value so the efforts that repeat putting in here or less if we would have started from here it was difficult to solve we could not have solved it easily so when we are calculating some higher value this lower values are useful because already we have calculated them so this approach we call it as table or approach to dynamic programming follows tabular approach so it starts from lower values to higher values now we have the complete data available the cost of a tray we got a 32 so as I said that the probabilities are multiplied by 16 and kept there to avoid decimal values so this result should be divided by 16 so 32 by 16 cost is 2 so the minimum cost of our optimal binary search tree is true so if you observe this we are always taking minimum so it means we are taking the one which is giving us best result are we trying on so if you start from the lower values and reach the higher value if you can see that we tried all possible roots we are trying all possible routes as I said in the beginning that we should try out all possible binary search trees and pick up the best one so yes we have tried all possible binary search tree row should be fast key or second key or third or fourth key this one it should be so that we get the minimum so we got 16 plus 16 32 who gave minimum 2 so based on the cost we are deciding so indirectly we are trying out all possible binary search trees now last thing what should be the tree so from this data we already have the data now we can take the decisions and form a optimal binary search tree so I will remove this and I'll form optimal binary search tree for these he is 10 20 30 and 40 let us generate the optimal binary search tree for what case 1 2 3 4 so we have to find out root 4 keys from 0 to 4 y 0 yes this unsuccessful search probability start from 0 for everything we have started from 0 so root is also 0 to 4 okay now for 0 to 4 in the table do you have any value you got the value which gives minimum yes - so rude should be to 2 mins second key that is 20 so I will write 20 here 20 so if you remember in the formula when a root is a second key here the second key right root is 2 so the left hand side value will come this side right hand side values goes on that side so what comes on this side so I'll write down this one Rudolf zero to K is a 2 here right so this should be 1 and K is a 2 here so this should be 2 - 4 if you remember whatever the key is left hand side is I to K minus 1 this is K 2 J right same method same based on the formula now here I have 0 to 1 and this is 2 to 4 so as a 2 is a root so only one key is left on side on the left hand side now what is a 0 comma 1 in the table our office here o comma 1 in the table is 1 yes first key what is the first key 110 so here key value is what 10 and case 1 so we have taken decision how we have decided who should be in the root table gave us so we give a we got a decision we have taken a decision based on the data that we have now 2 comma 4 who should be wrote 2 comma formants we have how many keys now that is 30 and 42 keys are there which one should be rude table will tell you based on the table data you take the decision 2 comma 4 so 2 comma 4 is here root of 2 comma 4 is 3 this is 3 third key so which is the third key 30 so who is a k here k is a 3 as per this value then 40 where it will go on this right hand side so right hand side there is only one key remaining I will not write on these values so I will directly fill up this right hand side that is 40 only one key is remaining right so I started from 0 to 4 so 0 is on this side 2 to 4 on that side 0 to 1 gave me one key so this is finished I stop there and 2 to 4 gave me one key so I stopped here because only one key is remaining and 40 definitely come on the right hand side so already I have to come in if you want to see this further as K is the key is a 3 so on this side if you take this is our of 2 comma 2 and this is R of 3 comma 4 so who is our of 3 comma 4 that is 4 yes we got 4 so no need of this this is the null value right that is external node so this is the tree so this is our optimal binary search tree with 20 in the root then on the left side 30 on the right side 40 on the right side so this is the optimal binary search tree based on the successful search or unsuccessful search probabilities this is the optimal binary search tree which takes minimum cost all right so as if we tried all possible binary search trees and we have taken the best one it is just like that if you see the approach we have taken we have found out all possibilities and took the minimum one so this is the approach of dynamic programming and we have solved one of the problem using than programming now if you have similar problems see that if it matches with this one then you can apply the same strategy there that's it so that's all in this video

Channel: Abdul Bari

Views: 166,875

Rating: 4.9129362 out of 5

Keywords: binary search tree, obst

Id: wAy6nDMPYAE

Length: 56min 59sec (3419 seconds)

Published: Tue Apr 02 2019