In the previous video you learned about UP-Trees, and you learned how the UP-Tree running time is good, but has a very bad worst case performance, when we have something that looks like a linked list. Let's dive into the actual idea of UP-Trees and see if there's any room for improvement, especially as we're unioning two trees together. Here on this slide, we see that we have a tree that is both short and wide, as well as a tree that's like a links list that really doesn't make us happy. So, we've got a tree that has a nearly ideal structure, and a tree that has a really, really worst case structure. So, two of these, we want to be smart about how we actually union them together. So, remember the running time actually runs proportional to the height. So, we want to keep the height of the tree as small as possible. But we also want to make sure that we when union things together, we're not making the run time of a lot of different node worse. So, looking at our array implementation, we know that a whole bunch of nodes are really useful because they tell us what our parent is. But there's two nodes, that we have just a kind of sentinel value in them. We have the value negative one in two different positions within this array and that says we've reached our representative element. Instead of using the value negative one, I wonder if we can put something that relates to the structure of the tree inside of that index and we're going to explore two different ways we can use a structure of the tree to do that. One idea, is we may want to store the height of the tree inside of the node itself. So, when we reach identity element, it might be really nice to know how tall is the tree beneath us. So, we can always make sure that we're adding the shorter tree to a taller tree, so we never make the taller tree taller. So, to do that, instead of representing the root node as negative one always, we can represent the root of our tree as the negative value of the height, but we can't just use a negative height, so consider the element 12. The element 12 has a height right here of zero. So, to ensure that the height is always negative, we're not going to just simply use the height, we're going to use the height negative minus one. So, a height tree of zero is going to have the value of minus one. The height of tree of three is going to have the value of negative four. So, here updating this array itself, we know that the node four right here has a height of one, two, three, longest path to the root. So, this has a value of negative three plus one or negative four. Here, seven has a height of one, two, so negative two minus one is negative three. So, seven has a height of negative three. Now when we union two things together by unioning by height, what we're able to do is put the shorter tree onto the taller tree. So, what this does is, here seven becomes part of tree four and we know we didn't increase the height of the highest tree at all. In fact, we increase the element or the height of every single element inside of our big tree by one because now the child of the nodes four, but what we didn't do was we didn't actually increase the total height of the tree at all and this is fantastic. This means we're really limiting the height and we're using some extra information inside of the tree. But one downside about union by height, is the height of every single element in this larger tree is being increased by one. So, the other thing we might want to do is consider what results the lease nodes actually increasing in height. So, to do that, we can look at a second union operation. This union operation is called union by size. In the union by size operation, instead of storing the height at every single route identity node, we're going to store the size of elements in that set. So, in doing so, we're just going to do the negative of the size and this works out just fine without having to adapt to it because think about the element 12. The element 12 is it's own root tree. There's one element in the set, so it's going to have negative value of negative one. Here in this set, there's four elements, so the identity element four is going to have the value of negative four. Here in this set, the identity elements seven is going to have one, two, three, four, five, six, seven, eight elements. So, it's going to have the value of negative eight. Now when we union by size, we're going to take the smaller of the two sides trees and union it with the larger of the size trees. So, that means is when I unions four with seven, what I've done is I've only increased the height of four nodes instead of increasing the height of eight notes. In unioning by size, we're able to build up this tree to be an absolutely great tree that's always going to ensure that the height of the tree increases it with as few nodes as possible every step of the way. The great news is, it doesn't actually matter if we union by size or union by height. That both of these algorithms ensure that we have a tree that is O(log n) in height. That we have a tree whose structure has all of the characteristics of a binary tree just like what we studied earlier in the semester. So, we know the height of this tree using either method is going to be bound by O(log n). So, O(log n) is great and it's awesome that we have a tree that's going to be no larger than O(log n). But what we really want to do is not just have something that looks like a binary tree. We want to have something that looks better than a binary tree. So, the second little hack I'm going to do is not just hacking on the union to make the union smart, but to also make sure that find is an incredibly intelligent algorithm. So, let's look at a really tall tree that we're going to use something called path compression on. So, here in this tree, what we have is we have a tree that's quite tall that we might do a find operation on five. During a fine operation on five, we know that we're going to have to follow five to four, four to two, two to seven, seven to nine, and finally nine to 10 to find the identity element. What happens here, is we've got this really, really long path that we hope to never have to take it yet because what we ultimately know is five is going to have the same return value as four, which is going to have the same return value as two and seven and nine is after we use recursion as we're rolling down our recursion. What we can do, is we can take a look every step of the way and actually find out the tree structure can be updated, so that every single one of these nodes point to 10 directly. So, seven going back down knows result is 10. It can point directly to 10. Two, knowing the result is 10, can direct point to 10. Four, knowing the result is 10 can point directly to 10 and five can also point directly to 10. So, notice after this process we have updated this tree such that all of the elements that were intermittent along the way now point directly to the root node itself. Notice as I remove the edges that we've updated, notice how so few edges exist and now given that each of these sub-elements only had a height of one, we know that each of these elements are now that much closer to the root. So, the idea here is by ensuring that whenever we have a path to the root, we're going to go through and make sure that every element that we took along that path now points directly to the root node itself. To make it closer and closer to this ideal perfect tree where we are a root node and a number of another nodes underneath it. So, this is absolutely fantastic and the end goal that we're trying to build as we're building an UP-Tree. So, the very end of this series of lectures, I want to do a little bit of analysis on exactly what the running time of the beat of our UP-Tree is and how well we implement disjoint sets and how we can use this to build amazing algorithms when we get to graphs. So, I'll see you for analysis in the next video. I'll see you there.
