1 00:00:00,012 --> 00:00:04,366 Next we're going to talk about binary search trees. 2 00:00:04,366 --> 00:00:09,251 And we said that binary trees are a classic structure in combinatorics. 3 00:00:09,251 --> 00:00:12,516 And they are enumerated by the Catalan numbers. 4 00:00:12,516 --> 00:00:16,338 But there also a classic structure in Computer Science. 5 00:00:16,338 --> 00:00:21,526 It's a fundamental data structure that's used for all sorts of things. 6 00:00:21,526 --> 00:00:27,642 But one of the most important is, for implementing symbol tables where we have 7 00:00:27,642 --> 00:00:31,792 lots of information. Each piece of information is associated 8 00:00:31,792 --> 00:00:37,192 with a key and we want to insert things into the symbol table, and we want to 9 00:00:37,192 --> 00:00:41,181 retrieve them by key. You can find much more inflammation, 10 00:00:41,181 --> 00:00:46,564 information, about symbol tables in our algorithms book or on the book site 11 00:00:46,564 --> 00:00:50,786 associated with the book. But I'll describe what minory trees, 12 00:00:50,786 --> 00:00:55,897 minory search tree's are because one of the, that's one of the most important 13 00:00:55,897 --> 00:01:01,279 algorthms in computer science and it uses a classical data structure, the binary 14 00:01:01,279 --> 00:01:03,503 tree. So, we work with nodes. 15 00:01:03,503 --> 00:01:07,255 and those are the things we can write programs to manipulate. 16 00:01:07,255 --> 00:01:11,737 Each node has a key, and the keys have values that are so called comparable 17 00:01:11,737 --> 00:01:14,884 values. That, that means is, it means, means that 18 00:01:14,884 --> 00:01:19,215 we will take two of them, and know whether one's less, equal or greater than 19 00:01:19,215 --> 00:01:24,002 the other, that's all. now usually in the implementations we do 20 00:01:24,002 --> 00:01:27,567 nowadays we assume the keys to be all distinct. 21 00:01:27,567 --> 00:01:33,007 we can do things with equal keys but both for the analysis and for the 22 00:01:33,007 --> 00:01:36,887 implementation, it's better to use distinct keys. 23 00:01:36,887 --> 00:01:42,928 now in the binary tree representation, nodes have 2 sub-trees, left sub-trees 24 00:01:42,928 --> 00:01:47,384 and right sub-trees, which are empty or might be whole trees. 25 00:01:47,384 --> 00:01:52,831 And if there's keys in the left sub-tree, all those keys are smaller than V. 26 00:01:52,831 --> 00:01:58,012 And if there's keys in the right sub-tree, they're all larger than V. 27 00:01:58,012 --> 00:02:04,316 that's what a binary search tree is. Now [COUGH] in Java and again without 28 00:02:04,316 --> 00:02:10,645 going into detail of Java code for those of you who don't know it, it might take 29 00:02:10,645 --> 00:02:16,066 some, you might have to read the algorithms book a bit to really follow 30 00:02:16,066 --> 00:02:21,622 all of this, and those of you who do know it, but either way it's very. 31 00:02:21,622 --> 00:02:27,434 Had, it's elegant it's simple it's small amount of code, to implement nodes and 32 00:02:27,434 --> 00:02:32,526 binary trees in java. so we build a data type, that, holds the 33 00:02:32,526 --> 00:02:38,502 associated information, so that we can manipulate it and keep it together. 34 00:02:38,502 --> 00:02:42,532 Programs that manipulate, and you'll see what those look like in just a minute. 35 00:02:42,532 --> 00:02:46,472 and the only operation that we need to perform is to be able to create a new 36 00:02:46,472 --> 00:02:50,002 node, with a given key and value, and that's what this code does. 37 00:02:50,002 --> 00:02:54,353 It defines that data type. That holds a, node's got four fields, 38 00:02:54,353 --> 00:02:59,385 it's got a key and a value, and it's got a reference to the two subtrees. 39 00:02:59,385 --> 00:03:05,523 The left subtree has smaller keys and the right subtree has larger keys, and that's 40 00:03:05,523 --> 00:03:09,822 how we represent it. and for programming language aficionados, 41 00:03:09,822 --> 00:03:14,343 we usually use generic types for keys, which means that we can hold any type of 42 00:03:14,343 --> 00:03:17,331 data with that. And again, you can read about these 43 00:03:17,331 --> 00:03:21,641 details in the algorithm. [INAUDIBLE] so that's what the computer 44 00:03:21,641 --> 00:03:24,747 representation of a binary search tree looks like. 45 00:03:24,747 --> 00:03:29,979 we have nodes that have keys and values and then each node points to another node 46 00:03:29,979 --> 00:03:34,709 which is another [INAUDIBLE], another binary search tree, the one on the left 47 00:03:34,709 --> 00:03:38,432 with smaller keys and the one on the right with larger keys. 48 00:03:38,432 --> 00:03:41,177 Keys. And it's a recursive structure, and 49 00:03:41,177 --> 00:03:46,041 eventually we get to places where the left sub tree is empty or the right sub 50 00:03:46,041 --> 00:03:49,606 tree is empty, in which case those links would be null. 51 00:03:49,606 --> 00:03:53,844 So that's the structure, and now what we're going to, what I'm going to 52 00:03:53,844 --> 00:03:58,968 describe is programs for manipulating that structure, for inserting your keys 53 00:03:58,968 --> 00:04:04,840 and for searching [UNKNOWN] for keys. the easiest is search unless look at the 54 00:04:04,840 --> 00:04:08,898 search implementation. This is a recursive program that operates 55 00:04:08,898 --> 00:04:13,897 on that recursive structure. there's some programming language jargon 56 00:04:13,897 --> 00:04:19,164 at the top, that has to do with the generics in otherwise let's look at what 57 00:04:19,164 --> 00:04:22,438 it does. so this is a data type for manipulating 58 00:04:22,438 --> 00:04:25,780 binary trees. What is a binary tree its a root node, so 59 00:04:25,780 --> 00:04:32,056 that is what the first line code says. Then theres the definition of nodes, and 60 00:04:32,056 --> 00:04:38,383 then this is the method for retrieving the value associated with a given key. 61 00:04:38,383 --> 00:04:43,272 I'll do it line by line. We have a variable X that we set to be 62 00:04:43,272 --> 00:04:48,142 the root of the tree, as long as that node acts as not-null. 63 00:04:48,142 --> 00:04:52,457 Then we got to compare the key at X. That's X dot key. 64 00:04:52,457 --> 00:04:59,420 with the key we were given to search for. that comparison can have three outcomes. 65 00:04:59,420 --> 00:05:03,742 Either less than zero, greater than zero or equal zero. 66 00:05:03,742 --> 00:05:09,664 If it's less the key we're looking for is less than x's key, then we're go to the 67 00:05:09,664 --> 00:05:12,022 left. Go to the left is x=x.left. 68 00:05:12,022 --> 00:05:17,952 That's recursively move down the tree to the left sub tree that contains smaller 69 00:05:17,952 --> 00:05:23,192 nodes than x's, and we have a smaller key so that's where we want to go. 70 00:05:23,192 --> 00:05:28,823 If it's greater, we go to the right, and if it's equal, we're done, we return x's 71 00:05:28,823 --> 00:05:32,738 value. that's an implementation of search for 72 00:05:32,738 --> 00:05:38,154 binary search trees, so in this example you can see to search, say for M, we 73 00:05:38,154 --> 00:05:41,495 start at S. M is less than S, so we go left. 74 00:05:41,495 --> 00:05:46,752 It's greater than E so we go right and then we're successful to see M. 75 00:05:46,752 --> 00:05:52,219 If we're searching for something that's not in the tree, say we're searching for 76 00:05:52,219 --> 00:05:58,088 Q we go left again, Q's less than S, it's bigger than E we go right, it's bigger 77 00:05:58,088 --> 00:06:03,732 than M we go right, but now we're on a null link and essentially that says that 78 00:06:03,732 --> 00:06:07,301 If Q were in the tree, it would have to be here. 79 00:06:07,301 --> 00:06:11,740 But there's nothing in the tree here so it's not here. 80 00:06:11,740 --> 00:06:17,248 And in that case down at the last statement in the implementation we 81 00:06:17,248 --> 00:06:20,241 return. So it's a very simply expressed 82 00:06:20,241 --> 00:06:23,949 algorithm. this is in a modern programming language. 83 00:06:23,949 --> 00:06:29,056 It's also easy to program these in even assembly or machine language that people 84 00:06:29,056 --> 00:06:34,075 my age have done that even. in any programming environment now you 85 00:06:34,075 --> 00:06:38,792 can implement binary trees pretty easily with a small amount of code. 86 00:06:38,792 --> 00:06:43,926 and so it's unsucessful. Now what about insert. 87 00:06:43,926 --> 00:06:50,096 so this is the code, for insert out of the algorithm script. 88 00:06:50,096 --> 00:06:58,089 and essentially what it does is, when we Do an unsuccessful search, and we come to 89 00:06:58,089 --> 00:07:02,009 a null link. So, say to insert q, we get to the same 90 00:07:02,009 --> 00:07:05,477 place. But, then what it does is create a new 91 00:07:05,477 --> 00:07:08,166 node for q. That's the first line. 92 00:07:08,166 --> 00:07:12,792 x equals null return new node, and then attaches it there. 93 00:07:12,792 --> 00:07:17,683 In the recursive calls rather that x equals x dot left, we say x dot left 94 00:07:17,683 --> 00:07:23,140 equals recursive calls and that is what does the attachment of the new note this 95 00:07:23,140 --> 00:07:27,552 is a little bit tricky but it is a very concise recursive code. 96 00:07:27,552 --> 00:07:31,352 And then now we've implemented both, insert and search. 97 00:07:31,352 --> 00:07:36,477 And so that's an important algorithm, that we want to analyze the performance 98 00:07:36,477 --> 00:07:40,402 of this algorithm. It's actually got good performance and 99 00:07:40,402 --> 00:07:44,102 it's widely used. Now the key fact that we have to worry 100 00:07:44,102 --> 00:07:49,552 about in doing this analysis, is that the shape of a binary search tree depends on 101 00:07:49,552 --> 00:07:55,127 the order of insertion of the keys. so the best thing that can happen would 102 00:07:55,127 --> 00:08:00,889 be the keys are inserted in such a way that the tree is perfectly balanced. 103 00:08:00,889 --> 00:08:06,925 that's like the tree that's described merge sort, that we looked at in the 104 00:08:06,925 --> 00:08:10,812 first lecture. the height of that tree is log N. 105 00:08:10,812 --> 00:08:16,588 Uh,and in that case all searches are going to be guaranteed to take less than 106 00:08:16,588 --> 00:08:22,321 log n, key comparisons say. a typical case, is more like the one that 107 00:08:22,321 --> 00:08:28,617 I showed for the example, where there's some nodes on either side on most, for 108 00:08:28,617 --> 00:08:32,492 most sub trees. But it's not perfectly balanced. 109 00:08:32,492 --> 00:08:37,704 That's the one, that we want to analyze. And we'll get to that in a minute. 110 00:08:37,704 --> 00:08:42,308 and it's also the worst case. so the keys come in, in order. 111 00:08:42,308 --> 00:08:47,292 if the keys come in, in order it's not very good performance. 112 00:08:47,292 --> 00:08:53,188 because their average cross for searching for Q in the tree is going to be about 113 00:08:53,188 --> 00:08:57,032 N/2, and that's going to be a performance problem. 114 00:08:57,032 --> 00:09:02,182 If you think of a huge symbol table. And, nowadays most of them are huge. 115 00:09:02,182 --> 00:09:07,307 With say a million or a billion keys. This one over here is going to get to any 116 00:09:07,307 --> 00:09:12,407 key with twenty or thirty searches. This one could require a half million or 117 00:09:12,407 --> 00:09:16,327 a half Billion. It's a very important performance 118 00:09:16,327 --> 00:09:19,563 difference. It's going to make the difference between 119 00:09:19,563 --> 00:09:24,172 being able to address the problem and not address it at all and we're to see 120 00:09:24,172 --> 00:09:28,499 average fall in between. that's where the analysis of algorithms 121 00:09:28,499 --> 00:09:31,929 comes in. so it's reasonable to analyze binary 122 00:09:31,929 --> 00:09:36,507 search tree structures under the assumption that the keys are inserted in 123 00:09:36,507 --> 00:09:40,244 random order. now that's a, a starting point. 124 00:09:40,244 --> 00:09:45,614 certainly you've got situations where clients do not insert em in random order. 125 00:09:45,614 --> 00:09:51,510 And it's not like Quick Sort where we can randomize because the insertions might 126 00:09:51,510 --> 00:09:57,026 come from some completely external force. And we don't, we don't have any source. 127 00:09:57,026 --> 00:10:00,762 And we don't have any way to rearrange their orders. 128 00:10:00,762 --> 00:10:05,479 So it's not quite as it's not a randomized algorithm that we can 129 00:10:05,479 --> 00:10:11,157 guarantee performance probabilistically the way we can with quick sort but still 130 00:10:11,157 --> 00:10:17,306 it's a reasonable model that actually is it can be validated in lots of practical 131 00:10:17,306 --> 00:10:20,887 situations. So it's a good starting point for 132 00:10:20,887 --> 00:10:26,502 analysis of a tree algorithm. when you, when you do that, if you have, 133 00:10:26,502 --> 00:10:30,869 this is BST built from, EDTs inserted in random order. 134 00:10:30,869 --> 00:10:37,217 you can see that the trees you get, they're different but unlike what we saw 135 00:10:37,217 --> 00:10:41,792 for random binary trees, would be tree [INAUDIBLE] likely. 136 00:10:41,792 --> 00:10:46,822 these are kind of balanced. well sometimes you get a little 137 00:10:46,822 --> 00:10:51,147 imbalance. so that's a typical random binary search 138 00:10:51,147 --> 00:10:54,332 trees. And again our goal is to characterize 139 00:10:54,332 --> 00:11:00,042 this analytically and explain why this is different from what we get with random 140 00:11:00,042 --> 00:11:03,982 binary trees. so we're going to analyze them both. 141 00:11:03,982 --> 00:11:10,278 now the key thing is that when you're analyzing binary search trees, the shape 142 00:11:10,278 --> 00:11:14,450 of the tree is a property of permutations, not trees. 143 00:11:14,450 --> 00:11:20,658 Our input model is a random permutation. that's N things in arbitrary order, 144 00:11:20,658 --> 00:11:26,188 N-factorial possibilities. Binary search tree is where we're talking 145 00:11:26,188 --> 00:11:31,262 about a random tree we're talking about 1 out of a [UNKNOWN] number of 146 00:11:31,262 --> 00:11:36,377 possibilities, which is way less. So, that's really important to remember. 147 00:11:36,377 --> 00:11:41,112 We're talking about propertation of, property of permutations, not tree. 148 00:11:41,112 --> 00:11:45,972 So you could have, and this gives all possibilities, for 1,2,3, and 4 nodes. 149 00:11:45,972 --> 00:11:50,782 And, the one that's blown up, is just one illustration, that shows, that. 150 00:11:50,782 --> 00:11:54,513 2 different permutations can lead to the same tree shape. 151 00:11:54,513 --> 00:11:59,646 So this case 1 comes in, tree goes to the right and then 2 goes to the left of tree 152 00:11:59,646 --> 00:12:04,779 and then 4 goes to the right of the tree. But 4 and 2 could come in the other order 153 00:12:04,779 --> 00:12:09,934 and you'd still get the same tree. And again, on the other hand, the tree 154 00:12:09,934 --> 00:12:15,664 where the keys come in all in order, 1-2-3-4, that's the only permutation that 155 00:12:15,664 --> 00:12:19,982 gives that shape. The ones that are more balanced, there's 156 00:12:19,982 --> 00:12:25,908 more permutations that give rise to them. Now that's an important observation to 157 00:12:25,908 --> 00:12:31,941 try to understand why we get more balance with binary search trees than with binary 158 00:12:31,941 --> 00:12:35,242 trees. so that's an observation and we're going 159 00:12:35,242 --> 00:12:39,662 to validate that. now it, it's int, in order to get it done 160 00:12:39,662 --> 00:12:44,382 we really want to think about the question if you have a tree shape, how 161 00:12:44,382 --> 00:12:47,802 many permutations are going to lead to that tree shape. 162 00:12:47,802 --> 00:12:52,009 So that means how many, if you would take a permutation and insert it into an 163 00:12:52,009 --> 00:12:56,521 initially empty binary search tree, how many are going to give that shape? Well, 164 00:12:56,521 --> 00:12:59,738 we sort of just did that. The answer to that is there's two 165 00:12:59,738 --> 00:13:02,001 different ones. The two has to be first. 166 00:13:02,001 --> 00:13:05,792 That's the one at the root. Then either you could either have the one 167 00:13:05,792 --> 00:13:08,313 go to the left, and the three go to the right. 168 00:13:08,313 --> 00:13:11,652 Or the three go to the left, and the one go to the right. 169 00:13:11,652 --> 00:13:16,754 and those are the only ones. Let's look at a bigger tree, how many 170 00:13:16,754 --> 00:13:21,915 permutations mapped to that one? Well that's a more complicated problem. 171 00:13:21,915 --> 00:13:26,212 so well one thing you know is that the root has to be 4. 172 00:13:26,212 --> 00:13:30,849 So you got, at least the first element permutation has to be 4. 173 00:13:30,849 --> 00:13:34,352 And then you have to have 1, 2, and 3 on the left. 174 00:13:34,352 --> 00:13:39,012 And 5 and 6 on the right. The 5 and 6 on the right, ther'es only 175 00:13:39,012 --> 00:13:44,127 one order that gives, that shape. Five has to go first and then six. 176 00:13:44,127 --> 00:13:47,497 And on the left you have the two possibilities. 177 00:13:47,497 --> 00:13:52,755 Either the two, one, three. But the other thing is that there's, Two 178 00:13:52,755 --> 00:13:56,312 possibilities, with the 1, 2, 3 and 5 and 6. 179 00:13:56,312 --> 00:13:59,547 They can be intermixed any number of ways. 180 00:13:59,547 --> 00:14:04,580 So, the answer is 20. you've got 5 keys that's left of the 181 00:14:04,580 --> 00:14:10,817 stuff that goes on the left and the right and you can intermix them, 5 choose two 182 00:14:10,817 --> 00:14:16,180 ways and then you've got the two possibilities for the left and the 1 183 00:14:16,180 --> 00:14:21,197 possibility for the right. and those are the 20 permutations that 184 00:14:21,197 --> 00:14:26,112 lead to that tree shape. and you can check that, validate that and 185 00:14:26,112 --> 00:14:30,088 if you don't quite believe or understand that math. 186 00:14:30,088 --> 00:14:35,621 so that's a bigger example. And then from that it's not hard to come 187 00:14:35,621 --> 00:14:40,286 to the general case, how many permutations map to a general A binary 188 00:14:40,286 --> 00:14:45,470 tree like that. Well, there's some number of nodes on the 189 00:14:45,470 --> 00:14:50,269 left sub tree. so the left sub tree is t sub l and the 190 00:14:50,269 --> 00:14:54,692 size of t sub l. Then the root has to be that number plus 191 00:14:54,692 --> 00:14:58,538 one. and then right sub tree has it, has its 192 00:14:58,538 --> 00:15:03,251 number of nodes. And then by the same argument that we 193 00:15:03,251 --> 00:15:08,703 just gave, if you define P sub 2 to be the number of permutations that map 194 00:15:08,703 --> 00:15:12,340 toward tree t. Then you have a recursive formula. 195 00:15:12,340 --> 00:15:18,131 P sub t = t sub L + t sub R choose t sub L, there's a number of different ways to 196 00:15:18,131 --> 00:15:21,702 intermix them. The smaller elements and the larger 197 00:15:21,702 --> 00:15:26,788 elements, and then for whatever all the ways of intermixing them, you can still 198 00:15:26,788 --> 00:15:31,410 put them in any one of the P sub P sub L orders or any one of the P sub P sub R 199 00:15:31,410 --> 00:15:34,475 orders. You have to multiply all those together 200 00:15:34,475 --> 00:15:38,812 to get the number of permutations that map to a general binary tree. 201 00:15:38,812 --> 00:15:44,637 so that's an interesting observation, and actually you can apply that formula 202 00:15:44,637 --> 00:15:50,312 recursively and just read off from the tree the number of shapes that map to it. 203 00:15:50,312 --> 00:15:54,632 But we're going to use that exact formula, a little bit later. 204 00:15:54,632 --> 00:16:00,164 so, and the other thing to observe from this formula is, that that binomial 205 00:16:00,164 --> 00:16:05,547 coefficient is going to be much much larger when the, two sub-trees are nearly 206 00:16:05,547 --> 00:16:09,374 balanced. that's the Gaussian distribution, so it's 207 00:16:09,374 --> 00:16:13,522 much larger at the middle. And we verified that analytically. 208 00:16:13,522 --> 00:16:18,165 if it's within square root of the, it's going to be much much larger. 209 00:16:18,165 --> 00:16:21,802 And, if T sub L is small, or T sub R is small, 210 00:16:21,802 --> 00:16:27,954 it's going to be exponentially smaller. So the, a number of permutations that map 211 00:16:27,954 --> 00:16:33,940 to an unbalanced tree is way, way smaller than the number that mapped to a balance 212 00:16:33,940 --> 00:16:38,548 tree, and that's why, that's what we observe in practice. 213 00:16:38,548 --> 00:16:44,438 so in summary so far. I describe two different binary tree 214 00:16:44,438 --> 00:16:51,443 models that, they're both fundamental, binary, random binary trees from the 215 00:16:51,443 --> 00:16:58,272 Catalan is, classic [UNKNOWN] structure. Binary search degrees is a classic, 216 00:16:58,272 --> 00:17:03,455 Computer Science strucuture. in the one model, in the BST model, that 217 00:17:03,455 --> 00:17:06,772 we used in, certain type of implentations. 218 00:17:06,772 --> 00:17:12,782 balanced shapes are much more likely. And actually, one way to think of it, is 219 00:17:12,782 --> 00:17:18,162 what's the probability that the root is of length k for a given k from 1 to n. 220 00:17:18,162 --> 00:17:22,737 Well in the BST model, it's built from a random permutation. 221 00:17:22,737 --> 00:17:28,737 So, in it's the first element in the permutation that goes at the root so the 222 00:17:28,737 --> 00:17:33,692 probability that any particular value is at the root is just 1/n. 223 00:17:33,692 --> 00:17:37,681 It's the same for all. It doesn't seem like it balances, but if 224 00:17:37,681 --> 00:17:42,760 you compare it with and so anyway, that's what the balances is, and in the 2nd one 225 00:17:42,760 --> 00:17:46,649 will compare that probability in what you get for the other case. 226 00:17:46,649 --> 00:17:51,742 so the [UNKNOWN] model, on the other hand, each tree shape is equally likely. 227 00:17:51,742 --> 00:17:57,312 and, and this is the probability that the root is of rank k in a random binary 228 00:17:57,312 --> 00:18:01,066 tree. you can have any tree on the left and any 229 00:18:01,066 --> 00:18:04,408 tree on the right out of all possible trees. 230 00:18:04,408 --> 00:18:11,170 that's called a Catalan distribution. and that gives rise to these much more 231 00:18:11,170 --> 00:18:15,022 unbalanced trees. 2 fundamentally different models. 232 00:18:15,022 --> 00:18:20,164 I don't want to emphasize that because we go into the analysis soon we get into the 233 00:18:20,164 --> 00:18:25,213 math without the picture it's easy to lose track of the fact that we're talking 234 00:18:25,213 --> 00:18:28,473 about something that's totally, totally different. 235 00:18:28,473 --> 00:18:31,742 In fact, here's a plot of that Catalan distribution. 236 00:18:31,742 --> 00:18:37,868 that the root is of rank k, in a randomly binary, chosen binary true of n nodes. 237 00:18:37,868 --> 00:18:43,844 And again, this is normalized, the way that we usually do these distributional 238 00:18:43,844 --> 00:18:49,182 plots, so that we can see how it converges to a curve, and look at the 239 00:18:49,182 --> 00:18:53,389 curve. the most of the weight is off on the 240 00:18:53,389 --> 00:18:57,450 edges, extremely close to the edges in fact. 241 00:18:57,450 --> 00:19:03,746 So as N gets larger, most of the probabilitiy that the root is a rank of 242 00:19:03,746 --> 00:19:11,306 N/2 becomes exponentially small, and the probability that the root is the smallest 243 00:19:11,306 --> 00:19:17,673 or the largest actually is a quarter. So the, it's actually a pretty good 244 00:19:17,673 --> 00:19:23,314 chance that it's going to be unbalanced. and just, by the way there's no magic in 245 00:19:23,314 --> 00:19:27,483 plotting a distribution like this and people who are comfortable with 246 00:19:27,483 --> 00:19:30,542 programming, I encourage you to go ahead and. 247 00:19:30,542 --> 00:19:35,728 Try to develop plots like that. You can it's easy to write inefficient 248 00:19:35,728 --> 00:19:41,136 programs but if you think about it And this one isn't even all that efficient, 249 00:19:41,136 --> 00:19:45,186 but anyway this is the program that I use to produce that pot. 250 00:19:45,186 --> 00:19:50,521 so the prob, as I mentioned, the probability that at least one of the two 251 00:19:50,521 --> 00:19:54,975 sub-tress is empty is about a half. So that's why it's going to be 252 00:19:54,975 --> 00:19:58,299 unbalanced. it's like flipping a coin and, and 253 00:19:58,299 --> 00:20:03,551 putting an empty or putting a random one. It's, it's a going to lead to much, much 254 00:20:03,551 --> 00:20:06,792 different shape than we have for the other case. 255 00:20:06,792 --> 00:20:13,009 Now again just to full disclosure of the code that I'm using to make these 256 00:20:13,009 --> 00:20:19,300 pictures for people that are comfortable with programming, the code that I use to 257 00:20:19,300 --> 00:20:25,810 generate random binary trees and it's all very similar to the code that I talked 258 00:20:25,810 --> 00:20:31,064 about for binary search trees. The only difference is that I add 259 00:20:31,064 --> 00:20:37,577 coordinates to get the height and the width, and it's the little calculation in 260 00:20:37,577 --> 00:20:44,102 terms of where to place nodes and I used our programming model from the 261 00:20:44,102 --> 00:20:50,767 algorithm's website to do the drawings. But what I want to talk about now is the 262 00:20:50,767 --> 00:20:56,397 generate method. that's supposed to generate a new tree at 263 00:20:56,397 --> 00:21:01,192 a certain depth. And what that node does is basically it's 264 00:21:01,192 --> 00:21:07,432 a recursive program that computes the internal length of the root according to 265 00:21:07,432 --> 00:21:13,952 the appropriate probability distribution. and then recursively generates trees on 266 00:21:13,952 --> 00:21:18,727 the left and on the right. so and in this case to make the trees 267 00:21:18,727 --> 00:21:23,512 look good, I actually included the invisible external nodes in the rank 268 00:21:23,512 --> 00:21:26,567 field. and the point of this is to show there 269 00:21:26,567 --> 00:21:31,535 are a lot of similarities, and. I use this same curve to generate both 270 00:21:31,535 --> 00:21:36,384 kinds of trees. the only difference is, for random BST I 271 00:21:36,384 --> 00:21:42,528 uniformly choose the value of that rank. And for a random binary tree, I went to 272 00:21:42,528 --> 00:21:46,158 that Catalan distribution. to use it. 273 00:21:46,158 --> 00:21:51,740 So with a relatively small amount of code I've been generating these tree diagrams. 274 00:21:51,740 --> 00:21:56,034 and then again full disclosure and I'm not going to go through that. 275 00:21:56,034 --> 00:22:00,699 This is the code using our standard drawing model from the Algorithms book 276 00:22:00,699 --> 00:22:08,459 site, that scales and draws the binary tree as I talked about a few minutes ago. 277 00:22:08,459 --> 00:22:15,625 and for those of you who enjoy programming, it's a, it's a interesting 278 00:22:15,625 --> 00:22:22,662 exercise, to imlement the centered bi-level method that did for 279 00:22:22,662 --> 00:22:27,914 I already ran the Catalan trees. It's a draw general trees, and forests, 280 00:22:27,914 --> 00:22:32,396 and other things. Each one of those tasks, is intriguing 281 00:22:32,396 --> 00:22:36,390 programming exercise for, for people who enjoy programming. 282 00:22:36,390 --> 00:22:41,204 So that's a introduction to binary search trees and next we'll get into the 283 00:22:41,204 --> 00:22:41,793 analysis.