Hi.

In the previous video we considered a few naive implementations

of the disjoint sets data structure.

In one of them, we represented each set as a linked list.

Let me give you a small example.

So these four elements are organised into a linked list.

And we treat the tail of this element of this list, so

this last element has the idea of the correspondence set.

And this is well defined idea because it is unique for any list,

and it can be easily reached from any other element in the correspondence set.

So if we need to find the ID of the set that contains this element,

we just follow the next pointers shown here until we reach the tail of this list.

Another advantage is that merging two sets is very easy in this case.

So assume that this is our first set and the second set looks as follows.

Then, to merge these two sets, we just append one of the least to the other one.

Like this.

The first advantage of this merging is that it is clearly constant time.

We just change one pointer.

Another advantage is that it updates the ID of the result in that list

automatically.

Now, with three these elements as ID of the result in list.

It still can be reached for many as an element of this list,

just by following these pointers.

The main disadvantage of this approach is that over time,

lists get longer and longer.

Which in turn, implies that the find declaration gets slower and slower.

Well, we then discussed another possibility to merge two lists,

namely we can do the following.

Again, consider the same two lists.

And now I assume that instead of just appending one list to the other one,

we do the following strange thing.

We'll just change this pointer as follows.

Well, as you see what we get is not actually a list,

however it is a tree whose root is this element and it has two branches,

so we do not get a long trees, but instead we get a tree.

And in this tree we can still treat this last element,

this root element is the idea of the correspondent set.

Because it is unique for this for

this tree, and also it can be reached from many as an element.

So in this lesson, we'll going to further develop this idea.

By doing this we will eventually get a very efficient implementation of

the disjointed data structure.

The general setting is the following.

Each set is going to be represented as a rooted tree.

We will tree the root of each tree as the idea of the corresponding cell.

For each element, we will need to know its parent and

this will be stored in the array parent of size m.

Namely parent of i will be equal to j

if element j is a parent of i or in case i is a root.

Then, parent of i will be equal to i.

So this is a toy example.

Here, we have three trees and there are three roots, five, six, and four.

And these three trees are stored in their right parent as follows, for example, to

indicate that four is the root, we store four in the fourth cell of this array.

To indicate that 9 is the parent of 7, we'll put 9 into the 7th cell.

Recall that MakeSet of i creates a single [INAUDIBLE] set

consistent of just a single element i.

To do this, we just assign parent of i to be equal to i.

This creates the three, whose only element is right and

this is the root of these three.

So for this reason, we assign parent to five be equal to i.

The running time of this operation is, of course, constant.

To find the root of the three that contains a given element, i,

we just follow the parent links from the node i until we reach the root.

This can be done as follows.

While i is not equal to parent[i], namely while i is not the root

of the corresponding tree, we replace i by its parent.

So each time, we go close it, there's a route.

And eventually, we will reach a route.

And then this point, we return the results in element.

The running time of this operation is, of course,

at most, the height of the correspondent tree.

Now, we need to design a way of nurturing to a trees and

there is a very natural idea for doing this.

We have two trees, let's just take one of them and

camp under the root of the other one.

Let me illustrate it with a small example.

Assume that this is our first tree.

It contains just three nodes and this is the root of this tree so

it points to itself, and this is our second tree.

This is the root, so it points at itself again.

To merge these two trees we just change one pointer.

Namely, we say that now.

This node is not the root anymore but its parent is this node.

So we hang the left tree on this root of the right tree.

Once again this node is not the root anymore,

while this node is the root of the resulting tree.

And at this point, there is a natural question.

We can hang the left tree on the root of the right tree.

But also, vice versa,

we can hang the right tree under the root of the left tree.

So which one to choose?

And after thinking a little bit, we realize that it makes sense to hang

a tree whose height is smaller under the root of the true whose height is larger.

And the reason for this is that we would like to keep our trees shallow.

And in turn the reason for this is that the height of the trees

in our forest influences the running time of the find operation.

Namely, the worst case running time of the find operation

is actually at most the maximal height of a tree in our forest.

To give a specific example,

let's consider the following through trees shown on the slide.

In this case, we have a tree of height one and tree of height two.

Assume that we call Union of 3 and 8, in this case we need to merge

these 2 trees and these will discuss there are 2 possibilities for doing this.

Either we hang the left tree under the root of the right tree or vice versa,

we hang the right tree under the root of the left tree.

The results of these two cases are shown here on the slide, and

you see that in the last case the height of the tree increased.

And this is not something that we want, because as we've discussed the height of

this tree influences the worst case running time of the find operation.

So this illustrates that to keep our trees shallow,

when merged into a trees we would like to hang a tree who's height is smaller.

And there's a root of the tree whose height is larger.

Trees for Disjoint Sets

Data Structures

Conoce a los instructores