1 00:00:00,012 --> 00:00:06,012 Today, we're going to talk about trees. this is the first, second half of the 2 00:00:06,012 --> 00:00:09,287 course. This is the first of, of a series of 3 00:00:09,287 --> 00:00:14,192 lectures on applications. just a little bit in the way of 4 00:00:14,192 --> 00:00:19,932 orientation before we begin. for the first half of the class the first 5 00:00:19,932 --> 00:00:23,063 thing we do is introduce analysis of algorithms. 6 00:00:23,063 --> 00:00:26,755 but then, we spent, have spent the rest of the time surveying the basic methods 7 00:00:26,755 --> 00:00:31,987 that we need in terms of mathematics, in order to do scientific studies about the 8 00:00:31,987 --> 00:00:35,838 perfomance of algorithms. And then, we finished off last time by 9 00:00:35,838 --> 00:00:40,401 introducing analystic combinatorics. So, this is all about mathematics and 10 00:00:40,401 --> 00:00:44,932 about technique. now we're going to and now we're going to 11 00:00:44,932 --> 00:00:50,347 switch to the second half of the class. We're going to switch to applications. 12 00:00:50,347 --> 00:00:56,322 And we're going to talk about some basic classic combinatorial classes with lots 13 00:00:56,322 --> 00:01:00,227 of applications. And we're going to look at techniques 14 00:01:00,227 --> 00:01:05,113 from analytical combinatorics that we use to study them, including applications to 15 00:01:05,113 --> 00:01:09,469 the analysis of algorithms. and this will bring us to really basic 16 00:01:09,469 --> 00:01:14,468 common attoric class with all kinds of applications, trees, permeations, strings 17 00:01:14,468 --> 00:01:19,240 and tries, words and mappings. we'll be using labeled and unlabeled 18 00:01:19,240 --> 00:01:24,063 classes alternating with ordinary generating functions and exponential 19 00:01:24,063 --> 00:01:29,836 generating functions really applying all of the mathematical techniques that we 20 00:01:29,836 --> 00:01:35,470 learned in the first half of the class. So today we're going to begin with trees. 21 00:01:35,470 --> 00:01:40,927 And we'll start off by talking about the basic definition of trees and forests. 22 00:01:40,927 --> 00:01:46,392 To begin I'll review what we've talked about in terms of binary trees by 23 00:01:46,392 --> 00:01:50,108 contrast with the general trees that we're going to talk about today. 24 00:01:50,108 --> 00:01:54,645 recall that a binary tree is an external node or an internal node in two binary 25 00:01:54,645 --> 00:01:58,002 trees where the order of the internal node is significant. 26 00:01:58,002 --> 00:02:04,552 so at the top is a root and in this case, that root has two binary trees or two 27 00:02:04,552 --> 00:02:10,277 [COUGH] internal nodes as its children. and then, down at the bottom we have some 28 00:02:10,277 --> 00:02:14,952 nodes called leaves that have both of their children are external. 29 00:02:14,952 --> 00:02:22,144 the external nodes are signified with little boxes and the internal nodes are 30 00:02:22,144 --> 00:02:27,591 signified with circles. we talked about binary tree we've talked 31 00:02:27,591 --> 00:02:31,960 about those before. so now, we refer to the level or the 32 00:02:31,960 --> 00:02:36,622 depth of a node in a tree. starting with a root at depth zero. 33 00:02:36,622 --> 00:02:40,272 the children of the root at depth one and so on. 34 00:02:40,272 --> 00:02:45,347 and the deepest node in the tree that's what we'll call the height of the tree. 35 00:02:45,347 --> 00:02:49,462 and we'll look at other parameters of trees later on. 36 00:02:49,462 --> 00:02:54,937 now remember one of the first problems that we looked at in the last couple of 37 00:02:54,937 --> 00:02:58,927 lectures is how many binary, binary trees are there within nodes. 38 00:02:58,927 --> 00:03:03,992 And that's the [UNKNOWN] numbers. and we did a derivation with the symbolic 39 00:03:03,992 --> 00:03:08,583 method that I'll just rush through because we've done it so many times, but 40 00:03:08,583 --> 00:03:14,022 just to get back on the notation. so we have a generating function which is the 41 00:03:14,022 --> 00:03:19,117 sum over all objects is either the size of that object which collects together 42 00:03:19,117 --> 00:03:23,470 objects by their size. we have atoms that are internal nodes and 43 00:03:23,470 --> 00:03:26,240 external nodes. And then depending on how you set the 44 00:03:26,240 --> 00:03:29,614 size of those atoms that's what we're going to count. 45 00:03:29,614 --> 00:03:32,208 And this case, we're counting internal nodes. 46 00:03:32,208 --> 00:03:35,935 And then, we have a combinatorial construction that comes as, as a 47 00:03:35,935 --> 00:03:40,837 mathematical representation of our explicit definition of what we mean by a 48 00:03:40,837 --> 00:03:44,178 binary tree. And then our basic transfer theorem 49 00:03:44,178 --> 00:03:49,444 translates that construction immediately into an equation on the generating 50 00:03:49,444 --> 00:03:55,215 function which then we can solve and get asymptotic estimates of the coefficients. 51 00:03:55,215 --> 00:04:00,479 so that's just a quick review of the symbolic method for binary trees just to 52 00:04:00,479 --> 00:04:06,012 set the context for different problems that we're going to do in this lecture. 53 00:04:06,012 --> 00:04:13,057 so now, in general, the mathematical, classical mathematical concept of the 54 00:04:13,057 --> 00:04:20,067 tree is in terms of forest. So, forest is a set of trees and the tree is a forest 55 00:04:20,067 --> 00:04:25,912 with a root added the top. and there's actually just from this quick 56 00:04:25,912 --> 00:04:31,073 observation the generating function that enumerates for us is just one of the 57 00:04:31,073 --> 00:04:35,383 trees, or the generative function that enumerates trees is just Z times the 58 00:04:35,383 --> 00:04:40,042 generating function that enumerates for us corresponding to adding the root. 59 00:04:40,042 --> 00:04:43,992 so this is a recursive definition but these are recursive structures. 60 00:04:43,992 --> 00:04:46,317 A forest is a sequence of disjoined trees. 61 00:04:46,317 --> 00:04:49,777 A tree is a node called a root. It should say forest is emptier, 62 00:04:49,777 --> 00:04:53,812 instead of just disjoined trees. Tree is a node called a root connected to 63 00:04:53,812 --> 00:04:59,218 the roots of trees in a forest. And so now a root can have any number of 64 00:04:59,218 --> 00:05:06,271 children including zero in the leaf nodes of the nodes with zero children. 65 00:05:06,271 --> 00:05:10,730 so [COUGH] the, and then the level is the same as before. 66 00:05:10,730 --> 00:05:18,095 we start with the root at depth zero, the children of the root at depth one and so 67 00:05:18,095 --> 00:05:22,554 forth. and the height is again the deepest node 68 00:05:22,554 --> 00:05:26,711 in the tree. in contrast to binary trees, we don't 69 00:05:26,711 --> 00:05:32,946 have external nodes in, in general trees. so that's now a question comes up 70 00:05:32,946 --> 00:05:40,146 immediately is enumeration. How many forests are there within nodes? so this, 71 00:05:40,146 --> 00:05:49,855 these are all the forests with 1 2, 3 and 4 nodes and immediately right away, you 72 00:05:49,855 --> 00:05:56,640 can recognize that the catalan numbers are rising yet again. 73 00:05:56,640 --> 00:06:04,872 so there's 5/4 with 3 nodes just 3 individual nodes or tree size 2 and 74 00:06:04,872 --> 00:06:11,017 another node in either order. or the node, root node connected to 2 75 00:06:11,017 --> 00:06:16,347 children or the straight line, which is a root connected to a child, 76 00:06:16,347 --> 00:06:20,647 connected to a child. Notice the order of significance, the 77 00:06:20,647 --> 00:06:27,006 forest is a sequence of trees and that's consistent with computer applications 78 00:06:27,006 --> 00:06:31,783 where we have to represent the thing in a computer some way and we pick a sequence 79 00:06:31,783 --> 00:06:35,211 usually. so anyway, the catalan numbers are here. 80 00:06:35,211 --> 00:06:38,485 And, of course a tree is a root connected to a forest. 81 00:06:38,485 --> 00:06:42,557 So, if you attach roots to all of those, you get all possible trees. 82 00:06:42,557 --> 00:06:45,592 And it's the same numbers with one, shifted over by one. 83 00:06:45,592 --> 00:06:50,272 So let's look at the analytic combinatorics for deriving the catalan 84 00:06:50,272 --> 00:06:56,393 generated function for trees and forests. so and we just follow through the basic 85 00:06:56,393 --> 00:06:59,367 steps that we've outlined many times before. 86 00:06:59,367 --> 00:07:04,733 and we're going to be doing this a lot but a small mistake leads to completely 87 00:07:04,733 --> 00:07:08,352 the wrong answer, so it's good, good to be careful. 88 00:07:08,352 --> 00:07:13,625 so F is the class of all forests and the size is going to be the number of nodes 89 00:07:13,625 --> 00:07:15,108 where our atoms are. Now, 90 00:07:15,108 --> 00:07:20,220 there's just one kind of node and its got generating function Z. 91 00:07:20,220 --> 00:07:24,901 And G is the class of all trees on the same atom and again the same size 92 00:07:24,901 --> 00:07:28,042 function. So, those are two combinatorial classes. 93 00:07:28,042 --> 00:07:34,282 and now, we can use our definitions of those classes to develop constructions 94 00:07:34,282 --> 00:07:39,687 directly from the definitions. what did we say? we said, a forest is a 95 00:07:39,687 --> 00:07:44,041 sequence of trees and a tree is a root node in a forest. 96 00:07:44,041 --> 00:07:49,089 And that immediately corresponds to those two constructions. 97 00:07:49,089 --> 00:07:55,455 and then the transfer theorems immediately give us the for For those two 98 00:07:55,455 --> 00:08:02,011 combinatorial classes. F(z) is 1/1-G(z) and G(z)=zF(z), that's 99 00:08:02,011 --> 00:08:09,797 what I referred to in a previous slide. So now, if we just solve that we get F(z) 100 00:08:09,797 --> 00:08:16,572 substitute in 1-zF(z) for G(z) and then solve for F, you get F(z)-zF(z)^2=1. 101 00:08:16,572 --> 00:08:22,032 and that's exactly identical to the catalan generating function, so it means 102 00:08:22,032 --> 00:08:26,885 that the number of forests with N nodes is exactly, exactly equal to the number 103 00:08:26,885 --> 00:08:31,788 of trees with N nodes, which is the catalan numbers, which we know the 104 00:08:31,788 --> 00:08:37,167 asymptotics for and the number of trees with N nodes, the number of force with 105 00:08:37,167 --> 00:08:40,202 N-1 nodes, so it's got a factor of 4 left. 106 00:08:40,202 --> 00:08:45,317 so that's a symbolic method that shows that the number of force and the number 107 00:08:45,317 --> 00:08:49,247 of trees is exactly the same. Now, from an analytic point of view, 108 00:08:49,247 --> 00:08:53,981 we're happy to get get the result. But usually in combinatorics, when you 109 00:08:53,981 --> 00:08:58,224 find that you have two classes, that enumerate exactly the same what you want 110 00:08:58,224 --> 00:09:02,539 to find is a bijection showing that a correspondence between every member of 111 00:09:02,539 --> 00:09:07,697 one class and every member of the other. And, in this case, that bijection is 112 00:09:07,697 --> 00:09:13,447 important because it gives us a way to represent forests and trees in the 113 00:09:13,447 --> 00:09:18,287 computer conveniently. so here's how that bijection goes. 114 00:09:18,287 --> 00:09:24,572 Every forest with N nodes corresponds precisely to a binary tree with N nodes. 115 00:09:24,572 --> 00:09:30,071 now forest that node can have multiple children, in a binary tree, a node can 116 00:09:30,071 --> 00:09:34,954 have exactly 2 children. So the way the correspondence goes is 117 00:09:34,954 --> 00:09:40,602 that for every node, we connect it to its left child and its right sibling. 118 00:09:40,602 --> 00:09:46,364 So the node at the left in the forest corresponds to the top node in the binary 119 00:09:46,364 --> 00:09:51,337 tree and so forth. and that's a one-to-one correspondence between force 120 00:09:51,337 --> 00:09:55,480 and binary trees. Another way to look at this may be even 121 00:09:55,480 --> 00:10:01,059 easier to see, called the rotation correspondence. If you take this binary 122 00:10:01,059 --> 00:10:06,247 tree [COUGH] and connect it up as if we have the nodes in the forest, 123 00:10:06,247 --> 00:10:10,001 you can see that you have the forest kind of rotated. 124 00:10:10,001 --> 00:10:15,952 and that's a very useful and easy way to represent forests in general trees within 125 00:10:15,952 --> 00:10:22,151 a computer because a binary tree is easy to represent in chunks in memory where 126 00:10:22,151 --> 00:10:27,032 every node has whatever information is associated and its two children. 127 00:10:27,032 --> 00:10:32,257 whereas in the forest, you have to deal with a variable number of children per 128 00:10:32,257 --> 00:10:38,157 node, which can be inconvenient and difficult in some computing environments. 129 00:10:38,157 --> 00:10:42,357 just as an aside, that these points what we're thinking 130 00:10:42,357 --> 00:10:46,982 about is the idea of an algorithm for growing binary trees. 131 00:10:46,982 --> 00:10:52,826 and I want to show that because I'm going to be showing a lot of binary trees. 132 00:10:52,826 --> 00:10:58,917 and the exercise of writing a program for drawing binary trees is a worthwhile 133 00:10:58,917 --> 00:11:04,568 exercise for everyone to do. So the most natural approach that we use 134 00:11:04,568 --> 00:11:11,099 very often, particularly when talking about a sorting and searching algorithm 135 00:11:11,099 --> 00:11:17,340 is to well, first of all, the y-coordinate is easy, that's just well, 136 00:11:17,340 --> 00:11:21,999 it's the depth but since they go down, it's the height minus the depth. 137 00:11:21,999 --> 00:11:26,846 So, we start with the root at the, at the highest and just subtract 1 so we know 138 00:11:26,846 --> 00:11:32,614 the y-coordinate of every node. the x-coordinate of the node the easiest 139 00:11:32,614 --> 00:11:37,904 way to set that up is to just do a recursive, in order traversal, 140 00:11:37,904 --> 00:11:44,137 traversal of the tree and just assign x-coordinates every time you reach a 141 00:11:44,137 --> 00:11:47,469 node. and that's corresponding to set of 142 00:11:47,469 --> 00:11:51,467 recursive programs says, what's the coordinate of the root. 143 00:11:51,467 --> 00:11:54,810 it's the number of nodes on the left plus one. 144 00:11:54,810 --> 00:12:00,442 and then the coordinate, the x-coordinate on the right side is bigger than that. 145 00:12:00,442 --> 00:12:05,628 And you can see immediately that that is number one, it's easy to assign the 146 00:12:05,628 --> 00:12:09,290 coordinates, just do an in-order traversal of the tree. 147 00:12:09,290 --> 00:12:13,582 and number two, it spaces the nodes in the tree out nicely. 148 00:12:13,582 --> 00:12:19,664 usually when we draw big trees we leave, big binary trees, we leave out the 149 00:12:19,664 --> 00:12:23,934 external nodes. now, there's a problem with this, is that 150 00:12:23,934 --> 00:12:28,312 you get the distracting long edges for some kinds of trees. 151 00:12:28,312 --> 00:12:33,197 particularly for say, binary trees represent general trees. 152 00:12:33,197 --> 00:12:38,767 and you can use a similar algorithm like this for general trees by the way. 153 00:12:38,767 --> 00:12:43,423 but anyway, that's a problem. So what we do sometimes is take the 154 00:12:43,423 --> 00:12:48,064 x-coordinate and at every level we just evenly space the nodes. 155 00:12:48,064 --> 00:12:54,050 If there's four nodes at that level, we'd evenly space them and send them on their 156 00:12:54,050 --> 00:12:57,753 route node. And that's a useful way to draw trees 157 00:12:57,753 --> 00:13:03,776 because it gives a profile of what the trees how thick the trees are, how many 158 00:13:03,776 --> 00:13:09,462 nodes there are at each level. And that's an interesting thing to know 159 00:13:09,462 --> 00:13:15,106 about in some kinds of analysis. so just, this is what a random binary 160 00:13:15,106 --> 00:13:20,884 tree looks like with this idea. And actually when you see random binary 161 00:13:20,884 --> 00:13:24,331 trees they have many, many different shapes. 162 00:13:24,331 --> 00:13:29,453 And if we were to do random trees or random forests as well you'd see quite A, 163 00:13:29,453 --> 00:13:32,964 A collection of different and interesting shapes. 164 00:13:32,964 --> 00:13:38,163 and so, the challenge that we have that we're going to go into and the reason 165 00:13:38,163 --> 00:13:43,029 that I wanted to draw these big binary trees is to make clear what that 166 00:13:43,029 --> 00:13:45,946 challenge is. And so, we have to analytically 167 00:13:45,946 --> 00:13:51,345 characterize this in some way. maybe averaging over all of these or 168 00:13:51,345 --> 00:13:55,029 whatever it is that we're doing in terms of the analysis. 169 00:13:55,029 --> 00:13:59,198 it's going to have to explain this this kind of behavior. 170 00:13:59,198 --> 00:14:05,342 And remarkably we're able to get very far in doing that and so that's what we'll 171 00:14:05,342 --> 00:14:09,242 start doing now. That's just a brief introduction about 172 00:14:09,242 --> 00:14:10,385 trees and forests.