A&DS S01E08. Disjoint Sets

0:00 [Music] so hello everyone today we'll talk about the joint sets or sometimes it's called union fine date structure sometimes it's also called merch find but it's quite rarely said usually it's called the joint cells or union find so it's it's not a special data structure it looks pretty strange but but it's uh surprisingly important in many

0:46 algorithms which we will discuss late in this course mostly in the next year because uh we will discuss graph algorithms in the next in the third semester so it will be in in the next year uh but maybe maybe we'll use it in some another algorithms in the next semesters also mostly in this semester we'll learn some data structure some base and later we'll use some we will use this data structure to uh to make some efficient algorithms so so what is this drain sets it's very simple data structure it maintains the set of some objects uh let's say for simplicity that we have

1:33 some n objects ah let's say one two three four five six seven good enough so we have some seven objects and these objects are grouped into some sets so each o each object belongs to exactly one set so we have some uh number of disjoint sets so that's why that's why it's called disjoint sets so for example here we have like a set of these three elements these two elements and these two elements

2:22 okay cool so it's just just like we divide all elements into some sets in some principle uh huh no we have no summer time in russia it was deprecated few years ago sorry i have i have a google calendar if you are if you're just if you're afraid you may forget about it i have a google calendar of my twitch teams so you may just copy this calendar into your calendar to make sure you will not forget about future lectures

3:07 what i was talking about ah you join so we have some objects these objects uh you can download this color from from the to which description it is somewhere in in the bottom of the twitch dashboard um so here so we have some elements they are divided into some uh sets so what what we want to do these sets we want to perform two type of operations so basically it's union and find why the second name of this circuit structure is union fight first operation is union

4:00 union is it's bad word for for programming because union is a resort word word for c plus plus so you can't make a function named union so i usually call it same like unite or join or something like that but here i will write union because i'm not writing in c plus plus so what this function does ah it gets two arguments we have arguments x and y and it simply unite these two sets so we have we take the set that contains element x uh let's see this element x we take the element uh the set which contains element y and we just unite these two sets into one big set

4:47 so we have these two sets so make one big set like this uh that's the first operation we just take these two sets and make one big set out of them and the second operation is to find the set which contains element x it's usually called find i also i usually write get because i know for for historical reasons i think well let's let's make it more simple let's say find x

5:35 so so this function returns the set which contains element x that's all we have we have these two operations first operation is just unite two given sets into one and second operation is return the set which contains the given element that's that simple that's all now ah in the second operation we need to return this set which contains the element so we need some another class of objects which represents the sets yeah so we have the elements

6:22 and also we have the sets of elements so we need like two types of objects ah that's not very complex we have two types of objects so to make it more simple we will do the following instead of uh returning the set which contains the given element we already own one special element of this set so for each set there is this for each set uh we will mark one element and say that this particular element is the representative of this set so for each set one element is special let's say this element like this element and this element so these three elements are special

7:10 elements so and each set contains exactly one special element this element is representative of this set and now instead of returning this special objects offset we will return this representative of this set for example here if we recall find from element let's say 6 it will return free and if you call find of element and say 5 it will return 5. so element six belongs to this set in this set three is a representative element so we will show three and element five belongs to this set five is representative of this set so we will return five

7:56 ah important thing that represents always return the same element so if you if you call uh fine from two elements of the same set you will you will get the same element each time so if you call like uh find from element two it will return the same element five uh so this this is how you may uh understand that two elements belong to the same set so if you want to check if two elements belong to the sunset you call fine from both these elements and check that this file returns the same uh representative element cool you're too quiet today let's write something in each other like

8:41 so i understand you you everything is clear by now um that's all we have these two operations yeah like this cool now let's uh first let's discuss some very simple way to implement just join sets uh first implementation uh very simple uh let's just make a array let's make array p and element in ray p will be the representative of element x so each element of array we have seven elements

9:44 so we make array of size n and for each element of the array we will maintain the representative of the set which contains element x for element one the representative is five for element two it's five for free it's r three four four it's seven five three and seven that's all now let's implement these two functions uh let's have this function find so how to find how to find representative of element x no it's quite simple we

10:30 just have the array of whole representative of all elements so we just look on this array find the representative and the terms it's very simple that's all now how to unite two sets into one so let's see of x and y first let's uh i mean let's get a representative of these two sets so let's say x is the representative of the set x and y is representative of set y now uh

11:18 what we need to do for example we need we have these two sets is this x this is y so what we need to do is just uh take all elements of one set no we need to first we need to choose what element will be the representative of this big set uh for example let's say that element y will be the representative of this uh union of two states so so we need to take this big set and set the representative of all elements in the set to y uh for this for these elements it's already y but for these elements we need to set the representative from x to y so we need to find all elements which

12:04 representative is element x and change it to y so just iterator all elements and it's from one case it's quite uncommon to have indices from one but okay we started from one so let's let's keep it r is from one to n and say if representative of i equal to x then set representative to y that's all so it's very very very simple realization of this idea now let's calculate time complexity

12:52 what is the tank of next year no for find it's obviously constant another one it's constant and for union it's obviously linear because we have this cycle so we always make any any iterations of this cycle so that's big o of n yes we will definitely prove it later on yeah that's just the first version okay that's the simplest implementation of the disjoint set it's quite bad because union takes linear time we don't want to spend linear time now

13:38 let's stop here for a little let's talk about uh how many union operations can we perform in our data structure how fine is constant we just look in the array and array lookup take constant it's not a hash map it's not even a hash map it's just array so we have very fast operation find but very slow operation union um let's go back so ah what i want to talk about is what is the number of operation of union operation can be in your algorithm uh since we only

14:25 unite these sets into big ones uh the number of union operation cannot be more than n minus one so we cannot have more than n minus one operations well that's that's basically because in in the beginning we have n sets and each union operation decrease number of sets yeah so we we have one set instead of two sets so we're decreasing the number of sets so in the in total we'll have no more than n minus one unit operations uh so now

15:12 later uh in data structures like this then you know the total lifetime of your data structure like if you know that the number of operations is constant so you start with these sets and you only make an n operations until you reach the final state of the data structure you usually calculate not the single time of operation but the total of all operations so instead of calculating the time of single operation we will usually calculate the total time of all united operations that's more like amortization it's like the basic case of the amortized time when you calculate the amortized time you like divide the total time by the number of operations but here you know the number operations is already is is constant uh it's always will be n

16:01 so you if you just calculate the total number of questions divided by n you will get the amortized in this case the total time of all your union operations will be tal will be n squared that's all okay that's all about this simple implementation now let's move to the something more more complicated first optimization let's see what we're doing here here we just iterator all elements uh which belong to one set and

16:47 like move these elements to another set so we need to find all elements in array p equal to x and change it to y so uh is it possible to iterate over all elements with given value faster than just look on all or all elements so can we just like in this array we need to find elements with x equal to let's say three so we need to find these two elements and change these two values to seven right so uh let's try to find these two elements uh without uh scanning the whole array so how can we do this

17:32 ah quite easily we can just maintain the list of all elements for each value x so for so for each representative let's keep the list of elements which belongs to corresponding set so one two three i don't have i only have representative three five and seven let's have representative three five and seven so for free we have elements three and six four five we have elements one two and five uh this list shouldn't be sorted so we have like for example two five and one uh and for

18:19 seven we have seven and four and we also have empty lists for one two three four five six so so let's maintain n lists for each element x we will maintain the list of all indices uh such that the value equal equal to x uh i will go back here and go here so how can we how can we rewrite this union let's say x will find x y equal to find y

19:05 now we need to take all elements with value equal to x uh to do this we just take the corresponding list we take this list and iterate over these elements so we take these elements go in array p and change these values to y let's call this lists so we take list of element for value x so again what is the change here

19:52 instead of iterating all elements we iterate only over elements with value equal to x so we don't need to to make this check we only need to redraw or elements with value equal to x ah and just change this value to y not so all right we also need to fix the list we also need to uh transfer these elements from these lists to these lists so this is x this is y so we need to iterate all these elements change the representative to y and move these elements to this list

20:49 we also can clear this list and then just for simplicity just just to free some memory it's not important but just okay that's all now did we change something in the time complexity uh let's think uh the find still works the same so the define function is still the same so we just return the value from arrow ap so it still works in constant time uh what about the union uh did we actually change the

21:36 total time for the separation uh we it it actually it it obviously can work in linear time so in the worst situation when for example we have uh one big set of elements so we will iterate or all elements here literally over all elements of some big set so the the number of elements in this set can be linear so this time the number of iterations of this cycle may be linear delete my file not sure what you mean

22:27 no we never remove elements from this set and we never modify anything to make similar two simple operations we may unite two sets and check the which set belongs to given maybe i don't get your question let's go back so what is a multiple yeah so let's go back here again again let's think uh this union function obviously may work in linear time in worst case this function may work

23:15 linearly but what is the total time is is it possible that the total time is still in square so is there a situation when this procedure is called n times and the total time complexity of all these n calls is still about n square

24:03 okay just let you think little while i'm erasing this okay uh so the answer is it is possible sometimes if you call this union function in wrong order you may get a quadratic number of operations for example if you have an elements

24:48 and in the first union operation you unite these two elements so the first union let's see so you call union from one and two so you unite these two elements and you spend like one operation so you need to change ah again so so array p looks like this so you called union for elements one and two and you need to change uh the representative from one to two so you change this one to two and it cost you one iteration

25:36 and now you call union for elements two and three for example so you need to change the representative elements from two to three so you change these two into three one and two three and three and it cost you two operations and now you make union of three and four and so on you need to change these three elements to fourth and it cost you three operations and so on so the total number of all operations will be about n squared

26:28 is clear enough so we have this sum uh the first operation goes through one operation then it goes your second second ratio costs you two operations and so on so the sum of these times will be something like n multiplied by n minus one divided by two something like that so it is big omega of n square yep so it's it's it's not actually better than we have here so we still have n square time complexity here uh this kind of said we tried to improve everything but we have the same time complexity but the good thing is that we can we

27:13 actually can improve this by using the simple trick uh let's look here when you unite two sets you have set contain x and second containing y you may choose which elements uh which element will be x and which element will be y so we have two sets set x and set y you may transfer all elements from x to y so you may find all elements uh with representative equal to x and change it to y or alternatively you can find all elements in this set and set element set representative to x so you can move all elements from here to

27:59 here or you can move all elements from here to here let's look on the size of these two sets and let's make the x the smallest of these two sets so let's look on size of this list for example and if x is the biggest of these two sets let me just swap them so let's say if lists of x size is bigger than lists of y size we just swap them and now x is always the smaller of the set so we always take the smallest set

28:48 and transfer the elements to the bigger set that's the whole trick quite easy right now let's think did did we actually change something did we concentrate uh let's look on the total time complexity again now this situation like here will not happen because for example if you unite elements one and two what will happen again we have our ap you have one two three four five six and so on you'll make union of elements

29:34 one and two so again you check which which uh set a smaller and move elements from one to two so you change this one two two and now now you make union of two and three but you see that the set of element three is side half size one and set of eleven two have size two so instead of moving this element elements from set two to set three you move one element from set three to sets two back so we change these three two so it's only cost you one operation ah now again you try to unite three and four so you unite these two set you have three elements here only one element here

30:19 so it's faster to move this one element to this set so you change this to two and again cos one pressure so the total number of all operations will be linear huh yeah yeah the worst case as you as your actually mentioned uh the worst case is when we merge two sets of equal size so when i have two sets of equal size then we need to go from one big set and transfer all elements to another big set this may happen but let let's think about the worst possible case

31:04 what is the worst possible case uh workforce location is when you always merge two sets of equal size what will be the total time time complexity what will be the total complexity let's look on some element imagine you have one element we have some element x let's look on the lifetime of this element let's see how many time can we move this element from one set to another set so in the beginning we have element x in the set of

31:50 of of itself so we have set of size one ah next time when we will move the element to another set is when we will unite this set to with another so we have another set of size at least one so we'll combine these sets into one you have sets of size at least two yes and square over two is the same as n square yeah oh no it's time complexity here we just get rid of all constants so yeah one operation is time capacity of one operation is still linear i'm talking about this total time

32:36 complexity here here the time complexity of one operation in the worst case will be linear so if we still if we merge two sets of size n over two so we have one big set another big set we have n over two elements here and our two elements here yeah so in the worst case we need to transfer all these elements to this set so we take n over two l operations uh so it's still linear worse time time complexity for one operation is still linear that's right but i i'm talking about total time complexity so i want to calculate the total number of operations in all union operations

33:23 and last time the total total time was n square and i claim that now it's smaller it's not now if we use this trick the total number of operations of all union liberation will be smaller than n squared uh-huh so let's go back let's try to calculate the total number of all moves so in a single operation here what what caused the time complexity it goes with this for these these loops in in each loop we just move see this is one move operation let's calculate the total number of moves of all elements during the whole the lifetime of this

34:09 data structure so we start from elements of sets of size one so each element belongs to a special set containing only this element and each time we unite two sets into one big set so in total we have n minus one union operations i want to calculate the total time complexity of this n minus one union operations and i claim that it is smaller than n square because this y is smaller than square let's look on some element let's look on element x let's see how many time we can move this element here so for each element x let's calculate

34:55 the number of times we move this approach so we change the representative for element x so how many times my e times this p of x changes so if you calculate this we will calculate total time complexity because this total time complexity is some from this part and in this part we just move element from one set to another so we change the representative for this element if we calculate the total number of times we change uh the representative for the given

35:40 element we will calculate so we have element x uh in the beginning we have the set of one element x now each time we move the element x element x is moved to some set with bigger size so first we have element x in a small set of size one ah next time we move element we merge this element x of some another set so we have element x in some set of size at least two next time when we will move element x it means that element x belongs to some set which is smaller of these two sets so when we will move this element x next

36:26 uh we will merge these two sets and sum another set of size at least two so element x will belong to some set of size at least four and so on next time when we will move element x it means that element x belongs to small smaller of these two set uh so it means that we unite our set with another set with size at least four so we have some another size set of size at least four we make another union so the size of this set is at least eight and so after each union which causes the element x to move

37:12 to another set the size of the set which contains element x is increased at least twice so the total number of of times when we move element x from one set to another is at most logarithmic n that is true for each element so each element of our data structure is moved from one set to another at most logarithmic times so the total num the total number of moves is the same thing complexity is big o of n logan

38:01 let's mark it here clear enough again you're too quiet just say something from time to time that's all and this is actually this is actually quite important technique uh especially so most of you come from school forces so you learn some competitive programming it's quite important technique when you need to make some merchable data structure so if you have some data structure and you can like insert elements one by

38:47 one and you want to make merchable data structure you want to be able to merge to the structures into one so the easiest technique about to to do this is just to take a smaller data structure and put elements one by one in the bigger data structure and if you do this the total number of moves of elements from one day structure to another structure will be in logan and you can see in some tasks when for example you have some tree and you need to calculate something on this tree so for each you may take that structure from one of the you need to unite all children into some big data structure you have data structure for each child of the given node and you need to merge these data structures into one

39:32 so you can do it by by taking the biggest of the data structures and just moving all elements from other data structures to this big data structure and if you do this just if you always move elements from small distortion to big data structure the total number of moves will be logan for example if you if you have a binary hip yeah like we discussed on on on the second lecture binary hit and you want to be able to merge two binary hips you can just copy all elements from small binary heap to the big binary heap so in total you will have analog and moves from one hip to another hip and you can move element from one hip to

40:18 another in logarithm time so total time complexity will be n log square something like that yes we'll talk about medium spanning tree next year but yes we have this in the plan it's a long course we'll we'll discuss many data structures before okay cool now the fight for the final part now we'll finally build the cool data structure so this hole is a very important basic actually so if you again again this technique like i

41:04 discussed here here it is very important when you need some mergeable data structure if you have some data structure which you can you can move for elements one by one you can make mergable data structure of total cost like in logan now i will erase everything and just rewrite it from scratch okay one final part now we'll discuss actually how how to make this data structure faster than in in logarithmic time the idea is that the idea is to get rid of this logarithm so logarithm is pretty small function but still quite big so we will make another data structure which do the same

41:50 operations which works faster than in logarithm time let's go so what will be the idea okay yeah go what is the idea again let's have some some sets one two

42:38 three four five six seven eight so we have some sets like here here and here so we have some sets of elements uh in each set we have one special elements representative elements we have representative representative and representative we will maintain these sets as trees for each tree the root element of the tree will be the representative of this set for example for this set one two four we may have three like this two let's have one here and four here

43:27 so these three represents this set the root element is the representative and all elements have links to the parent of of this element in the dream uh for this set for example we may have something more than we have we have different dream we may have like three and here we have five and here we have six we have three like this so these three represents this set again element three is the root of the tree and each element have a link to the parent element in the drink and here we have eight and seven let's have eight and seven

44:14 that's all that's how you represent this sense how to how to implement this very easily to implement the this we only need to have links from each element to the parent element so again we need only one array in this array we will maintain the pointers from element to the parent element so we have array p p of x is the parent of element x for example here what we have here p

45:09 ah from 154 it's two and units two for five it's three four six it's five four seven it's it ah what should we write as a parent element for for the roots of these trees uh it depends on your implementation you may write something special something special here like minus one but actually it's uh easier to write the pointer to itself it's easier to make pointer to itself here

45:56 if you do it like this the code will be simpler just we'll we'll write the code later i believe the whole code will be here except let's see so it will be two free and go next now let's implement the two operations

46:43 we need so we need operations find and union let's start the operation let's say find so how to find the representative of the set so we start from element x and we go to the root of the tree using these links so we go from element x to its parent then to its parent and so on until we reach the root of the tree now let's do it like this let's say if we want to recursively another recursively let's make it now so let's see while uh parent of x is not equal to x like

47:30 move to the parent like yeah this enough so we start from element and go to the parent until we reach the element whose parent equal to x and this element will be the root of the tree because only root have pointer to itself so we go to the root and then stop and return x cool how to make union do first okay again let's move to the representative of both elements so x equal to 5 of x and y equal to find of y now we move to

48:20 two root elements so we have x here and y here and now we need to combine two trees into one and the simplest way to do is just to make pointer from one root to another root so we'll just move this pointer from x to y from here this pointer we just move it to here that's all now if you start to find the root element from any element in this tree you follow these links and you go to

49:06 element x then use this link and go to element y so from each element in this set you will go to element y and from each element in this it will go to element y so y is the representative for all elements in this big tree in find we yes we have pointer to the node usually you you just have the array so all elements are just generated with integers from 1 to n something like that so you usually they just enumerated by integer small you can do this in pointer machine i believe yes i don't see any problems you can do it in pointer machines yes uh but

49:51 here i just i i just assume i have an array but i believe you can do the same in the pointer machine yes we don't need any special from arrays yes we we can we we can use just just the elements and pointers it's not balanced that's that's correct that's correct we'll get to it a little bit later uh by now by now in this implementation let's calculate time complexity uh first of all the time complexity of this union is composed of these two files so the the complexity of this is same as for find operation

50:36 and here you have like constant number here so so the union is pretty fast so the only thing we need to optimize is operation find the operation five may be slow but a little bit later but union makes some two fines and then constant number of operations let's go go to fight what is the time complexity of the fine ah it depends so we start from some element and use this link to move to the root is it possible that the number of these jumps will be linear no it actually can be it can be linear

51:22 so if you uh merge these two trees in the wrong order like like we did before so if you start from element one and merge it to element two then merge this three with element three and then merge these three of element four you will have this bamboo tree so you start from so this three becomes some one big path and in the end if you if you call fine from this node you will need to follow all these links up to the last element so in in the in the worst case this find may

52:07 work linear time that's not good we all this lecture we try to avoid this situation so uh how to avoid this this situation here so is it possible to make this fine work faster uh and quick answer is yes uh and that two different strategies how to improve the time complexity of this fine operation first the idea uh let's try to avoid situations like this so let's try to avoid these long paths and to avoid situations we need to kind of make the tree balanced how to make the tree balanced there are

52:53 different strategies simple explanation is what you what you usually need is again like like like in previous implementation you need to uh link the small tree to the big tree so if you have two trees of different size you need somehow to pick the small tree and connect it to the big tree uh i will use the rank heuristics but you can there are several different heuristics which works as well so i i will use the rank heuristics so what is the characteristics

53:38 i think let's maintain for each element its rank rank is basically uh the maximal possible distance to the leaf in this node so so for we have for each element x we find the longest path in this tree and the length of this path will be the rank of element x now for example here we have we have element two have rank equal to one these elements have around

54:25 zero please come around zero with number one and this element three have rank equal to for two right so here we have rank two here we have rank one here we have rank zero we have rank one run zero and so on so each element has the rank which is equal to the length like this is called the height of the tree so it's the maximal possible distance in this stream good and now what we will do we will try to connect three with small rank to three with the big b bigger one so here

55:14 uh let's say x will be the element of smaller so if rank of x is bigger than rank of y then we just swap them and then connect x to y and now we need to recalculate the ranks how to recalculate the ranks oh if you connect to trees if you have two drinks of different ranks so if rank of x is smaller than rank of y and you connect like here so you have some path here some path here

56:03 what will be the longer path in this uh big tree let's see so here this path this path will have length a rank of x plus 1 and this path will have length rank of y and if rank of x is less than length of y the integers so rank of x plus 1 will be less or equal let's write it here the rank of y so the maximal rank or the the the maximal length of this path will

56:49 be just rank of y mm-hmm yeah rank is the distance to the two to two to two to the first leaf sorry yeah that's correct we need to find the the maximal distance in this tree again again if you merge two trees of different ranks then a rank of x plus 1 will be less or equal than rank of y so the maximal possible distance will be still rank of y so this will be no greater than this

57:34 and if you merge two trees of the same rank then the maximal path will be a rank of x plus one so the the rank of the y will be increased by one if you have the same distances here then the maximal distance will be this so ranks will be increased by one yeah is the same with the height of the tree if you know what what is the height of the tree it's absolutely the same like like here here are the ranks of old nodes so if ranks are equal we need to increase rank of y by one

58:34 hmm uh that's the holoristic soul that's the whole trick that's all now i claim that uh these heuristics will cause this fine operation works in lobby from time so i claim if you do if you do it like this then the maximal distance you can travel here is logarithmic why is this true no let's see

59:30 let's see if you have element of rank r you have that you have some tree uh yeah i claim that the number of elements in this tree is at least two in the power of rank of x like here you have element of rank two it means that these three contain at least four elements so at least at least four elements for example this length y this three contains at least two elements it contains these two elements and so on

1:00:16 um optimal number of children no no you you want to have maximum michelle so it's it it's never bad to have many children because because if you have many children that means that the depth is smaller so you you always go up to the roots you never go down so the big number of children is no problem again let's go back uh what i want what i want to prove i want to prove that the rank is never more than logarithm of n that's what i want to prove

1:01:02 how to prove this uh very easily let's look on element x let's prove that number of elements in this tree is at least two in power of rank of x uh why is it true because by construction so what happened here when you combine two trees of different ranks then rank of y will be the same and the number of elements will be more than than before so we increase the number of elements and the rank is the same so this property is still satisfied and when you merge two element two two threes of the same rank then you have like no no less than two

1:01:48 in power of r elements here and no more than two elements of r here so total number of elements will be at least two in power r plus one so when you combine two trees of the same rank the total number of elements will be at least two and power of r plus one and you increase the length by one so if before this union you have two trees of size at least two in power of r then in the end you have big tree of rank r plus one and the total number of elements is at least two and power r plus one so the if the property satisfies before the new union it is satisfied after the union and in

1:02:34 the beginning of this structure we have all elements uh we have single elements of rank zero and element of running zero there yeah the size of this tree is one so it's two in power of zero it's satisfied so this property is satisfied in the beginning of that structure and it is satisfied after any union operation so this union operation do not break this property so in in each moment of of of life emphasis of the data structure for each element x the size of these three is at least two and power of rank of x and if it's not upper flat legs and this is no more than n it means that rank of x

1:03:20 is no more than logarithmic that's all in the next semester we'll talk about balance trees that's actually what happens usually in balance trees so when you have balanced trees you will have usually some proofs like this instead when you when you want to prove that something is up logarithm you make the inverse situation and prove that this part is up to exponential of this stuff like that okay so that was the first heuristics you just you just maintain the ranks of

1:04:06 all elements and uh link this three small rank two to the three of the big rank and if you do this you keep your three balanced so the ranks of all elements are up to logarithm so here when you make find you follow to the root and the length of this path will be no more than logarithm that's all that's the first basic heuristics how to maintain this tree balanced cool second heuristics is very very different what we can do we can improve this find function

1:05:03 so this technique is called path compressing uh what's basically mean imagine you have this find you you call this fine operation and it takes long time so you have some very long trips to the root so you call fine from here uh and you need to follow the all this route to the to the root element what you can do you can uh

1:05:50 improve your tree for future calls so when you call this find in the same element next time you already know that you will end up in this element so what you can do is you might change your pointer to the parent element to the root element so you might change this pointer to here so next time when you will call the fine from this node x you will go strictly to the root element so the next call will be working in constant time and also you may do the same for all elements in this root so for each element in this path you can change the pointer

1:06:36 from the current one to the root so you may change all pointers this already like this that's called path compressing so again what is it what is the difference every time you call the find you follow this route to the root element and when you go back you change all the pointers to the root element instead of the parent element that's all that's the whole idea so let's modify this fine

1:07:40 do you want to make it recursive on any cursive that's that's a matter of of taste accelerations that's let's make it on recursive just first i have to make it interesting so again we follow to the root now we have x to the root uh we need to remember ah so let's move to the root let's make y here so it's y equal to x while uh p of y not equal to y y equal to p of y so move to the root and then move again and change all pointers to the root

1:08:26 now let's do it like here while p of x not equal to x so i won't move here and change the pointer it says that equal to p of x uh p of x equal to y and then x equal to it's over complicated but okay good enough it's much easier when you when you write

1:09:13 it recursively when you write recursively you just call recursive function for the parent the recursive function will build everything here so in the end we just go back from the recursion and change your pointer to the root so it's like two to two lines of code but did this still work okay questions not for me okay that's all so what is the idea again what is the idea every time you call the find you

1:09:58 not only find the root node but you also change all the pointers on this path to the root node so next calls of the find will work in constant time so if you if you after the separation you you again call the find from any of these nodes you will go directly to this root node so each call each next call will will will cost you constant time that's the idea uh-huh okay now the results results

1:10:46 so what will happen if you use this technique if you use this technique without the rank heuristics if you use fat compression and without any other heuristics you just just use something like this and and connect any trees in any other so you may have this long bamboo trees but you always make five compression uh so this heuristics alone will give you logarithm timers uh for the final version so the amortized time of this find will be logan

1:11:35 and the more interesting fact is that if you use both heuristics so if you use spread compression and some other heuristics which maintain your tree balanced so if you if you use path compression on some balanced tree like we did or when we have like rancheristics so if you for example use path compression plus rancheristics ah the time will be even less than logarithmic so the amortized time of the find will be actually big o of inverse

1:12:22 document function of m and n so what is this these quite interesting faction so it's called an inverse ackermann function uh here you have two arguments so n is the size of the tree the number of elements in our sets if you maintain you may think about it in in terms of sets or in terms of trees and m is the number of iterations number

1:13:07 of fine of course of find this function of finds so if you call this find operation m times in total then time complexity will be something like that and the interesting about this function is that if you if n is increasing that function will be also increasing and if m is increasing so if you increase the number of calls uh this function is actually decreasing so it becomes smaller

1:13:57 that actually makes sense so if you have some structure of your tree and you make a lot of find operations then the more operations you make the shorter the paths became so after each fine operation the trees kind of improved so this length became shorter and shorter so if you make many fine operations the tree became something like that so all operations all future fine operations will cost you constant time that's interesting so so this time complexity actually depends on number operations you you make on in this data structure

1:14:43 if you make more operations uh they actually work faster than if you have small number of operations that's interesting uh we will not talk about this function today i may i i'm always planning to have a special lecture about this but i i never have enough time uh that's interesting so we may have like a special lecture about it at some point but uh the problem is you need to spend like an hour to exp to explain what the function means uh it's maybe not an hour but like 30 minutes just to explain what is the inverse sacrament function it's kind of complicated so instead of this we will prove some

1:15:29 uh some more simple uh upper bound on on this time complexity uh we will prove like the worst case for this situation uh in the worst case so in the worst case m equal to n so if m equal to n then this inverse accurate function became the iterated logarithm uh and we will prove this upper bound what is the iterated logarithm

1:16:18 uh the iteration logarithm is very simple function actually uh it's mostly how many times you need to get logarithm of of this integer until it became small so let's let's look on some integer 2 in power let's say 6 5 5 3 6. let's take logarithm for this element so so we take logarithm of this number you have 2 and a power of 16 then again you take logarithm of this number you have 2 you have 16 16 power of four then again you take logarithm from the

1:17:04 two in power of two then take logarithm to power four one twenty two power now let's calculate the number of times we take logarithm until we have small number for example here we start from this number take logarithm logarithm until we until we are here so we take logarithm like uh five times so its rated logarithm is the number of times you take logarithm of of the number until it becomes small enough no let's say here is small enough so let's say that iterated logarithm of n of of this number

1:17:55 is five sometimes it's plus my plus or minus one so it depends on where you want to end so if you end here then it's five if you want to make one more step then it will be six it's not not a big deal okay so this is the iterated logarithm function it is a very slow it grows very slowly so even for this big number it's it's up to five so it's it's it's extremely slow uh actually if you have these many elements in your data structure then you have much more interesting problems for example you don't know how to store

1:18:40 these elements because there is not enough atoms in the universe to store these elements so you most you usually don't have this many elements in your data structure that's what i want to say at least by now maybe physicists will learn something about how to store this number of elements in the future computers but in in normal computers by by now which you you don't you have no no chance to have this big data structure that's all now what i want to prove i want to prove that the time complexity

1:19:28 of find operation amortization complexity is a big o of iterated logarithm of energy that's what we'll approve right now ah that's not that fun it's the as this upper bound because this this is much more interesting but it's good enough so we will prove that the time complexity is pretty small cool so let's go how to prove this uh no to proof this we again this is the amortized cost so to prove the matter cost we need to

1:20:14 calculate the sum of time complexities of all find functions so we have this tree and we call the find operation several times so again you have situations like this so you start on from the structure and you call the union then you call find uh you another call another find union and so on so you make some number of operations like evaporations and i want to calculate the total time complexity of these operations

1:21:00 and then i'll i will divide by m and get the time complexion operation let's go so how to calculate the time complexity let's look what happens when you perform the fine operation so you have some element x you move from here to the root so the time complexity is uh equal to the number of these jumps so you start from element x and then move uh to the parent until you reach the root of the tree so uh the time complexity is formed by this by the length of this path so what we'll

1:21:46 calculate will calculate the total total length of all these paths okay first let's look on this last edge so this last edge is special let's calculate these edges first uh we have one last edge in each in in each fine operation so the total number of these last edges will be m so let's just calculate these last edges separately so so total time will be no more let's go

1:22:35 so in each fine operation we have one last no last edge so let's calculate it separately so this will be the last ones last edges nice now let's calculate this this edges uh to calculate this edges we will split all edges into two groups uh we will have like how to call them huh i don't know i don't know the correct terms in english it's interesting um let's call them small jumps in big jump

1:23:43 no i need i i i want to that's not not really even if if the terms are correct it's it's used only in this proof so as soon as the proof is correct it's fine okay let's look on some node x so you have this node x let's look on this edge from x to its parent so this is parent of x uh we will say we make small jump if the rank of the parent

1:24:29 is let's say less or equal than 1.9 in the power of rank of x and we say we have big jump let's say less if rank of the parent is greater or equal than ranks yeah good enough yeah that's fine so again we look on this edge from from

1:25:15 x to the parent of x in the tree and if rank of the parent is big enough we say that this is the big jump and if the rank of the parent is small we will say that this is small german that's all now let's calculate the number of why it's 1.9 yeah because i need some number less than two actually i need some number less less than two but quite close to two it's we'll get this right now we'll get to it in any minute uh first first let's calculate number of big jumps

1:26:02 i claim that number of big jumps in each fine operation is about uh iterated logarithm so we have m log iterated of n big jumps you know like this plus this why is it true no because you start from element x and each time you have a big jump you move from element uh to the element of rank something like that if if i if you have two here you will have exactly something like that so you start from

1:26:49 you start from element then run zero then when you have a big jump you go to element frank one then you have another big jump you go to element rank two and rank four to run 16 to rank 2 in power of 16 and so on so each big jump moves you from element rank x to rank at 2 power of x so you may make at at most iterated logarithms number of jumps i here i have not two but 1.9 but it's not a big deal if you make two big jumps so if you move from element x and you make one big

1:27:35 jump so you here you have two n power of x and you might make another big jump then if you two in power two or power of x ah one point nine uh sorry so move here it's one point nine in power of x and you move here you nine point nine in power nine one point nine power of x so this will be greater or equal than 2 and power of x so it's asymptotically the same if you make two big jumps you move to the vertex with a rank at least 2 in the power of x and you may have no more than iterated logarithms number of

1:28:22 jumps like this clear enough again again this is the same skill so it's red logarithmic number of times you you may make a logarithm you make logarithmic from the given number and here you make the opposite one you you go from number to the number 2 in power of x so if you go from right to left here you make start from here and each time you move to the integer which is 2 in the power of x so the number of jumps from here to here will be up to its rated logarithm of n is clear enough okay that so well it's it's actually it's in quite quite in intuitive so so

1:29:07 if you look on these big jumps uh that if you if you make a big jump it means that you go from number from some very big number so you move from number x to some number two and power of x and you can't make too many of jumps like this even after like five operations you go to the number which is extremely big okay so number of big jumps is at most iterated logarithm for each find operation so total number will be something like that that's all and finally let's calculate number of small jumps to calculate number of small jumps let's look on some some some integer some note x

1:29:56 yeah is it this big it's big enough to to to to make this proof let's talk about small jumps let's look on the number x no number x like this one element x so let's look on the edge from the x to its parent imagine we let's say let's say x is not here x isn't somewhere here so we start find from here go to element x then use this edge and go up to the root every time if the x is not the final edge and we already calculated this final edges so if this edge is not the final

1:30:43 edge then it means that we will change this pointer to the pointer to the root so we if we go from here then we will use path compression and we will change this pointer to here it means that the pointer is moved to some element with bigger rank so the rank of the root is strictly bigger than the rank of the point of of the parent of element x this is the root

1:31:31 again before we make this find uh the pointer from x was to to this element the parent of x and when we make this fine we move this pointer from this element to the root the root have bigger rank than this element because ranks are strictly increasing each parent have bigger rank than than the children yes yes this edge will become the last edge but not for this it will became the last edge but then we can like make a union so this all this tree will

1:32:16 be connected to something else so this edges will not will no longer be the last edge and so on so last edge is not final so since if the edge is final that we can then unite this set with some another set so we connect this root some some other roots so these edges will not be final anymore so it's not like the final point zone if if the age is final it's not final until the end of the day structure it's just final by now oh what was it if this edge is not the last edge on this path it means that we will reconnect this x from here to here and this node

1:33:05 have bigger rank than this node let's now let's look on this on this uh value let's look on this value i claim it each time you move across this node x this value will be increasing so each time if if this x is on your path from from this find operation this value will be increasing each time increasing okay it's increasing because we move

1:33:51 this pointer from here to here and this element have bigger than this element so so this parent was here and now it's here so this element have bigger end so this value is increasing now how many times can we increase this value until this x became the big jump so let's take element x okay let's make it slow again what happens you have element x you have some pointers here you have some fine operations which access element x so you have some find operation from here

1:34:38 each time when this fine operation access the node x you will move the pointer from parent to some another note so if you go here then you move the pointer here next time if you go here you will move pointer even even further so each time you access node x you move this pointer uh up to up to two to the root of the tree so let's calculate the number of such operations after this jump from x to its parent will become the big jump for x we need to make

1:35:27 at most 1.9 in power rank of x operations until until until the jump from x to parent of x became so what i want to say

1:36:13 each time you go through this element x you move this pointer up up to three so uh when you make 1.9 in the power of rank of x operations like this uh the rank of this parent node will be bigger than one point nine in the far right because rank is always increasing you always move pointer to some uh node with bigger rank so after this number of operations this jump from x to its parent will became a big jump because rent of x is constant and rank of its parent is always

1:36:58 increasing that's all now let's calculate the total number of suppression like this i want to calculate the sum for all for all nodes uh 1.9 in the power of rank of x so this will be the total numbers of operations which access all elements yeah so for for each element x we go through this element at least at most this number of times so now let's calculate the sum of all these values uh how to create this sound no it's actually quite easy we will group all all nodes by the rank so let's say we

1:37:46 group all nodes by rank multiply by 1.9 so let's group all nodes by the rank and calculate the sum for all nodes of the same rank and what we'll have here how many nodes may have the rank are so imagine you have the tree you have several nodes of the same red if you have several nodes of the same red then for each subtree you have at least two in the power of r uh nodes

1:38:36 and in total you have n nodes so the number of these elements is no more than n divided by 2 power of r yes it's it's it it's little bit complicated to get from the first time you you may need to watch it again something later maybe it's not maybe it's not the best explanation for this but i think it's quite clear but it's it's no no no not the easiest stuff okay let's go back here finally that that's the finish what we have here i want to calculate

1:39:23 the total number of small jumps yep let's look on some node x we make some small jumps from this vertex x from vertex x we'll have up to this number of jumps until this jump became a big jump so the total number of small jumps will be something like that now we calculate this sum by regrouping all the summons into in in the groups of the same of of the of of nodes of the same remedy so we take all the notes of rank r calculate the number of notes of what this is the number of num pair of notes uh

1:40:09 equal to r so we take all nodes of the same red get the number of nodes multiplied by this this value that's all let's just just regrouping of this m of elements of this sum uh and this one and the number of elements of which have rather than r is up to n divided by the sum and divided between the power of r multiplied by 1.9 per r this will be n multiplied by this sum

1:41:01 and that's all and this sum is constant so this is big o of n so here we have last edges big no big jumps and plus and small jumps so the total number of uh operations in all these finds will be m log n plus n and we will assume that m is bigger than n because it's uh

1:41:46 so the total time will be up to peak maybe not maybe not the clearest explanation but okay that's the first time explaining english that's all that that that that's why this that structure works and it's right logarithm and the the interesting part why why is it important because this this function is ex grows extremely slow and also all that all the operations we used are pretty are pretty fast so if

1:42:32 you look on the code then all operations in this course are fast we just go we just look in the array go to the link go to link and so on so we use very simple operations and time complexity is slow so the the the this implementation is actually very fast just it's one of the fastest data structure uh when you may use and it's it's it's actually almost the constant working time so like in average you have like three operations in this literature so it's it's it's quite cool it's really it's really useful you can use this in in in in you can use this in in really context in real context and so on so

1:43:20 uh later we will use some maybe we'll discuss it yeah we'll discuss next week in the this in the home task it can be improved not only to to maintain the sets but also to calculate some functions in these sets and we will discuss it in the home task i believe so it it can be modified to be able to calculate some different functions on the paths in the trees so it's very important so that's i believe it's all for today so thank you again for joining me see you next time

1:44:06 [Music] so [Music]

1:45:00 so [Music]

1:45:56 my [Music]

1:47:07 you [Music] you