4.6 Optimal Binary Search Tree (Successful Search Only) - Dynamic Programming

the problem is optimal binary search tree in this video I am going to talk about what is binary search tree then what does it mean by optimal binary search tree the problem then the dynamic programming approach for solving this problem so I take an example and I will solve it and I will also use the formula and show you how the formula is generated my focus will be on showing you how dynamic programming is working on this problem right instead of just showing you a shortcut how to fill up the table and get the answer let us start with binary search tree see if the set of keys are given here and the purpose is to search the keys if already I have the list of elements and I want to search some element so there are different search methods like linear search and binary search and also we have a data structure called binary tree can we utilize a binary tree for searching purpose let us see I will arrange these elements in the form of a binary tree so I will create a binary tree out of these elements so I'll keep root as 40 and twentieths left child and 10 as its left child and 30 here 60 50 and 70 now you can see that the elements are arranged such that for any node all the elements on its left hand side are smaller all the elements on its right-hand side are larger for 40 all these elements are larger and for this 60 this element is larger than this element is smaller likewise here also so the benefit of arrange this type of binary tree is that it is useful for searching suppose I want to search for a key element shift D then I can start from here is it 50 new 50 is greater than this one so definitely it is on the right hand side go here and check it is it 50 no the key value what I am searching is smaller than this one so go on the left hand side yes key is found so that's all what is the time taken for searching a key element the maximum time will be if the element is in the leaf so what is the amount of time so this is height of a tree and the height of our binary tree is minimum login and this is minimum height only so the time taken for searching in a binary search tree is login now one more thing we have to consider here when I am searching for the key like 50 I got the key suppose I am searching for a key element that is 45 is it there no if I search for it 45 is greater and 45 smaller than 60 45 is less than 50 so my search will terminate here and the search is unsuccessful so search may be successful or search you may not be successful that is it may be unsuccessful when you are searching for the keys now next I will show you for a given set of element how many different binary search trees are possible I have taken just 3 keys let us see how many different binary search trees are possible so for these 3 keys 10 as a root and 20 as its right child and 30 here so 10 30 and 20 on this side 20 10 and 30 on this side so for 3 keys there are 5 different binary search tree is possible right so for any keys how many different binary search trees are possible to and see n by n plus 1 binary searches are possible so for 3 this will be 2 into 3 C 3 by 3 plus 1 this will be 5 so 5 different biased ratios are possible for 3 keys for n number of keys these monies are possible you will see what is the cost of searching it in each tray see the cost is dependent on the number of comparison required for searching for a key element so in this tree if I am searching for this key element that the cost is 1 if I search for this one then I have to make 2 comparisons and if I have to search for this one I have to make 3 comparison so what is the average number of comparison average number of comparisons are there are total 3 nodes so this by three that is true likewise if I consider all of them then this is 1 and this is 2 and this is 3 so this is 1 plus 2 plus 3 that is 6 by 3 that is true and here it is 1 and this is 2 and this is 2 so this is 5 by 3 so this is less than 2 right and this is 1 and this is 2 comparison and 3 comparison so this is 6 by 3 1 comparison 2 comparisons and 3 comparisons so this is also 6 by 3 so you can see that all of these 5 trees one of the tree I got less number of comparisons that's average of comparison is less so that's what this is a balanced binary search tree so why we got less has the height of this a tree is less so that's why this is balanced binary search tree so I have shown you what does it mean by height balanced binary search tree now let us come to the actual problem that is optimal binary search tree so in this problem we consider that if these are the keys available then we also consider what is the frequency of searching of those keys if the keys are having some frequencies of search let us say the frequency of searching 10 is 3 and this is 2 and this is fine so this means that all the keys will not search them with the same frequency some keys are there that are most frequently used so we search them more frequently more often Li and some are in the use so like that who is having highest frequency 30 is having highest frequency then if the frequencies are defined for each key then what will be the cost so I want to know which at reorganization will be optimal or better so let us check them see the number of comparisons required for this one is 1 but its cost is 3 frequency is 3 and this frequency is 2 and this frequency is 5 so how much this will be 15 plus 4 plus 3 18 this is a three and this is a 2 this is 5 and this is a 2 so this is 10 plus 6 plus 3 so this is 19 and here the frequencies are this is 2 and this is the number of comparisons are 2 and it's frequency is 3 so this will be 3 into 2 and the number of comparison required that is the level is a 2 and it's frequency is 5 so this is 10 plus 6 plus 2 this is 18 and here it is a 5 then 10 that is a 3 and this is a 2 so this is 5 plus 6 plus 6 so this is 17 and this is 5 into this is 2 and this is 3 this 9 plus 4 plus 5 18 now the cost of the trees are different you can see that this tree organization has given us best result so that is optimal binary search tree for these 3 keys though it is not hide balanced this was height balance now the height is more but based on the frequencies that cost of that binary search tree is minimum so that's what the problem is if the keys are given and the frequencies are given we have to find out which the tree organization will be optimal based on the frequencies now I will take a problem and I will solve it using dynamic programming approach here I have keys 10 20 30 40 and their frequencies are given here for finding out optimal - history for these set of keys I have created a table here I am filling the values in this table and then that will help me to generate a table here the keys are 1 to 4 now the table you can see that it is starting from 0 onwards right but the keys are starting from 1 onwards I have to confirm own onwards this is from 0 onwards so that it's suitable for formula let us see how to solve this problem let us call these roles as I and columns as J now first of all we'll find out those values which are J minus I is equals to zero so for which values it will be J minus I will be 0 this is 0 minus 0 is 0 1 minus 1 is also 0 2 minus 2 3 - three four - four all these are 0 so it means I'll find out the cost of 0 comma 0 and 1 comma 1 and all these so it means I will fill up the diagonals and for the diagonal I will first fill up with all zeros this is the first step now I will find out this diagonal so in this one J - I really should be fun J - I equal to 1 then what it should be so this is 1 minus 0 is 1 2 minus 1 is 1 3 minus 2 is also 1 4 minus 3 is also 1 so this is 0 comma 1 1 comma 2 and 2 comma 3 3 comma 4 so I'll find out the cost of all those cost of 0 comma 1 cost of 1 comma 2 cost of 2 comma 3 and cost of 3 comma 4 now we will start filling the values now C 0 comma 1 means I'll be considering just one key that is key 110 what is frequency 4 so the cost is 4 and C of 1 2 - just ignore this first value and take this 1 so this is the key second key second key is 2 and the cost is 2 so yes this is 2 and this is third key third key is 30 and its cost you see that its frequency is C so the cost is 6 and this is 40 and its frequency is 3 so the cost is 3 so 4 - 6 3 so I got the answers as 4 2 6 3 so I have considered just one more 3G - I equal to one now next we'll go for J minus I equal to 2 now when this J minus I will be equal to 2 so this will be 4 2 minus 0 this is 0 comma 2 and 3 minus 1 this is 1 comma 3 and J will be food and I will be 2 so this is 2 comma 4 so for these things J minus I value will be 2 so it means I will be conserving 2 keys so I will consider first key and second key first so that means I will take this one first cost of 0 comma 2 I will find out this is 0 comma 2 right I am considering 2 keys so what are those two keys just ignore 0 starts from 1 so key 10 and key 20 what are their frequency is 4 and 2 let us see using these two keys only what is the minimum cost of binary search tree or the optimal binary search they can generate just by using Pookie's so for two keys what are the possible binary search trees 10 and this is 20 that is first is the root and this is second one is the root so 10 will be on this side so what is the cost of this so directly I will calculate see the frequency is 4 and this is one time and this is frequencies 2 and the number of comparisons are two so how much this is 4 plus 4 it is 8 and this is 2 into 1 and this is 4 into 2 so 1 comparison required for this and 2 comparisons required for this so this is how much 8 plus 2 so this is giving 10 and this is giving 8 so which one is minimum this one is minimum any one causes 8 and the which key is forming a row to 1 so I will fill up this value 8 and remove this one now I will show you how I can apply the formula here now before showing the formula I will use one value that weight of zero to four for example then this means sum of all the frequencies from one to four actually we have frequencies from what before what will write from zero to four right we are starting from zero so that we can make a formula so C of 0 to 4 months all sum of all the frequencies from 1 to 4 so let us see the formula see this is the cost is 8 I got now here I was taking root as 1 so this is C of 0 comma 0 on the left hand side then C of 1 comma 2 on the right hand side plus weight of 0 to 2 right so this is 0 to 2 let us check from the table what we got will we get this value as 8 or not let us set C of 0 comma 0 how much 0 plus C of 1 comma 2 C of 1 comma 2 is how much to 2 plus weight of 0 to 2 mins I should add all the frequencies from 1 to 2 1 & 2 so I already I have this 4 plus 2 so 4 plus 2 so answer is 8 now how the same formula is applicable on this side see this one is I am taking 2 as a root so one on this sides so C of 0 comma 1 plus C of 2 - 2 plus weight of 0 to 2 so from the table let us see 0 1 0 1 is how much 4 plus C of 2 comma 2 is 0 weight of all these that is 4 plus 2 is 6 so how much this is 10 yes we got the same answer so either I just check them with the height I am getting the same answer or else I am using the formula so I'm not showing the complete formula just I am applying it here so which has given us the minimum result 8 so that I have written right now I have to find out 1 comma 3 C of 1 comma 3 just ignore 1 so start from 2 so 2 2 3 so I will be taking keys 2 & 3 already wanted to all finish so 2 & 3 because every time we'll be taking just two keys so keys are 20 and 30 and their frequencies are 2 & 6 now what are the different race from this one I can make this second one as a key root so this side will be 30 or you can make third one as a root so this side will be 20 now what are the cost for this one this is 2 into 1 and the number of comparisons for this one will be 2 so this is 6 into 2 so how much this is so 2 plus 2 L is 14 and this is 1 into 6 and this is 2 into 2 so this is 4 plus 6 that is 10 who became root here third key this is the second key and this is the third key so third key became a root here so this is 10 and third key became root I will not use the formula all the way I have shown you now let me finish another value also known its key is this 1 this is 2 comma 4 so 2 comma 4 C of 2 comma 4 so ignored to we'll be taking third key and food key so third key is how much 30 and it's frequency is 6 40 is 40 and its frequency is 3 now what are the trees possible so if I make 30 as a rule then 40 will be on the right hand side or else 40 as a rule then 30 will be on the left hand side so two different trees are possible out of this right let me put the chorus directly so the frequency of this one is 6 and the number of comparison required are 1 and this is a 3 and the number of comparisons are 2 so this is 6 plus 2 6 and that is 2 and this is 3 into 1 and this is 6 into 2 its cost is 6 so this is 12 plus 3 fifteen so who has given us the minimum Brazil 2l has given us the minimum reserve and what is the key here third third one is the key so answer is 2l and three is the key so three will become a root third key will become a road so that's it we have filled up this diagonals where every time we were considering two keys now we have to fill up this diagonal and we have to consider three keys at a time now J minus I equal to 3 so what are the possibilities J is a 3 and I is a 0 so this is 0 comma 3 and J is the four and I is 1 so this is 1 comma 4 so these are the two possibilities so I should consider first 3 keys and then what that is 1 2 3 and then 2 2 4 so 3 3 I should select so let us see if I select this first one that is 0 2 3 so just ignore 0 and take the key so the keys are 10 20 and 30 first key second key and third key and the frequencies are 4 to 6 now what are the tree is possible with these 3 if I take 10 as a root then on this side I can get 20 and 30 this is one possibility or 10 as a root then 30 and 20 this is another possibility just 10 as a root so 10 is 1 as a root write 1 as a root then if I take 2 as a root then what are the possibilities 20 is here and on the left hand side is 10 and the right hand side is 30 if I make 30 as a key that is root here 3 as a root third value then 30 on this side then left side it can be 20 10 or 30 as a root 10 and right side 20 so with the three keys by selecting any one of the key as a rule there are total five different responsibilities one is minimum which one is minimum so for this I will use the formula directly right I will not calculate them so formula if you remember this one some of the frequency so we have to get from zero to three so if I find out weight of zero to three indirectly I will find out how much it is four plus two plus six so this is 12 so let us use this 2l every time all right so what is the cost of this side and this side and this side see here who is Route one is root so if one is root then this will be C of 0 comma 0 plus C of 1 comma 3 and plus wait wait is how much 2n I'll directly write on this one then for this when 2 is there as a root so this is 0 comma 1 plus C of 2 comma 3 plus 12 and on this side C of 0 comma 2 plus C of 3 comma 3 plus 12 out of this I have to select any one of them that is giving me minimum so that will the cost of C of 0 comma 3 C of 0 comma 3 so 0 comma 0 that is 0 plus 1 comma 3 how much 10 plus 2 n 22 0 comma bother how much 4 plus 2 comma 3 how much 2 comma 3 is 6 plus 2i so let's study 2 then 0 comma 2 how much 8 plus 3 comma 3 0 plus 12 this is 20 so 22 and this is also 22 which one has given minimum result this is 20 so 0 comma 3 0 comma 3 is 20 and which route has given its answer 3/3 wood has given us dancer so this is third route has given us dancer so third key should be a route or to find out next value this one for three keys and that is 1 comma 4 C of 1 comma 4 so what are the keys just ignore 1 and star taking the key from 2 onwards second key so that is 20 and the third key that is 30 40 40 and the frequencies are 2 6 and 3 right so I will not bear all possible trees now directly I will use the formula and solve it so for that I will find out the weight so W of 1 comma 4 so in this skip 1 and remaining we have to find out so it is nothing but sum of all these frequencies so Stu plus 6 plus 3 so this is 11 now let me use the formula C of 1 comma 4 is minimum of C of second is the root so 1 comma 1 plus C of 2 comma 4 or C of third key is a root so 1 comma 2 plus C of 3 comma 4 4 key as a root C of 1 comma 3 plus C of 4 comma 4 and at last I have to add that weight that is 11 so let me write down these values 1 comma 1 s 0 plus how much this is 2 comma 4 2 comma 4 is 12 0 plus 12 1 comma 2 is 10 1 comma 2 is 2 plus 3 comma 4 is 3 3 1 comma 3 is a 10 plus 4 comma 4 is 0 so which one of this is minimum this is minimum so this is 5 plus 11 as 16 so cost of this one is 16 right so answer is 16 and who gave this up which was the root here here the root was 2 and here the hoot was 3 this was the root so 3 is a root again now next J - I equal to 4 then I should consider 4 keys so for this possibility is 0 4 - 0 that is 0 comma 4 so finally I have to find out this value last value so for that all possible binary search trees from that I have to pick up the best one that's going to give me a optimal cost now I will directly use the formula and solve that one so cost of 0 to 4 so ignore 0 I have to keep taking 1 2 3 4 that are 10 20 30 and 40 and their frequencies are 4 2 6 3 then weight of 0 - 4 will be how much add all these so this is 15 and the cost of 0 comma 4 will be minimum or if I consider first key as a root then this is 0 comma 0 plus C of 1 comma 4 then if I consider this second as a root then this is C of 0 comma 1 plus C of second as the roots of 2 2 4 then third one as a root so C of 0 comma 2 plus C of 3 comma 4 the last one is C of 0 comma 3 plus C of 4 comma 4 and in all these I should add this weight that is 15 right so I will write down their values here so this is 0 plus 1 , for is how much 1 comma 4 is 16 plus 0 comma 1 is 4 plus 2 comma 4 2 comma 4 is 12 4 plus 2 n this is 0 comma 2 that is 8 + 8 + 3 comma 4 s 3 3 0 comma 3 0 comma 3 is 20 + 4 comma 4 is 0 only sort of this which is giving minimum result this is 16 and this is also 16 and this is 11 and this is 20 so minimum answer is 11 plus 15 and who is a root here 3 is a root here so answer is Kostas 26 + 3 is removed so this is 26 + 3 is a root so the cost of optimal binary search tree is 22 6 + root is 3 now I have a generator tree let us generate a tree from this data this is 0 comma 4 and the root is 3 so 4 root of 0 comma 4 as a 3 so if I take third key as a root this is the key number not a key that is 30 is a key the key number then on this side what we will get root of 0 to 2 and this is root of 3 to 4 now 0 to 2 0 2 tours this one so who is a vote here 1 so for this root is 1 then on this side what I get root of when one is the root 0 to 0 and on this side root of 1 2 - then who is root of 1 to 2 1 to 2 s this one - this is the second key right this is the second key first key and the second key so that a second key is the root so here is the second case the root then on this side what it will be root of 1 2 1 and this side root of 2 2 2 so for this answers are 0 only now 3 to 4 so what is 3 to 4 3 to 4 is this one this is fourth key so this is a fourth key and on this side root of 3 to 3 and root of 4 before so for this all the values are 0 only so this is a tree so who should be a root 30 should be a root and the left hand side should be 10 right side of this one should be drinking and the right side of this is 40 that's it this is the optimal binary search tree for this the cost of searching will be minimum based on their frequency of search now finally I will write on the formula that I was using cos trough I comma J is equals to minimum of cost of I comma K minus 1 plus cost of K 2 J plus weight of I comma J when K takes the values greater than I less than equal to J so the route was not studying from I afterwards so if this is 0 comma 4 so we'll start from 1 onwards ignore 0 that is the meaning so this is the formula for optimal binary search tree and the same formula I was using it for filling the table so that's all about optimal by this forestry problem

Channel: Abdul Bari

Views: 449,042

Keywords: algorithms, algorithm, dynamic programming, optimal binary search tree, binary search tree, cost of tree, abdul bari, bari, gate

Id: vLS-zRCHo-Y

Length: 30min 19sec (1819 seconds)

Published: Thu Feb 22 2018