In the past video, we talked about a naive implementation of disjoint sets that allowed us do a really really efficient fine, but we found that union had to traverse the entire array. There are a lot of elements of this implementation that worked really really well. But there's going to be some elements that didn't work so well, that we need to change. So, let's keep the thing that's a very base of it. Let's keep the array as a thing we're going to be looking up. So, in this new implementation, we have an array, but the array let's not just store the root identity element itself. Let's store some additional information that allows us to create a structure that's going to be way more easy to union together. Let's look at what it says. So, we're going to do is going into continues array where the index is the key. The value in array is going to be negative one when we actually found the representative elements. Otherwise, the representative element is going to be the index of the parent itself, if we haven't found that representative element. What this means is, we're going to call this an up tree. This up tree is going to look just like this. Here, when we originally have four elements; zero, one, two, and three, which are all in their own sets. The up tree is going to have negative one as all of the values inside the array to note the fact that we've found the identity element. We can visually represent this up tree as the elements zero, one, two and three in their own little trees pointing up. But what we can do is we can start unioning these things together to see how this up tree actually works. So, suppose I want to union the element zero and three together. So, to do that, I'm going to connect zero to the three tree or three to the zero tree. So, I'm going to go ahead and keep zero on top, and now I'm going to move the three element to 0.20. So, what this means is, zero is identity element and three points to zero. So, we look at index zero to see what's happening next. One and two are still in its own trees, so they have the value of negative one. Next, we're going to go ahead and union one and two together. So, keeping zero and three unchanged, that's going to be negative one and index zero and zero next three to say that three needs to look at index zero to find out what the identity element is. Now, one being union with two means that two should look at one to find out its identity element and the identity element itself is negative one, here in index one. So, the up tree itself looks like a same up tree at index zero. But then, here index one, it is the identity element, so it just points up, but two points to one itself. Now, it gets really interesting. Now, we can actually union together zero and one. So, these are two elements in two different trees and we want to union them together faster than we were able to do in the simple implementation we did earlier, we don't want to traverse the entire array. Let's look at this tree and see what we can do. Here we have the tree zero and three, and the tree one and two. To update the identity element to one and two to be zero, we simply need to point every single element in this tree to zero. But because two points to one and you can follow along, we simply need to point one to zero instead of pointing one up. Now, we have created a setup where we've updated a single pointer and yet updated the identity element for everything in the tree. So, let's see how this array works. So, zero and three remains unchanged, negative one and zero, as well as the element two remains unchanged, so that points to one. Now, element one simply points directly to zero. Now, both element one and element three point to zero, so we know that both these elements point to whatever the identity element of elements zeros. Since the value in element zero is negative one, we know zeros identity element itself. So, our entire up trees says that zero is the identity element for everything, one points to zero as well as three pointing to zero, and finally, two points to one. So, notice that we're building up this tree where we have pointers that are all pointing up to the identity element itself inside of this up tree. Notice how the union operation required us to only update a single pointer. Looking at an entire disjoint set, here is an example that has a whole bunch of stuff inside of several different sets, just like the example we started with when we talked about disjoint sets. Here, I made one permissible mistake, so that we can actually identify what it is and go in-depth about what it means to build an up tree. Let's take a look. So here, we see the up tree has the array implementation down here and I have the visual implementation on the up tree up here. Looking at this up tree, we see that the root nodes are 5, 7, 4, and 3. So, we expect index five has negative one, this works out well. Index seven also is negative one, denoting it's a root node. Index four has negative one denoting its root node, and here, index three, index three is pointing to six. That's not what this error is actually indicating. The identity element of this set is three, so one of the errors is three should be pointing to negative one. Let's look at three's child. Index six here, we say an index six the identity element, instead, the correct implementation of this array is here three. We need to look at three to find out what the identity element over this three is and it is three. Now, when we union two words together, we can simply update the root node, and by updating the root node, we are able to union two trees together by adding a single pointer. So now, let's look at this. Consider that we just update four and pointing to seven. Now, the three and everything underneath four has identity element of seven. That's awesome. This amazing ability to update the union as quickly as possible in only changing one pointer. What we have is, we have an algorithm that allows us to quickly and efficiently update a data structure that maintains disjoint sets. We'll find that the running time of this is strong but we can do even better, because what's the very worst case? The worst case, it might be a tree that looks like a linked class, where we're linking one node at a time all the way up to the root. We're going to think about how we can improve this and how we can make an ideal tree, the very best case up tree in the very next video. I'll see you there.
