Trees for Disjoint Sets

Loading...

Del curso dictado por University of California San Diego

Data Structures

1604 calificaciones

University of California San Diego

Data Structures

1604 calificaciones

Curso 2 de 6 en SpecializationData Structures and Algorithms

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space!

De la lección

Priority Queues and Disjoint Sets

We start this module by considering priority queues which are used to efficiently schedule jobs, either in the context of a computer operating system or in real life, to sort huge files, which is the most important building block for any Big Data processing algorithm, and to efficiently compute shortest paths in graphs, which is a topic we will cover in our next course. For this reason, priority queues have built-in implementations in many programming languages, including C++, Java, and Python. We will see that these implementations are based on a beautiful idea of storing a complete binary tree in an array that allows to implement all priority queue methods in just few lines of code. We will then switch to disjoint sets data structure that is used, for example, in dynamic graph connectivity and image processing. We will see again how simple and natural ideas lead to an implementation that is both easy to code and very efficient. By completing this module, you will be able to implement both these data structures efficiently from scratch.

Trees for Disjoint Sets7:54

Union by Rank9:41

Path Compression6:07

Analysis (Optional)18:17

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

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.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play