1 00:00:00,012 --> 00:00:05,742 And next, we're going to talk about the analysis of path length in binary trees. 2 00:00:05,742 --> 00:00:12,039 and, this is an important problem to to study, because that''s the quantity that 3 00:00:12,039 --> 00:00:18,204 we use to predict performance in the analysis of the binary search algorithm 4 00:00:18,204 --> 00:00:24,265 that I talked about before. So here's the definition that I gave 5 00:00:24,265 --> 00:00:29,590 before for a binary tree and the level and the depth. 6 00:00:29,590 --> 00:00:37,294 When we talk about path length what we want to compute is the average length of 7 00:00:37,294 --> 00:00:42,521 a path to a node that's in the tree, say an internal node. 8 00:00:42,521 --> 00:00:48,920 so to do that we compute the total internal path length and then dividing 9 00:00:48,920 --> 00:00:54,244 that by n gives, gives that average cost. and so to computer the total you just 10 00:00:54,244 --> 00:00:58,102 count the number of nodes at each level. So at level 1 there's, 11 00:00:58,102 --> 00:01:05,365 2 nodes, at level 2, there 4, level 3, there's 3 4, there's 1, 5 there's 1, and 12 00:01:05,365 --> 00:01:09,490 you add that all up, that's called the internal path length, 13 00:01:09,490 --> 00:01:13,765 of, a binary tree. it's the, a sum over all nodes of length 14 00:01:13,765 --> 00:01:19,082 of a path from the root to that node or the sum of k times the number of at that 15 00:01:19,082 --> 00:01:22,712 at that, the k. for binary trees we also talk about 16 00:01:22,712 --> 00:01:28,232 external path length and that's just the same thing for external nodes. 17 00:01:28,232 --> 00:01:35,047 so external n, also that's a quantity of interest in studying the binary search 18 00:01:35,047 --> 00:01:39,873 algorithm. so these things there is relationships 19 00:01:39,873 --> 00:01:44,589 among these that are easy to prove it's all recursive. 20 00:01:44,589 --> 00:01:51,767 so and there's a lot of notation to be able to talk about these things. so let's 21 00:01:51,767 --> 00:01:54,705 look at some simple relationships among them. 22 00:01:54,705 --> 00:02:00,025 so we're talking about binary trees and we have this size function and just a 23 00:02:00,025 --> 00:02:03,316 different size function for external nodes. 24 00:02:03,316 --> 00:02:07,905 and then its left and right subtrees we'll indicate with tl and tr. 25 00:02:07,905 --> 00:02:13,942 ipl stands for the internal path length, xpl stands for the external path length. 26 00:02:13,942 --> 00:02:18,787 So that's all the notation, and again, these are simple quantities to define as 27 00:02:18,787 --> 00:02:23,012 I did on the previous slide. so here's some recurrsive relationships. 28 00:02:23,012 --> 00:02:27,842 So one thing is the number of internal nodes in a tree is the number of internal 29 00:02:27,842 --> 00:02:32,142 nodes on the left plus the number of internal nodes on the right plus one for 30 00:02:32,142 --> 00:02:36,589 the root so that's five. external nodes, it's just 31 00:02:36,589 --> 00:02:41,571 the, root is not an external node, so the number of external nodes in the 32 00:02:41,571 --> 00:02:47,052 tree is the number of external nodes on the left plus the number of external 33 00:02:47,052 --> 00:02:51,244 nodes on the right. internal path link so this is an 34 00:02:51,244 --> 00:02:55,232 interesting one. If you wanted the internal path length of 35 00:02:55,232 --> 00:03:01,061 the whole tree you take the internal path length on the left, and the internal path 36 00:03:01,061 --> 00:03:03,938 length on the right, and add those together. 37 00:03:03,938 --> 00:03:08,865 And then, what you are is you're are off by one on every single node except the 38 00:03:08,865 --> 00:03:12,080 root. So, if you add, t-1, then you're adding 39 00:03:12,080 --> 00:03:16,715 this length to all the nodes. and so that's a recursive relationship 40 00:03:16,715 --> 00:03:22,192 for the external path length and for internal path length and for external 41 00:03:22,192 --> 00:03:26,347 path length it's similar. external path length on the left, 42 00:03:26,347 --> 00:03:30,982 external path length on the right, but you're off by one for every node because 43 00:03:30,982 --> 00:03:35,982 you didn't take into account the nodes that connect the external node the 44 00:03:35,982 --> 00:03:40,832 subtree to the root. So those are simple but very useful 45 00:03:40,832 --> 00:03:46,383 recursive relationships so and then, from those relationships, 46 00:03:46,383 --> 00:03:52,187 you can prove easy things, like the number of external nodes is equal to the 47 00:03:52,187 --> 00:03:57,254 number of internal nodes plus one, and that's just by induction. 48 00:03:57,254 --> 00:04:03,935 so just plug in [COUGH] from this formula here the number of the external nodes is 49 00:04:03,935 --> 00:04:09,603 the sum of the external nodes in the two parts by the inductive hypothesis that's 50 00:04:09,603 --> 00:04:15,271 equal to tl+tr+1 and then, using the recursive relationship of internal nodes 51 00:04:15,271 --> 00:04:20,806 we're left with internal nodes plus one. there's lots of ways to to prove that. 52 00:04:20,806 --> 00:04:27,736 here is another one external path length is equal to internal path length plus two 53 00:04:27,736 --> 00:04:31,422 times the number of internal nodes in the tree. 54 00:04:31,422 --> 00:04:36,655 And again, that's inductive right from the simple recursive relationships that 55 00:04:36,655 --> 00:04:40,533 we talked about. so and again, there's a lot of ways to 56 00:04:40,533 --> 00:04:45,990 prove those things, too just using these as an exercise for getting used to the 57 00:04:45,990 --> 00:04:51,797 idea of path length in its relationship with the path length in the subtrees to 58 00:04:51,797 --> 00:04:57,917 the path link in the whole tree that is critical to the analysis that we're 59 00:04:57,917 --> 00:05:00,182 going to do. okay, so here's our first problem. 60 00:05:00,182 --> 00:05:05,877 we have a random binary tree. So that's a binary tree where all tree 61 00:05:05,877 --> 00:05:11,641 shapes are equally likely with a probability of one over Catalan numbers 62 00:05:11,641 --> 00:05:15,942 one over n plus [INAUDIBLE]. what's the average path length of a 63 00:05:15,942 --> 00:05:21,499 random binary tree? That's some kind of description of the tree shapes that we 64 00:05:21,499 --> 00:05:24,433 saw. How how far are all the nodes from the 65 00:05:24,433 --> 00:05:27,462 root and far is an average node from the root? 66 00:05:27,462 --> 00:05:35,017 This sort of what we're saying with that. so these are the quantities that we're 67 00:05:35,017 --> 00:05:39,882 going to work with. so QNk is the number of trees with N 68 00:05:39,882 --> 00:05:45,007 nodes and in internal path length k. Tn is the number of trees, that's a 69 00:05:45,007 --> 00:05:49,111 Catalan numbers, and accumulated cost is the total 70 00:05:49,111 --> 00:05:54,131 internal path length path length on all trees, so that we get the average by 71 00:05:54,131 --> 00:05:57,846 dividing the accumulated cost by the number of trees. 72 00:05:57,846 --> 00:06:03,557 that's the, that's the way that we compute average values of parametrs. 73 00:06:03,557 --> 00:06:09,982 So this is for two so in this case both of the trees with two nodes have internal 74 00:06:09,982 --> 00:06:16,243 path length of one so the average so the total accumulated internal path length is 75 00:06:16,243 --> 00:06:21,270 one, the average internal path length is one, it's still not, not so interesting. 76 00:06:21,270 --> 00:06:27,046 now, this is a little more interesting. so there's five trees with three nodes. 77 00:06:27,046 --> 00:06:32,753 four of them have internal path length three zero to the root, one to the one 78 00:06:32,753 --> 00:06:36,649 below, and two more to the next one. So, that's three. 79 00:06:36,649 --> 00:06:42,039 Four of them have that structure, one of them has internal path length two the 80 00:06:42,039 --> 00:06:47,503 nodes are both just one from the root. So, Q32=1, there's one tree of size 2 81 00:06:47,503 --> 00:06:54,001 that has internal path length 1, and there is four trees of size 3 that 82 00:06:54,001 --> 00:07:00,417 have internal path length 3. and so and that's [INAUDIBLE] equals 83 00:07:00,417 --> 00:07:04,690 five. So the total, the average internal path 84 00:07:04,690 --> 00:07:09,648 length is 14/5 is 2.8. so that's the figures for three and 85 00:07:09,648 --> 00:07:13,129 here's the corresponding figures for four. 86 00:07:13,129 --> 00:07:19,487 Total path length in all of these trees is 74 and there's 14 of them, so the 87 00:07:19,487 --> 00:07:26,285 average expected internal path length is 5.2 in these trees of size four. 88 00:07:26,285 --> 00:07:32,367 And then, you can take that and say the average distance to an internal node, 89 00:07:32,367 --> 00:07:37,903 divide that by four again to get about how far a node is from the root. 90 00:07:37,903 --> 00:07:40,940 so that's the quantities that we're after. 91 00:07:40,940 --> 00:07:44,002 It's always good to do small cases like this uh,. 92 00:07:44,002 --> 00:07:48,861 to make sure that you have a good fix on the exact quantities that's you're 93 00:07:48,861 --> 00:07:52,050 analyzing, expected path length of a random binary 94 00:07:52,050 --> 00:07:55,457 tree. so here is the analytic combinatorics 95 00:07:55,457 --> 00:08:00,482 derivation of this and these are all things we've defined so far. 96 00:08:00,482 --> 00:08:07,367 so the counting GF is just the Ccatalans and that's all the information we know 97 00:08:07,367 --> 00:08:13,127 about the Catalan numbers. the cumulative cost generating function 98 00:08:13,127 --> 00:08:18,517 is sum over all trees, internal path length times z to the tress of size. 99 00:08:18,517 --> 00:08:24,582 and that's also equal to the sum of N sum of k, number of path length case and, and 100 00:08:24,582 --> 00:08:29,172 so forth. but, from now on, we're just going to go 101 00:08:29,172 --> 00:08:35,587 with cumulative counting and we know that the average is going to be the 102 00:08:35,587 --> 00:08:41,092 coefficient of z^N and the q divided by the coefficient of z^N and the t. 103 00:08:41,092 --> 00:08:45,897 The coefficient is z^N and the Q is the total internal path length of all trees 104 00:08:45,897 --> 00:08:48,692 of size N. If you divide by that by the number of 105 00:08:48,692 --> 00:08:52,332 trees of size N, then you get the average internal path length. 106 00:08:52,332 --> 00:08:57,217 so that's the cumulative counting method that we're going to use to analyze this 107 00:08:57,217 --> 00:09:00,907 quantity. and so now, what we have to do is analyze 108 00:09:00,907 --> 00:09:04,938 that cumulative, cumulative cost generating function and that's what we'll 109 00:09:04,938 --> 00:09:08,219 do next. so we have the counting GF and we have 110 00:09:08,219 --> 00:09:11,986 the cumulative GF. And we're going to use this recursive 111 00:09:11,986 --> 00:09:17,009 relationship slightly different but pretty similar to the one that we just 112 00:09:17,009 --> 00:09:21,394 talked about. the internal path length of a tree is 113 00:09:21,394 --> 00:09:28,787 equal to the internal path length of its two subtrees plus the number of nodes in 114 00:09:28,787 --> 00:09:34,125 the two subtrees. and so from that definition, we can 115 00:09:34,125 --> 00:09:42,289 immediately write down this decompostion. this first one is for the empty tree and 116 00:09:42,289 --> 00:09:48,659 this other one is for the root. but if we have that function, we look at 117 00:09:48,659 --> 00:09:53,970 this decomposition, the ipl of t is exactly equal to that and the size of t 118 00:09:53,970 --> 00:10:00,136 is exactly equal to that and so we have that that double sum for that cumulative 119 00:10:00,136 --> 00:10:06,177 cost cumulative cost. And that decomposition or looking other 120 00:10:06,177 --> 00:10:10,426 way that construction, now we can rearrange terms. 121 00:10:10,426 --> 00:10:15,358 and you could see for example that ipl(tl)z^tl times z^tr, 122 00:10:15,358 --> 00:10:19,861 that's Q(z)T(z). So, that's one of the terms that we find 123 00:10:19,861 --> 00:10:23,980 in there. and the other ones where these tl's come 124 00:10:23,980 --> 00:10:29,135 in to effect we get t prime of (z)T of z. This formula has those four terms and 125 00:10:29,135 --> 00:10:34,842 using these two equations, it immediately reduces to that simple equation relating 126 00:10:34,842 --> 00:10:40,665 the counting generating function and the cumulative generating function, 127 00:10:40,665 --> 00:10:46,383 recursive equation that relates those two generating function. Extremely simple 128 00:10:46,383 --> 00:10:52,359 argument, it's actually possible to develop this symbolically and we'll talk 129 00:10:52,359 --> 00:10:57,758 about derivations like that in part two. but it's worthwhile having the, the 130 00:10:57,758 --> 00:11:04,089 explicit decomposition in front of us to see how directly we get to the equation 131 00:11:04,089 --> 00:11:08,844 that matters, which is the generating fucntion the equation relating the 132 00:11:08,844 --> 00:11:12,982 generating functions that we can then solve and analyze. 133 00:11:12,982 --> 00:11:18,635 okay, so just to get it all in one slide, I'll put those steps down there. 134 00:11:18,635 --> 00:11:21,042 So, now we know that Q(z) = 2zT(z) times Q of z plus zT prime. 135 00:11:23,727 --> 00:11:31,172 we know what T and T prime are, the only thing we don't know is Q so we 136 00:11:31,172 --> 00:11:36,792 can solve that for Q. And then we can just T of z remember 137 00:11:36,792 --> 00:11:40,611 that's the, the Catalan and we know what T sub N is. 138 00:11:40,611 --> 00:11:46,327 and t prime is just the derivative of that which has two terms in it. 139 00:11:46,327 --> 00:11:50,916 but there is one thing that simplifies calculations a lot, 140 00:11:50,916 --> 00:11:56,602 1-2zT(z) if you multiply this by 2z, it's just square root of 1-4z, so that takes 141 00:11:56,602 --> 00:12:00,687 care of the denominator. So there is a little, still a little bit 142 00:12:00,687 --> 00:12:05,612 of algebra multiplying these two things together but there's lots of 143 00:12:05,612 --> 00:12:10,067 cancellations, because square root of 1-4z times square root of 1-4z is just 144 00:12:10,067 --> 00:12:13,274 1-4z. so I'm going to not going to pretend I'm 145 00:12:13,274 --> 00:12:18,512 going to omit some of the algebra but the final result is pretty simple. 146 00:12:18,512 --> 00:12:24,334 so that's an explicit equation for the cumulative counting generating function. 147 00:12:24,334 --> 00:12:29,116 And what do, what do you need? The coefficient of z^N in that is the 148 00:12:29,116 --> 00:12:32,502 internal path length of all the trees of size N. 149 00:12:32,502 --> 00:12:38,310 and just looking at that, you can see that it's going to be 4^N 150 00:12:38,310 --> 00:12:44,631 next turn, is lower in magnitude. so the take all those binary trees as Catalan 151 00:12:44,631 --> 00:12:49,567 number and add up all their internal path length and get 4^N. 152 00:12:49,567 --> 00:12:55,041 It's surprisingly simple. It's not exactly 4^N, but asymptotically, 153 00:12:55,041 --> 00:12:58,642 it's 4^N. And that's why we want to do precise 154 00:12:58,642 --> 00:13:02,919 asymptotics before, because, if you take that and divide it 155 00:13:02,919 --> 00:13:06,436 by the Catalan, all you're left with is n^2 of pi N. 156 00:13:06,436 --> 00:13:11,321 We divided two huge quantitites, but since we were working with preice 157 00:13:11,321 --> 00:13:16,712 asymptotic results, we get a precise answer, average internal path length of a 158 00:13:16,712 --> 00:13:22,052 random binary tree is N square root of, is asymptotic to N square root of pi N. 159 00:13:22,052 --> 00:13:27,241 And that's a very accurate estimate [COUGH] for the average internal path 160 00:13:27,241 --> 00:13:30,006 length. And we could do it, we could get it 161 00:13:30,006 --> 00:13:35,079 exactly, but doing it asymptotically is very compelling, 162 00:13:35,079 --> 00:13:40,702 because it's a simple and suprising and unexpected result. 163 00:13:40,702 --> 00:13:47,720 so now let's look at the same thing for random binary search trees. 164 00:13:47,720 --> 00:13:54,839 So that, that one kind of explains or starts to explain the shape of a Catalan 165 00:13:54,839 --> 00:13:59,346 tree. the nodes go down square root of N which 166 00:13:59,346 --> 00:14:02,636 in a 10,000 node tree, it goes down a 100. 167 00:14:02,636 --> 00:14:08,235 It's a good, pretty good size depth and that's the average so it goes down a few 168 00:14:08,235 --> 00:14:12,052 hundred. and what about binary search trees? 169 00:14:12,052 --> 00:14:16,835 Well, here's the same calculation per binary search tree. 170 00:14:16,835 --> 00:14:23,491 but now we're counting permutations that result in a binary search tree with N 171 00:14:23,491 --> 00:14:29,743 nodes and internal path length k. and now it's a little easy because the 172 00:14:29,743 --> 00:14:34,020 counting factor is N factorial we know that. 173 00:14:34,020 --> 00:14:41,092 but still the accumulated cost is the same way, it's just that 174 00:14:41,092 --> 00:14:46,196 we have to count the number of permutations, so in this case, some of 175 00:14:46,196 --> 00:14:51,938 the trees have internal path length 4, 5 and 6 as before, but the weighting is 176 00:14:51,938 --> 00:14:55,523 different. So all of these 12 permutations give 177 00:14:55,523 --> 00:14:58,318 four. there's only four of them that give 5, 178 00:14:58,318 --> 00:15:01,582 that's these four, and the remaining eight give 6. 179 00:15:01,582 --> 00:15:08,227 So the total internal path length of the trees that you get from all of the 24 180 00:15:08,227 --> 00:15:13,102 permutations is 74. If you divide that by 24 you get 4.833, 181 00:15:13,102 --> 00:15:19,057 which is less than what you get for Catalan trees, because the balanced ones 182 00:15:19,057 --> 00:15:25,009 are weighted are more, much more likely. That's the same setup and now we can use 183 00:15:25,009 --> 00:15:30,917 analytic combinatorics in this same way to analyze the path length of binary 184 00:15:30,917 --> 00:15:35,566 search trees and get a comparison between, showing us the difference 185 00:15:35,566 --> 00:15:40,502 between these two models. so start as usual, but now we have 186 00:15:40,502 --> 00:15:45,552 permutations and so our cost is the length of the permutation. 187 00:15:45,552 --> 00:15:50,927 but now when we say ipl, we mean, we want, the, it's the ipl of a permutation, 188 00:15:50,927 --> 00:15:57,026 which doesn't make sense, except if you say that the permutation is what we want 189 00:15:57,026 --> 00:16:01,721 is the internal path length of the BST you get from that permutation by 190 00:16:01,721 --> 00:16:04,804 inserting it in to an initially empty tree. 191 00:16:04,804 --> 00:16:10,610 and again the number of permutations of size N is N factorial and that saves us a 192 00:16:10,610 --> 00:16:17,119 step in the calculations as you'll see. and accumulated cost is the total ipl of 193 00:16:17,119 --> 00:16:21,128 binary search trees built from all permutations. 194 00:16:21,128 --> 00:16:26,619 So now our counting EGF is a simple one, that's the, the basic EGF for 195 00:16:26,619 --> 00:16:31,746 permutations it's just 1/1-z. we have an N factorial involved, but 196 00:16:31,746 --> 00:16:36,302 that's our number of permutations, so that cancels out. 197 00:16:36,302 --> 00:16:42,557 Our cumulative cost EGF it's the same symbols as before, except now we have 198 00:16:42,557 --> 00:16:47,167 permutations not trees and ipl has that different meaning. 199 00:16:47,167 --> 00:16:53,567 and so, to get the expected internal path length of a binary search tree built from 200 00:16:53,567 --> 00:16:59,621 a random permutation, we're going to take N factorial of coefficient of z^N in that 201 00:16:59,621 --> 00:17:02,941 divided by N factorial and those N factorials cancel out. 202 00:17:02,941 --> 00:17:09,232 So, it's just almost, it's treating it as an ordinary generating function gives us 203 00:17:09,232 --> 00:17:14,790 the divide by N factorial for free. It's just a little calculation trick does 204 00:17:14,790 --> 00:17:17,460 those, because we're using exponential 205 00:17:17,460 --> 00:17:24,018 generating functions, which means that we divide by N factorial but are probability 206 00:17:24,018 --> 00:17:28,988 spaces permutations, so we want to divide by N factorial, so it serves both 207 00:17:28,988 --> 00:17:32,312 purposes and saves us the step of dividing. 208 00:17:32,312 --> 00:17:36,553 We just look for the coefficient of z^N and see if you. 209 00:17:36,553 --> 00:17:43,614 So next we'll have to look at developing a generating function equation for that 210 00:17:43,614 --> 00:17:49,724 C(z) using the recursive defintion of the binary tree structure according to the 211 00:17:49,724 --> 00:17:55,213 way that we construct trees. so, same basic steps as before, it's just 212 00:17:55,213 --> 00:18:00,074 that we're going to come up with a different equation because we have a 213 00:18:00,074 --> 00:18:04,823 different structure. so again, this is a, just a summary what 214 00:18:04,823 --> 00:18:10,237 we're after is a, a better equation an equation that C(z) has to satisfy. 215 00:18:10,237 --> 00:18:16,612 and then, we're, what we're going to do is use this relationship that we talked 216 00:18:16,612 --> 00:18:22,822 about before, that gives us all the permutations that lead to the same tree. 217 00:18:22,822 --> 00:18:31,286 and so, that decomposition for but, from one, from a permutation P to a 218 00:18:31,286 --> 00:18:39,249 permutation that ipl of P is and those are all the permutations that give rise 219 00:18:39,249 --> 00:18:46,811 to that and then, i, ipl of P is is, got that recursive relationship as before. 220 00:18:46,811 --> 00:18:53,049 we can express everything there in terms of p sub l and p sub r, 221 00:18:53,049 --> 00:18:57,583 because of this decomposition that we already talked about. 222 00:18:57,583 --> 00:19:03,166 And this one is even simpler than the other one, there's just one trick that 223 00:19:03,166 --> 00:19:07,121 often works with exponential generating functions. 224 00:19:07,121 --> 00:19:13,006 This p l plus p one factorial causes in the denominator causes a little 225 00:19:13,006 --> 00:19:16,462 inconvenience in simplifying this formula, 226 00:19:16,462 --> 00:19:22,567 but we have z to that same quantity. So what we do is differentiate to cancel out 227 00:19:22,567 --> 00:19:25,166 that one factor, then you'll see there's a pL+pR factorial 228 00:19:27,092 --> 00:19:32,281 on the bottom and then we can mix that with the binomial coefficient. 229 00:19:32,281 --> 00:19:37,835 so this is a, a trick that often works with exponential generating functions. 230 00:19:37,835 --> 00:19:43,887 Differentiate, then cancel the pL+pR in the binomial coefficient and you're left 231 00:19:43,887 --> 00:19:50,085 with a pL factorial pR factorial. And now you've got a very simple double 232 00:19:50,085 --> 00:19:58,183 sum that completely decomposes and separates the [COUGH] you know, P(z) b or 233 00:19:58,183 --> 00:20:05,122 of P factorial is just P(z) and p prime of z is the one that takes care of 234 00:20:05,122 --> 00:20:08,647 pl over pl is pl minus one factorial, so use this equation. 235 00:20:08,647 --> 00:20:15,047 and then, again, we get a very simple differential equation now for the 236 00:20:15,047 --> 00:20:22,422 cumulative cost exponential generating function for path lengths and BSTs. 237 00:20:22,422 --> 00:20:28,475 Decomposition is important. It's gotta be precise. It's gotta be correct, but once 238 00:20:28,475 --> 00:20:33,320 you have that decomposition, you automatically get a relationship that, 239 00:20:33,320 --> 00:20:36,687 that b exponential generating function for the cumulative cost and the counting 240 00:20:36,687 --> 00:20:46,318 GF have to satisfy. [COUGH] And again, solving for C(z) gives 241 00:20:46,318 --> 00:20:55,412 just simplifying that subtituting in for P(z) gives a very simple equation. 242 00:20:55,412 --> 00:21:02,289 so recognize that equation? we saw that in the first lecture actually. 243 00:21:02,289 --> 00:21:08,653 that's the equation that came up with solving the quicksor recurrence. 244 00:21:08,653 --> 00:21:14,945 I guess it came up in the generating functon lecture pretty much the same 245 00:21:14,945 --> 00:21:19,732 equation. So just with that observation, we solve 246 00:21:19,732 --> 00:21:26,566 that, because it's a first that in first order differential equation that has a 247 00:21:26,566 --> 00:21:31,616 simple integration factor and was not difficult to solve. 248 00:21:31,616 --> 00:21:38,365 so now we can fit the and summarize the analysis of expected length of, in a BST 249 00:21:38,365 --> 00:21:41,609 built from a random permutation on this slide. 250 00:21:41,609 --> 00:21:48,630 start with the definition of equation for the cumulative generating function 251 00:21:48,630 --> 00:21:52,711 substitute in the construction and the decomposition. 252 00:21:52,711 --> 00:21:57,189 differentiate the simplify substitute the further simplification 253 00:21:58,516 --> 00:22:05,707 and that is a generating function that it has the solution 2/(1-z)^2 log of 1/1-z - 254 00:22:05,707 --> 00:22:11,222 2z/(1-z)^2. And those are elementary series that we 255 00:22:11,222 --> 00:22:18,212 can expand to define the coefficients as we did before to show that the average 256 00:22:18,212 --> 00:22:24,622 internal path length in a binary search tree is asymptotic to 2N natural log N. 257 00:22:24,622 --> 00:22:31,189 So a log N as a factor if divided by N log N to the average node 258 00:22:31,189 --> 00:22:37,738 in a binary search tree square root of N in a binary Catalan tree. 259 00:22:37,738 --> 00:22:48,042 in since the same equation comes up and people who've had algorithms courses know 260 00:22:48,042 --> 00:22:53,161 that there's a bijection between quicksort and binary search trees that 261 00:22:53,161 --> 00:22:56,862 explains this. We could have analyzed binary search 262 00:22:56,862 --> 00:23:00,692 trees just by taking advantage of this bijection. 263 00:23:00,692 --> 00:23:04,929 so, that is in quicksort, you have the first entry in 264 00:23:04,929 --> 00:23:09,999 the permutation as the partitioning element and the smaller ones and larger 265 00:23:09,999 --> 00:23:15,046 ones are mixed and then, after the partitioning you do them independently. 266 00:23:15,046 --> 00:23:20,378 and that's pretty much the same in a binary search tree you the first, the 267 00:23:20,378 --> 00:23:24,822 first one is the root and then you do the left and right independently. 268 00:23:24,822 --> 00:23:29,933 so you can show, that the average [UNKNOWN] pairs for the quicksort is 269 00:23:29,933 --> 00:23:34,428 exactly the average external path length, like the BST built from a random 270 00:23:34,428 --> 00:23:39,099 permutation. and that's an interesting bijection to to 271 00:23:39,099 --> 00:23:43,587 know to take advantage of. now, this same approach works for a lot 272 00:23:43,587 --> 00:23:49,243 of other parameters of trees and there's exercises to compute the number of leaves 273 00:23:49,243 --> 00:23:53,727 of trees and other things like that in the text. 274 00:23:53,727 --> 00:23:58,952 for finding the height of trees, it's much more intricate, it's a different 275 00:23:58,952 --> 00:24:02,227 approach, because it doesn't break down really as well. 276 00:24:02,227 --> 00:24:07,677 and that, but that's an interesting problem, because it's a natural thing to 277 00:24:07,677 --> 00:24:12,452 want to know what's the furthest node from the root in a tree that tells us 278 00:24:12,452 --> 00:24:15,102 more information about the shape of the tree. 279 00:24:15,102 --> 00:24:19,632 so the height derivation is described in the text. 280 00:24:19,632 --> 00:24:25,361 And actually for both, for both binary search trees and trees height was an open 281 00:24:25,361 --> 00:24:30,424 problem for quite a while. so just to summarize what we know about 282 00:24:30,424 --> 00:24:32,819 the shapes of these two different tree structures. 283 00:24:32,819 --> 00:24:39,407 we looked at random binary trees and, and binary search trees built from a random 284 00:24:39,407 --> 00:24:43,592 permutation. those are typical shape of those trees 285 00:24:43,592 --> 00:24:49,042 the average path length, that's the average distance to a node in a random 286 00:24:49,042 --> 00:24:55,473 tree, for binary trees, the square root of p N, for BSTs from random permutation, 287 00:24:55,473 --> 00:24:59,493 that's two natural log N. And again in, in the book there's some 288 00:24:59,493 --> 00:25:04,597 description of, of both of these derivations that are quite intricate. 289 00:25:04,597 --> 00:25:10,387 the height now is known for random binary trees to be twice that average. 290 00:25:10,387 --> 00:25:14,371 and for random BSTs, it's a little more than twice. 291 00:25:14,371 --> 00:25:18,488 It's a constant times natural log N, where the constant is about 4.31. 292 00:25:18,488 --> 00:25:24,755 and again there's lots of things that you might want to study about trees and I've 293 00:25:24,755 --> 00:25:29,082 only, I've only really talked in detail about path length. 294 00:25:29,082 --> 00:25:34,180 but you can find plenty of examples in the book and that show that the same 295 00:25:34,180 --> 00:25:39,714 approach works for many other tree parameters as well and I certainly don't 296 00:25:39,714 --> 00:25:43,416 have time to talk about all, all of them in this lecture. 297 00:25:43,416 --> 00:25:47,243 That's a summary of the study of path length and trees.