1093:
1082:
579:, where each node that is not the root of a tree points to its parent. To distinguish root nodes from others, their parent pointers have invalid values, such as a circular reference to the node or a sentinel value. Each tree represents a set stored in the forest, with the members of the set being the nodes in the tree. Root nodes provide set representatives: Two nodes are in the same set if and only if the roots of the trees containing the nodes are equal.
4031:
563:. "Semi-persistent" means that previous versions of the structure are efficiently retained, but accessing previous versions of the data structure invalidates later ones. Their fastest implementation achieves performance almost as efficient as the non-persistent algorithm. They do not perform a complexity analysis.
2123:
operation is applied. In this case, a tree with smaller rank will be attached to a tree with greater rank, rather than vice versa. And during the find operation, all nodes visited along the path will be attached to the root, which has larger rank than its children, so this operation won't change this
847:
This implementation makes two passes, one up the tree and one back down. It requires enough scratch memory to store the path from the query node to the root (in the above pseudocode, the path is implicitly represented using the call stack). This can be decreased to a constant amount of memory by
771:
is executed, there is no faster way to reach the root than by following each parent pointer in succession. However, the parent pointers visited during this search can be updated to point closer to the root. Because every element visited on the way to a root is part of the same set, this does not
1457:
do not change. If the ranks are the same, then either one can become the parent, but the new parent's rank is incremented by one. While the rank of a node is clearly related to its height, storing ranks is more efficient than storing heights. The height of a node can change during a
3036:
308:
of a graph. The importance of minimum spanning trees means that disjoint-set data structures underlie a wide variety of algorithms. In addition, disjoint-set data structures also have applications to symbolic computation, as well as in compilers, especially for
2435:
We create some buckets and put vertices into the buckets according to their ranks inductively. That is, vertices with rank 0 go into the zeroth bucket, vertices with rank 1 go into the first bucket, vertices with ranks 2 and 3 go into the second bucket. If the
566:
Variants of disjoint-set data structures with better performance on a restricted class of problems have also been considered. Gabow and Tarjan showed that if the possible unions are restricted in certain ways, then a truly linear time algorithm is possible.
1295:
are merged, the node with more descendants becomes the parent. If the two nodes have the same number of descendants, then either one can become the parent. In both cases, the size of the new parent node is set to its new total number of descendants.
2118:
claim that as Find and Union operations are applied to the data set, this fact remains true over time. Initially when each node is the root of its own tree, it's trivially true. The only case when the rank of a node might be changed is when the
3180:
3136:
953:
algorithms that retain the same worst-case complexity but are more efficient in practice. These are called path splitting and path halving. Both of these update the parent pointers of nodes on the path between the query node and the root.
4050:. This model can then be used to determine whether two vertices belong to the same component, or whether adding an edge between them would result in a cycle. The Union–Find algorithm is used in high-performance implementations of
3946:
time per operation, and thus in comparison with Galler and
Fischer's structure it has a better worst-case time per operation, but inferior amortized time. In 1999, Alstrup et al. gave a structure that has optimal worst-case time
582:
Nodes in the forest can be stored in any way convenient to the application, but a common technique is to store them in an array. In this case, parents can be indicated by their array index. Every array entry requires
458:) upper bound on the algorithm's time complexity,. He also proved it to be tight. In 1979, he showed that this was the lower bound for a certain class of algorithms, that include the Galler-Fischer structure. In 1989,
3668:
1279:. Both of these require a node to store information besides just its parent pointer. This information is used to decide which root becomes the new parent. Both strategies ensure that trees do not become too deep.
776:
operations faster, not only for the nodes between the query node and the root, but also for their descendants. This updating is an important part of the disjoint-set forest's amortized performance guarantee.
1822:
2888:
4496:
Harold N. Gabow, Robert Endre Tarjan, "A linear-time algorithm for a special case of disjoint set union," Journal of
Computer and System Sciences, Volume 30, Issue 2, 1985, pp. 209–221, ISSN 0022-0000,
1159:
The choice of which node becomes the parent has consequences for the complexity of future operations on the tree. If it is done carelessly, trees can become excessively tall. For example, suppose that
3092:
1665:
It is clear from the above implementations that the size and rank of a node do not matter unless a node is the root of a tree. Once a node becomes a child, its size and rank are never accessed again.
2568:
627:
operation adds a new element into a new set containing only the new element, and the new set is added to the data structure. If the data structure is instead viewed as a partition of a set, then the
638:
initializes the node's parent pointer and the node's size or rank. If a root is represented by a node that points to itself, then adding an element can be described using the following pseudocode:
3763:
3558:
615:
Disjoint-set data structures support three operations: Making a new set containing a new element; Finding the representative of the set containing a given element; and
Merging two sets.
3140:
3096:
3393:
4014:
will not improve as a result of the decrease in the number of elements. However, there exist modern implementations that allow for constant-time deletion and where the time-bound for
1634:
4000:
3944:
2261:
3248:
1935:
3468:
2832:
2427:
2306:
2254:
2015:
1977:
848:
performing both passes in the same direction. The constant memory implementation walks from the query node to the root twice, once to find the root and once to update pointers:
502:
2066:
The precise analysis of the performance of a disjoint-set forest is somewhat intricate. However, there is a much simpler analysis that proves that the amortized time for any
1867:
1217:
591:
bits of storage for the parent pointer. A comparable or lesser amount of storage is required for the rest of the entry, so the number of bits required to store the forest is
3822:
375:
452:
2611:
631:
operation enlarges the set by adding the new element, and it extends the existing partition by putting the new element into a new subset containing only the new element.
2044:
3857:
537:
2563:
2511:
233:), and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or different sets.
3889:
2883:
2793:
2740:
2677:
2386:
2351:
2161:
3399:
in different find operations. Because of path compression and not accounting for the edge to a root, this sequence contains only different nodes and because of
575:
Each node in a disjoint-set forest consists of a pointer and some auxiliary information, either a size or a rank (but not both). The pointers are used to make
399:
285:. Disjoint-set forests do not guarantee this performance on a per-operation basis. Individual union and find operations can take longer than a constant times
603:. If an implementation uses fixed size nodes (thereby limiting the maximum size of the forest that can be stored), then the necessary storage is linear in
1140:. If the roots are the same, there is nothing more to do. Otherwise, the two trees must be merged. This is done by either setting the parent pointer of
236:
While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation called a
1287:
In the case of union by size, a node stores its size, which is simply its number of descendants (including the node itself). When the trees with roots
3403:
we know that the ranks of the nodes in this sequence are strictly increasing. By both of the nodes being in the bucket we can conclude that the length
3859:
and this bound is tight). In 1985, N. Blum gave an implementation of the operations that does not use path compression, but compresses trees during
788:, makes every node between the query node and the root point to the root. Path compression can be implemented using a simple recursion as follows:
293:
time, but each operation causes the disjoint-set forest to adjust itself so that successive operations are faster. Disjoint-set forests are both
4832:
3052:
3573:
5197:
17:
4010:
The regular implementation as disjoint-set forests does not react favorably to the deletion of elements, in the sense that the time for
3031:{\displaystyle {\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.}
4873:
1743:
4676:
Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). "Worst-case and amortised optimality in union-find (Extended abstract)".
4092:, a different data structure for maintaining disjoint sets, with updates that split sets apart rather than merging them together
2058:
that can actually be written in the physical universe. This makes disjoint-set operations practically amortized constant time.
4717:
Alstrup, Stephen; Thorup, Mikkel; Gørtz, Inge Li; Rauhe, Theis; Zwick, Uri (2014). "Union-Find with
Constant Time Deletions".
5167:
4541:
1441:, which is an upper bound for its height. When a node is initialized, its rank is set to zero. To merge trees with roots
3675:
1449:, first compare their ranks. If the ranks are different, then the larger rank tree becomes the parent, and the ranks of
1884:
The combination of path compression, splitting, or halving, with union by size or by rank, reduces the running time for
549:
In 1994, Richard J. Anderson and
Heather Woll described a parallelized version of Union–Find that never needs to block.
5236:
4043:
3475:
5106:
1462:
operation, so storing ranks avoids the extra effort of keeping the height correct. In pseudocode, union by rank is:
4896:
4901:
4693:
4375:
4051:
3339:
543:
disjoint-set data structure per operation, thereby proving the optimality of the data structure in this model.
4823:
4661:
Blum, Norbert (1985). "On the Single-Operation Worst-Case Time
Complexity of the Disjoint Set Union Problem".
4866:
4077:
2630:
Proof: When we go from one bucket to the next, we add one more two to the power, that is, the next bucket to
4975:
1607:
3950:
3894:
463:
3191:
2432:
For convenience, we define "bucket" here: a bucket is a set that contains vertices with particular ranks.
1899:
4963:
3418:
2798:
2395:
2274:
2200:
1982:
1944:
469:
4846:
5231:
5179:
4946:
4941:
4531:
4480:
Conchon, Sylvain; Filliâtre, Jean-Christophe (October 2007). "A Persistent Union-Find Data
Structure".
282:
1834:
1175:
4936:
4186:
3792:
691:
This operation has constant time complexity. In particular, initializing a disjoint-set forest with
553:
332:
4780:
416:
4970:
4929:
4859:
3325:
is not the root (at the time of this traversing, otherwise the traversal would be accounted for in
3175:{\displaystyle T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}}
3131:{\displaystyle T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}}
2574:
4430:
Galil, Z.; Italiano, G. (1991). "Data structures and algorithms for disjoint set union problems".
4062:
3411:
is attached to a different root in the same bucket) is at most the number of ranks in the buckets
5210:
5187:
38:
2020:
1425:
The number of bits necessary to store the size is clearly the number of bits necessary to store
5192:
4992:
4752:
Ben-Amram, Amir M.; Yoffe, Simon (2011). "A simple and efficient Union-Find-Delete algorithm".
4066:
3827:
2047:
507:
455:
301:
294:
2170:
Initially when each node is the root of its own tree, it's trivially true. Assume that a node
5118:
5073:
5035:
4827:
4070:
784:
that achieve the asymptotically optimal time complexity. One family of algorithms, known as
720:. As long as memory allocation is an amortized constant-time operation, as it is for a good
305:
241:
4559:, Micha Sharir. "Top-down analysis of path compression", SIAM J. Comput. 34(3):515–525, 2005
2516:
2443:
5058:
4519:
4095:
4089:
3862:
2839:
2749:
2682:
2633:
2364:
2329:
2139:
1979:. This is asymptotically optimal, meaning that every disjoint set data structure must use
556:
version of the disjoint-set forest data structure and formalized its correctness using the
709:
Lack of a parent assigned to the node implies that the node is not present in the forest.
8:
4058:
576:
310:
724:
implementation, it does not change the asymptotic performance of the random-set forest.
5101:
5086:
4951:
4911:
4803:
4734:
4699:
4651:. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.
4600:
4447:
4381:
4293:
4205:
4177:
4155:
4039:
2101:
1938:
384:
378:
326:
245:
230:
222:
63:
4358:
Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89
1662:
bits. This makes the ranks an asymptotically negligible portion of the forest's size.
5020:
4919:
4689:
4537:
4451:
4371:
4335:
4318:
4173:
759:
operation presents an important opportunity for improving the forest. The time in a
546:
In 1991, Galil and
Italiano published a survey of data structures for disjoint-sets.
322:
229:. It provides operations for adding new sets, merging sets (replacing them by their
218:
59:
4807:
4738:
4604:
4385:
4159:
3252:
Since each find operation makes exactly one traversal that leads to a root, we have
5043:
4795:
4761:
4726:
4681:
4644:
4627:
4590:
4582:
4523:
4515:
4439:
4361:
4330:
4314:
4297:
4283:
4263:
4240:
4209:
4195:
4145:
4137:
4125:
4047:
4034:
A demo for Union-Find when using
Kruskal's algorithm to find minimum spanning tree.
958:
replaces every parent pointer on that path by a pointer to the node's grandparent:
942:
194:
152:
4841:
4703:
2111:
follows the path along to the root, the rank of node it encounters is increasing.
2050:. The inverse Ackermann function grows extraordinarily slowly, so this factor is
5063:
5005:
4648:
4353:
4267:
946:
557:
459:
74:
740:
until it reaches a root element. This root element represents the set to which
5155:
5133:
4958:
4882:
4570:
4556:
4527:
4498:
4356:; Saks, M. (May 1989). "The cell probe complexity of dynamic data structures".
4319:"A class of algorithms which require non-linear time to maintain disjoint sets"
4228:
2567:
560:
406:
258:
210:
78:
4765:
763:
operation is spent chasing parent pointers, so a flatter tree leads to faster
5225:
5128:
5025:
5010:
4224:
721:
410:
402:
214:
4678:
Proceedings of the thirty-first annual ACM symposium on Theory of
Computing
736:
operation follows the chain of parent pointers from a specified query node
4685:
4586:
4443:
4200:
4181:
4141:
3663:{\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}
1092:
5123:
5048:
1253:
passes through every node in the tree. For this forest, the time to run
1081:
4799:
4366:
552:
In 2007, Sylvain Conchon and Jean-Christophe Filliâtre developed a semi-
5111:
5015:
4030:
2513:
then the (B+1)st bucket will contain vertices with ranks from interval
2260:
5053:
5000:
4595:
4150:
2061:
1714:
If an implementation uses path compression alone, then a sequence of
1681:
does not attempt to control tree heights, can have trees with height
4730:
4631:
4481:
4288:
4271:
4244:
1172:. Begin with a forest that has just been initialized with elements
5150:
5096:
4924:
4128:(1975). "Efficiency of a Good But Not Linear Set Union Algorithm".
4851:
252:
addition, union, or find operations on a disjoint-set forest with
5145:
5091:
4618:
Hopcroft, J. E.; Ullman, J. D. (1973). "Set Merging Algorithms".
1827:
Using union by rank, but without updating parent pointers during
1429:. This adds a constant factor to the forest's required storage.
1271:
In an efficient implementation, tree height is controlled using
5140:
5081:
1817:{\displaystyle \Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))}
716:
must be preceded by an operation that allocates memory to hold
226:
4469:. 23rd ACM Symposium on Theory of Computing. pp. 370–380.
1019:
works similarly but replaces only every other parent pointer:
3273:
Also, from the bound above on the number of buckets, we have
1245:. The resulting forest contains a single tree whose root is
5162:
3169:(number of links traversed where the buckets are the same).
3125:(number of links traversed where the buckets are different)
3047:
represent the list of "find" operations performed, and let
772:
change the sets stored in the forest. But it makes future
4514:
4065:
functionality. It is also a key component in implementing
3087:{\displaystyle T_{1}=\sum _{F}{\text{(link to the root)}}}
4571:"Efficiency of a Good But Not Linear Set Union Algorithm"
4530:(2009). "Chapter 21: Data structures for Disjoint Sets".
4467:
Wait-free Parallel Algorithms for the Union-Find Problem
4836:
4716:
3772:
2353:
nodes. We will get the maximum number of nodes of rank
329:
in 1964. In 1973, their time complexity was bounded to
3576:
2440:-th bucket contains vertices with ranks from interval
4675:
4394:) implementation of the set union problem requires Ω(
3953:
3897:
3865:
3830:
3795:
3678:
3478:
3421:
3342:
3194:
3143:
3099:
3055:
2891:
2842:
2801:
2752:
2685:
2636:
2577:
2519:
2446:
2398:
2367:
2332:
2277:
2203:
2142:
2023:
1985:
1947:
1902:
1837:
1746:
1610:
1178:
510:
472:
419:
387:
335:
4663:
2nd Symp. On Theoretical Aspects of Computer Science
3758:{\displaystyle T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).}
3994:
3938:
3883:
3851:
3816:
3757:
3662:
3552:
3462:
3387:
3242:
3174:
3130:
3086:
3030:
2877:
2826:
2787:
2734:
2671:
2605:
2557:
2505:
2421:
2380:
2345:
2300:
2248:
2155:
2062:Proof of O(m log* n) time complexity of Union-Find
2038:
2017:amortized time per operation. Here, the function
2009:
1971:
1929:
1861:
1816:
1636:or less. Consequently each rank can be stored in
1628:
1211:
531:
496:
446:
393:
369:
4262:
3553:{\displaystyle T_{3}\leq \sum _{}\sum _{u}2^{B}.}
2388:nodes. In this case, the number of nodes of rank
244:which performs unions and finds in near-constant
5223:
4479:
4002:together with inverse-Ackermann amortized time.
2836:Proof: The maximum number of elements in bucket
2617:We can make two observations about the buckets.
1522:// If necessary, rename variables to ensure that
300:Disjoint-set data structures play a key role in
4536:(Third ed.). MIT Press. pp. 571–572.
2077:operations on a disjoint-set forest containing
1132:to determine the roots of the trees containing
27:Data structure for storing non-overlapping sets
4751:
4617:
4223:
1677:does not update parent pointers, and in which
1673:A disjoint-set forest implementation in which
1356:// If necessary, swap variables to ensure that
727:
4867:
4510:
4508:
4506:
4429:
4348:
4346:
4272:"Worst-case analysis of set union algorithms"
4214:. The paper originating disjoint-set forests.
4172:
2267:Lemma 3: The maximum number of nodes of rank
1740:operations, has a worst-case running time of
321:Disjoint-set forests were first described by
4499:https://doi.org/10.1016/0022-0000(85)90014-5
4465:Anderson, Richard J.; Woll, Heather (1994).
4464:
4309:
4307:
4258:
4256:
4254:
4120:
4118:
4116:
4114:
4112:
4110:
1623:
1611:
1525:// x has rank at least as large as that of y
4458:
4352:
4217:
2315:
4874:
4860:
4772:
4503:
4473:
4343:
3407:of the sequence (the number of times node
3400:
1359:// x has at least as many descendants as y
4781:"Unification: A multidisciplinary survey"
4594:
4365:
4334:
4304:
4287:
4251:
4199:
4166:
4149:
4107:
3388:{\displaystyle v_{1},v_{2},\ldots ,v_{k}}
3305:, suppose we are traversing an edge from
2746:The maximum number of elements in bucket
2187:
2120:
2108:
1604:It can be shown that every node has rank
4423:
4029:
2566:
2197:results, the root of which has at least
1647:bits and all the ranks can be stored in
1572:// If necessary, increment the rank of x
1091:
1080:
4323:Journal of Computer and System Sciences
4038:Disjoint-set data structures model the
2621:The total number of buckets is at most
2361:is the root of a tree that has exactly
14:
5224:
4778:
4568:
4313:
4124:
1629:{\displaystyle \lfloor \log n\rfloor }
1516:// x and y are already in the same set
1350:// x and y are already in the same set
4855:
3995:{\displaystyle O(\log n/\log \log n)}
3939:{\displaystyle O(\log n/\log \log n)}
2322:which is root of a subtree with rank
2182:nodes. Then when two trees with rank
2132:which is root of a subtree with rank
1437:For union by rank, a node stores its
1148:'s, or setting the parent pointer of
752:returns the root element it reaches.
4660:
4080:uses a Union-Find in the algorithm.
3773:Better worst-case time per operation
3567:
3243:{\displaystyle T=T_{1}+T_{2}+T_{3}.}
1930:{\displaystyle \Theta (m\alpha (n))}
4881:
4182:"An improved equivalence algorithm"
4057:This data structure is used by the
4042:, for example to keep track of the
3767:
3463:{\displaystyle 2^{B}-1-B<2^{B}.}
2827:{\displaystyle {\frac {2n}{2^{B}}}}
2422:{\displaystyle {\frac {n}{2^{r}}}.}
2301:{\displaystyle {\frac {n}{2^{r}}}.}
2249:{\displaystyle 2^{r}+2^{r}=2^{r+1}}
2010:{\displaystyle \Omega (\alpha (n))}
1972:{\displaystyle \Theta (\alpha (n))}
1076:
497:{\displaystyle \Omega (\alpha (n))}
24:
4231:(1973). "Set Merging Algorithms".
3796:
2259:
1986:
1948:
1903:
1838:
1747:
1668:
618:
473:
25:
5248:
4817:
4414:−1 Union's, beginning with
1168:a subtree of the tree containing
1100:, some sets are grouped together.
780:There are several algorithms for
570:
240:. This is a specialized type of
4063:Incremental Connected Components
3563:
1862:{\displaystyle \Theta (m\log n)}
1432:
1282:
1212:{\displaystyle 1,2,3,\ldots ,n,}
1164:always made the tree containing
4745:
4710:
4669:
4654:
4638:
4611:
4562:
4550:
4490:
4025:
3817:{\displaystyle \Theta (\log n)}
2186:are merged using the operation
370:{\displaystyle O(\log ^{*}(n))}
4719:ACM Transactions on Algorithms
3989:
3957:
3933:
3901:
3846:
3834:
3811:
3799:
3749:
3727:
3522:
3497:
2600:
2581:
2500:
2482:
2033:
2027:
2004:
2001:
1995:
1989:
1966:
1963:
1957:
1951:
1924:
1921:
1915:
1906:
1888:operations of any type, up to
1873:operations of any type, up to
1856:
1841:
1811:
1750:
1721:operations, followed by up to
526:
514:
491:
488:
482:
476:
447:{\displaystyle O(m\alpha (n))}
441:
438:
432:
423:
364:
361:
355:
339:
281:is the extremely slow-growing
33:Disjoint-set/Union-find Forest
13:
1:
4569:Tarjan, Robert Endre (1975).
4101:
3891:. His implementation runs in
3321:have rank in the bucket and
2606:{\displaystyle O(\log ^{*}n)}
658:is not already in the forest
610:
221:. Equivalently, it stores a
4754:Theoretical Computer Science
4336:10.1016/0022-0000(79)90042-4
1692:. In such a situation, the
1116:replaces the set containing
248:. To perform a sequence of
213:that stores a collection of
7:
5198:Directed acyclic word graph
4964:Double-ended priority queue
4083:
4005:
3777:The worst-case time of the
728:Finding set representatives
413:was the first to prove the
297:and practically efficient.
199:disjoint-set data structure
18:Disjoint set data structure
10:
5253:
4533:Introduction to Algorithms
4483:ACM SIGPLAN Workshop on ML
4390:Theorem 5: Any CPROBE(log
3336:and consider the sequence
2048:inverse Ackermann function
2039:{\displaystyle \alpha (n)}
1831:, gives a running time of
634:In a disjoint-set forest,
456:inverse Ackermann function
316:
283:inverse Ackermann function
256:nodes requires total time
5237:Amortized data structures
5206:
5178:
5072:
5034:
4991:
4910:
4889:
4842:Javascript implementation
4766:10.1016/j.tcs.2010.11.005
4620:SIAM Journal on Computing
4233:SIAM Journal on Computing
4187:Communications of the ACM
4078:Hoshen-Kopelman algorithm
3852:{\displaystyle O(\log n)}
2357:when each node with rank
1481:// Replace nodes by roots
1315:// Replace nodes by roots
1249:, and the path from 1 to
1096:After some operations of
539:bits must be accessed by
532:{\displaystyle O(\log n)}
203:union–find data structure
158:
151:
130:
99:
84:
73:
69:
55:
47:
37:
32:
4930:Retrieval Data Structure
3781:operation in trees with
949:also developed one-pass
5211:List of data structures
5188:Binary decision diagram
3570:, we can conclude that
3184:Then the total cost of
1406:// Update the size of x
1120:and the set containing
1053:.parent.parent
5193:Directed acyclic graph
4779:Knight, Kevin (1989).
4035:
3996:
3940:
3885:
3853:
3818:
3759:
3664:
3554:
3464:
3395:that take the role of
3389:
3244:
3176:
3132:
3088:
3032:
2879:
2828:
2789:
2736:
2673:
2614:
2607:
2559:
2558:{\displaystyle \left.}
2507:
2506:{\displaystyle \left=}
2423:
2382:
2347:
2318:, we know that a node
2302:
2264:
2250:
2157:
2040:
2011:
1973:
1939:amortized running time
1931:
1863:
1818:
1630:
1562:// Make x the new root
1396:// Make x the new root
1213:
1101:
1089:
681:// if nodes store rank
674:// if nodes store size
533:
498:
448:
395:
371:
295:asymptotically optimal
4847:Python implementation
4788:ACM Computing Surveys
4686:10.1145/301250.301383
4587:10.1145/321879.321884
4520:Leiserson, Charles E.
4444:10.1145/116873.116878
4432:ACM Computing Surveys
4201:10.1145/364099.364331
4142:10.1145/321879.321884
4071:minimum spanning tree
4040:partitioning of a set
4033:
3997:
3941:
3886:
3884:{\displaystyle union}
3854:
3819:
3760:
3665:
3555:
3465:
3390:
3245:
3177:
3133:
3089:
3033:
2880:
2878:{\displaystyle \left}
2829:
2790:
2788:{\displaystyle \left}
2737:
2735:{\displaystyle \left}
2674:
2672:{\displaystyle \left}
2608:
2570:
2560:
2508:
2424:
2383:
2381:{\displaystyle 2^{r}}
2348:
2346:{\displaystyle 2^{r}}
2303:
2263:
2251:
2158:
2156:{\displaystyle 2^{r}}
2041:
2012:
1974:
1932:
1864:
1819:
1631:
1214:
1095:
1088:creates 8 singletons.
1084:
818:.parent := Find(
534:
504:(amortized) words of
499:
449:
396:
372:
306:minimum spanning tree
5059:Unrolled linked list
4680:. pp. 499–506.
4486:. Freiburg, Germany.
4360:. pp. 345–354.
4315:Tarjan, Robert Endre
4126:Tarjan, Robert Endre
4096:Dynamic connectivity
4090:Partition refinement
4044:connected components
3951:
3895:
3863:
3828:
3793:
3676:
3574:
3476:
3419:
3340:
3192:
3141:
3097:
3053:
2889:
2840:
2799:
2750:
2683:
2634:
2575:
2517:
2444:
2396:
2365:
2330:
2275:
2201:
2140:
2021:
1983:
1945:
1900:
1835:
1744:
1608:
1176:
1001:.parent.parent)
767:operations. When a
679:.rank := 0
672:.size := 1
577:parent pointer trees
508:
470:
417:
385:
333:
5107:Self-balancing tree
4833:Java implementation
4828:Boost C++ libraries
4800:10.1145/62029.62030
4406:)) time to execute
4367:10.1145/73007.73040
4178:Fischer, Michael J.
4067:Kruskal's algorithm
4059:Boost Graph Library
4022:number of elements
3415:, that is, at most
2190:, a tree with rank
1700:operations require
1124:with their union.
744:belongs and may be
311:register allocation
302:Kruskal's algorithm
238:disjoint-set forest
5087:Binary search tree
4952:Double-ended queue
4824:C++ implementation
4575:Journal of the ACM
4276:Journal of the ACM
4174:Galler, Bernard A.
4130:Journal of the ACM
4036:
3992:
3936:
3881:
3849:
3814:
3755:
3660:
3599:
3562:From Observations
3550:
3536:
3526:
3460:
3385:
3240:
3172:
3166:
3128:
3122:
3084:
3081:(link to the root)
3078:
3028:
2875:
2824:
2785:
2732:
2669:
2615:
2603:
2555:
2503:
2419:
2378:
2343:
2312:
2298:
2265:
2246:
2168:
2153:
2116:
2102:iterated logarithm
2036:
2007:
1969:
1941:of each operation
1937:. This makes the
1927:
1859:
1814:
1626:
1209:
1102:
1090:
993:.parent) := (
529:
494:
444:
391:
379:iterated logarithm
367:
327:Michael J. Fischer
223:partition of a set
217:(non-overlapping)
64:Michael J. Fischer
5232:Search algorithms
5219:
5218:
5021:Hashed array tree
4920:Associative array
4543:978-0-262-03384-8
4524:Rivest, Ronald L.
4516:Cormen, Thomas H.
4264:Tarjan, Robert E.
4061:to implement its
3630:
3590:
3527:
3492:
3170:
3157:
3126:
3113:
3082:
3069:
3023:
2998:
2959:
2933:
2907:
2822:
2414:
2310:
2293:
2166:
2114:
822:.parent)
394:{\displaystyle n}
323:Bernard A. Galler
191:
190:
187:
186:
60:Bernard A. Galler
16:(Redirected from
5244:
5044:Association list
4876:
4869:
4862:
4853:
4852:
4812:
4811:
4785:
4776:
4770:
4769:
4760:(4–5): 487–492.
4749:
4743:
4742:
4714:
4708:
4707:
4673:
4667:
4666:
4658:
4652:
4645:Robert E. Tarjan
4642:
4636:
4635:
4615:
4609:
4608:
4598:
4566:
4560:
4554:
4548:
4547:
4512:
4501:
4494:
4488:
4487:
4477:
4471:
4470:
4462:
4456:
4455:
4427:
4421:
4420:
4369:
4350:
4341:
4340:
4338:
4311:
4302:
4301:
4291:
4268:van Leeuwen, Jan
4260:
4249:
4248:
4221:
4215:
4213:
4203:
4170:
4164:
4163:
4153:
4122:
4048:undirected graph
4017:
4013:
4001:
3999:
3998:
3993:
3973:
3945:
3943:
3942:
3937:
3917:
3890:
3888:
3887:
3882:
3858:
3856:
3855:
3850:
3823:
3821:
3820:
3815:
3780:
3768:Other structures
3764:
3762:
3761:
3756:
3742:
3741:
3720:
3719:
3707:
3706:
3694:
3693:
3669:
3667:
3666:
3661:
3650:
3649:
3631:
3629:
3628:
3619:
3611:
3609:
3608:
3598:
3586:
3585:
3559:
3557:
3556:
3551:
3546:
3545:
3535:
3525:
3515:
3514:
3488:
3487:
3469:
3467:
3466:
3461:
3456:
3455:
3431:
3430:
3414:
3410:
3406:
3398:
3394:
3392:
3391:
3386:
3384:
3383:
3365:
3364:
3352:
3351:
3335:
3331:
3324:
3320:
3316:
3312:
3308:
3304:
3294:
3269:
3249:
3247:
3246:
3241:
3236:
3235:
3223:
3222:
3210:
3209:
3187:
3181:
3179:
3178:
3173:
3171:
3168:
3165:
3153:
3152:
3137:
3135:
3134:
3129:
3127:
3124:
3121:
3109:
3108:
3093:
3091:
3090:
3085:
3083:
3080:
3077:
3065:
3064:
3046:
3037:
3035:
3034:
3029:
3024:
3022:
3021:
3012:
3004:
2999:
2997:
2996:
2989:
2988:
2971:
2960:
2958:
2957:
2939:
2934:
2932:
2931:
2913:
2908:
2906:
2905:
2893:
2884:
2882:
2881:
2876:
2874:
2870:
2863:
2862:
2833:
2831:
2830:
2825:
2823:
2821:
2820:
2811:
2803:
2794:
2792:
2791:
2786:
2784:
2780:
2773:
2772:
2741:
2739:
2738:
2733:
2731:
2727:
2720:
2719:
2718:
2717:
2700:
2699:
2678:
2676:
2675:
2670:
2668:
2664:
2657:
2656:
2627:
2612:
2610:
2609:
2604:
2593:
2592:
2564:
2562:
2561:
2556:
2551:
2547:
2540:
2539:
2512:
2510:
2509:
2504:
2478:
2474:
2467:
2466:
2439:
2428:
2426:
2425:
2420:
2415:
2413:
2412:
2400:
2391:
2387:
2385:
2384:
2379:
2377:
2376:
2360:
2356:
2352:
2350:
2349:
2344:
2342:
2341:
2325:
2321:
2307:
2305:
2304:
2299:
2294:
2292:
2291:
2279:
2270:
2255:
2253:
2252:
2247:
2245:
2244:
2226:
2225:
2213:
2212:
2196:
2185:
2181:
2177:
2173:
2162:
2160:
2159:
2154:
2152:
2151:
2135:
2131:
2128:Lemma 2: A node
2107:Lemma 1: As the
2099:
2095:
2080:
2076:
2072:
2069:
2057:
2054:or less for any
2053:
2045:
2043:
2042:
2037:
2016:
2014:
2013:
2008:
1978:
1976:
1975:
1970:
1936:
1934:
1933:
1928:
1895:
1891:
1887:
1880:
1876:
1872:
1868:
1866:
1865:
1860:
1830:
1823:
1821:
1820:
1815:
1810:
1806:
1799:
1798:
1794:
1739:
1736:
1730:
1727:
1720:
1717:
1710:
1699:
1695:
1691:
1680:
1676:
1661:
1646:
1635:
1633:
1632:
1627:
1567:.parent :=
1461:
1456:
1452:
1448:
1444:
1428:
1401:.parent :=
1294:
1290:
1267:
1256:
1252:
1248:
1244:
1243:
1230:
1229:
1224:
1223:
1218:
1216:
1215:
1210:
1171:
1167:
1163:
1155:
1151:
1147:
1143:
1139:
1135:
1131:
1127:
1123:
1119:
1115:
1099:
1087:
1077:Merging two sets
1049:.parent :=
952:
917:.parent :=
913:.parent
786:path compression
783:
775:
770:
766:
762:
758:
751:
747:
743:
739:
735:
719:
715:
705:
694:
665:.parent :=
637:
630:
626:
606:
602:
590:
538:
536:
535:
530:
503:
501:
500:
495:
453:
451:
450:
445:
400:
398:
397:
392:
376:
374:
373:
368:
351:
350:
304:for finding the
292:
280:
272:
255:
251:
201:, also called a
195:computer science
183:
171:
153:Space complexity
147:
139:
125:
112:
71:
70:
30:
29:
21:
5252:
5251:
5247:
5246:
5245:
5243:
5242:
5241:
5222:
5221:
5220:
5215:
5202:
5174:
5068:
5064:XOR linked list
5030:
5006:Circular buffer
4987:
4906:
4885:
4883:Data structures
4880:
4837:JGraphT library
4820:
4815:
4783:
4777:
4773:
4750:
4746:
4731:10.1145/2636922
4725:(1): 6:1–6:28.
4715:
4711:
4696:
4674:
4670:
4659:
4655:
4649:Jan van Leeuwen
4643:
4639:
4632:10.1137/0202024
4616:
4612:
4567:
4563:
4555:
4551:
4544:
4528:Stein, Clifford
4513:
4504:
4495:
4491:
4478:
4474:
4463:
4459:
4428:
4424:
4418:singleton sets.
4378:
4351:
4344:
4312:
4305:
4289:10.1145/62.2160
4261:
4252:
4245:10.1137/0202024
4225:Hopcroft, J. E.
4222:
4218:
4171:
4167:
4123:
4108:
4104:
4086:
4028:
4018:depends on the
4015:
4011:
4008:
3969:
3952:
3949:
3948:
3913:
3896:
3893:
3892:
3864:
3861:
3860:
3829:
3826:
3825:
3794:
3791:
3790:
3787:Union by weight
3778:
3775:
3770:
3737:
3733:
3715:
3711:
3702:
3698:
3689:
3685:
3677:
3674:
3673:
3645:
3641:
3624:
3620:
3612:
3610:
3604:
3600:
3594:
3581:
3577:
3575:
3572:
3571:
3541:
3537:
3531:
3510:
3506:
3496:
3483:
3479:
3477:
3474:
3473:
3451:
3447:
3426:
3422:
3420:
3417:
3416:
3412:
3408:
3404:
3396:
3379:
3375:
3360:
3356:
3347:
3343:
3341:
3338:
3337:
3333:
3330:
3326:
3322:
3318:
3314:
3310:
3306:
3303:
3299:
3280:
3274:
3259:
3253:
3231:
3227:
3218:
3214:
3205:
3201:
3193:
3190:
3189:
3185:
3167:
3161:
3148:
3144:
3142:
3139:
3138:
3123:
3117:
3104:
3100:
3098:
3095:
3094:
3079:
3073:
3060:
3056:
3054:
3051:
3050:
3044:
3017:
3013:
3005:
3003:
2984:
2980:
2979:
2975:
2970:
2947:
2943:
2938:
2921:
2917:
2912:
2901:
2897:
2892:
2890:
2887:
2886:
2858:
2854:
2847:
2843:
2841:
2838:
2837:
2816:
2812:
2804:
2802:
2800:
2797:
2796:
2768:
2764:
2757:
2753:
2751:
2748:
2747:
2713:
2709:
2708:
2704:
2695:
2691:
2690:
2686:
2684:
2681:
2680:
2652:
2648:
2641:
2637:
2635:
2632:
2631:
2622:
2588:
2584:
2576:
2573:
2572:
2535:
2531:
2524:
2520:
2518:
2515:
2514:
2462:
2458:
2451:
2447:
2445:
2442:
2441:
2437:
2430:
2408:
2404:
2399:
2397:
2394:
2393:
2389:
2372:
2368:
2366:
2363:
2362:
2358:
2354:
2337:
2333:
2331:
2328:
2327:
2323:
2319:
2287:
2283:
2278:
2276:
2273:
2272:
2268:
2258:
2234:
2230:
2221:
2217:
2208:
2204:
2202:
2199:
2198:
2191:
2183:
2179:
2175:
2171:
2147:
2143:
2141:
2138:
2137:
2133:
2129:
2126:
2097:
2082:
2078:
2074:
2070:
2067:
2064:
2055:
2051:
2022:
2019:
2018:
1984:
1981:
1980:
1946:
1943:
1942:
1901:
1898:
1897:
1896:operations, to
1893:
1889:
1885:
1878:
1874:
1870:
1836:
1833:
1832:
1828:
1790:
1780:
1776:
1769:
1765:
1745:
1742:
1741:
1737:
1732:
1731:operations and
1728:
1722:
1718:
1715:
1701:
1697:
1693:
1682:
1678:
1674:
1671:
1669:Time complexity
1648:
1637:
1609:
1606:
1605:
1602:
1459:
1454:
1450:
1446:
1442:
1435:
1426:
1423:
1292:
1288:
1285:
1258:
1254:
1250:
1246:
1233:
1232:
1227:
1226:
1221:
1220:
1177:
1174:
1173:
1169:
1165:
1161:
1153:
1149:
1145:
1141:
1137:
1133:
1129:
1125:
1121:
1117:
1105:
1097:
1085:
1079:
1074:
1014:
950:
940:
845:
781:
773:
768:
764:
760:
756:
749:
745:
741:
737:
733:
730:
717:
713:
696:
695:nodes requires
692:
689:
635:
628:
624:
621:
619:Making new sets
613:
604:
592:
584:
573:
558:proof assistant
509:
506:
505:
471:
468:
467:
418:
415:
414:
386:
383:
382:
346:
342:
334:
331:
330:
319:
286:
274:
257:
253:
249:
174:
162:
142:
134:
116:
103:
75:Time complexity
28:
23:
22:
15:
12:
11:
5:
5250:
5240:
5239:
5234:
5217:
5216:
5214:
5213:
5207:
5204:
5203:
5201:
5200:
5195:
5190:
5184:
5182:
5176:
5175:
5173:
5172:
5171:
5170:
5160:
5159:
5158:
5156:Hilbert R-tree
5153:
5148:
5138:
5137:
5136:
5134:Fibonacci heap
5131:
5126:
5116:
5115:
5114:
5109:
5104:
5102:Red–black tree
5099:
5094:
5084:
5078:
5076:
5070:
5069:
5067:
5066:
5061:
5056:
5051:
5046:
5040:
5038:
5032:
5031:
5029:
5028:
5023:
5018:
5013:
5008:
5003:
4997:
4995:
4989:
4988:
4986:
4985:
4984:
4983:
4978:
4968:
4967:
4966:
4959:Priority queue
4956:
4955:
4954:
4944:
4939:
4934:
4933:
4932:
4927:
4916:
4914:
4908:
4907:
4905:
4904:
4899:
4893:
4891:
4887:
4886:
4879:
4878:
4871:
4864:
4856:
4850:
4849:
4844:
4839:
4830:
4826:, part of the
4819:
4818:External links
4816:
4814:
4813:
4771:
4744:
4709:
4694:
4668:
4653:
4637:
4626:(4): 294–303.
4610:
4581:(2): 215–225.
4561:
4557:Raimund Seidel
4549:
4542:
4502:
4489:
4472:
4457:
4438:(3): 319–344.
4422:
4376:
4342:
4329:(2): 110–127.
4303:
4282:(2): 245–281.
4250:
4239:(4): 294–303.
4216:
4194:(5): 301–303.
4165:
4136:(2): 215–225.
4105:
4103:
4100:
4099:
4098:
4093:
4085:
4082:
4027:
4024:
4007:
4004:
3991:
3988:
3985:
3982:
3979:
3976:
3972:
3968:
3965:
3962:
3959:
3956:
3935:
3932:
3929:
3926:
3923:
3920:
3916:
3912:
3909:
3906:
3903:
3900:
3880:
3877:
3874:
3871:
3868:
3848:
3845:
3842:
3839:
3836:
3833:
3813:
3810:
3807:
3804:
3801:
3798:
3774:
3771:
3769:
3766:
3754:
3751:
3748:
3745:
3740:
3736:
3732:
3729:
3726:
3723:
3718:
3714:
3710:
3705:
3701:
3697:
3692:
3688:
3684:
3681:
3659:
3656:
3653:
3648:
3644:
3640:
3637:
3634:
3627:
3623:
3618:
3615:
3607:
3603:
3597:
3593:
3589:
3584:
3580:
3549:
3544:
3540:
3534:
3530:
3524:
3521:
3518:
3513:
3509:
3505:
3502:
3499:
3495:
3491:
3486:
3482:
3459:
3454:
3450:
3446:
3443:
3440:
3437:
3434:
3429:
3425:
3382:
3378:
3374:
3371:
3368:
3363:
3359:
3355:
3350:
3346:
3328:
3301:
3278:
3257:
3239:
3234:
3230:
3226:
3221:
3217:
3213:
3208:
3204:
3200:
3197:
3164:
3160:
3156:
3151:
3147:
3120:
3116:
3112:
3107:
3103:
3076:
3072:
3068:
3063:
3059:
3041:
3040:
3039:
3038:
3027:
3020:
3016:
3011:
3008:
3002:
2995:
2992:
2987:
2983:
2978:
2974:
2969:
2966:
2963:
2956:
2953:
2950:
2946:
2942:
2937:
2930:
2927:
2924:
2920:
2916:
2911:
2904:
2900:
2896:
2873:
2869:
2866:
2861:
2857:
2853:
2850:
2846:
2819:
2815:
2810:
2807:
2783:
2779:
2776:
2771:
2767:
2763:
2760:
2756:
2744:
2743:
2742:
2730:
2726:
2723:
2716:
2712:
2707:
2703:
2698:
2694:
2689:
2667:
2663:
2660:
2655:
2651:
2647:
2644:
2640:
2602:
2599:
2596:
2591:
2587:
2583:
2580:
2554:
2550:
2546:
2543:
2538:
2534:
2530:
2527:
2523:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2477:
2473:
2470:
2465:
2461:
2457:
2454:
2450:
2418:
2411:
2407:
2403:
2375:
2371:
2340:
2336:
2309:
2297:
2290:
2286:
2282:
2243:
2240:
2237:
2233:
2229:
2224:
2220:
2216:
2211:
2207:
2165:
2150:
2146:
2113:
2063:
2060:
2035:
2032:
2029:
2026:
2006:
2003:
2000:
1997:
1994:
1991:
1988:
1968:
1965:
1962:
1959:
1956:
1953:
1950:
1926:
1923:
1920:
1917:
1914:
1911:
1908:
1905:
1858:
1855:
1852:
1849:
1846:
1843:
1840:
1813:
1809:
1805:
1802:
1797:
1793:
1789:
1786:
1783:
1779:
1775:
1772:
1768:
1764:
1761:
1758:
1755:
1752:
1749:
1670:
1667:
1625:
1622:
1619:
1616:
1613:
1595:.rank + 1
1591:.rank :=
1494: := Find(
1486: := Find(
1464:
1440:
1434:
1431:
1411:.size :=
1328: := Find(
1320: := Find(
1298:
1284:
1281:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1104:The operation
1078:
1075:
1021:
960:
956:Path splitting
850:
790:
729:
726:
640:
620:
617:
612:
609:
572:
571:Representation
569:
528:
525:
522:
519:
516:
513:
493:
490:
487:
484:
481:
478:
475:
443:
440:
437:
434:
431:
428:
425:
422:
390:
366:
363:
360:
357:
354:
349:
345:
341:
338:
318:
315:
246:amortized time
225:into disjoint
211:data structure
207:merge–find set
189:
188:
185:
184:
172:
160:
156:
155:
149:
148:
140:
132:
128:
127:
114:
101:
97:
96:
91:
86:
82:
81:
79:big O notation
67:
66:
57:
53:
52:
49:
45:
44:
41:
35:
34:
26:
9:
6:
4:
3:
2:
5249:
5238:
5235:
5233:
5230:
5229:
5227:
5212:
5209:
5208:
5205:
5199:
5196:
5194:
5191:
5189:
5186:
5185:
5183:
5181:
5177:
5169:
5166:
5165:
5164:
5161:
5157:
5154:
5152:
5149:
5147:
5144:
5143:
5142:
5139:
5135:
5132:
5130:
5129:Binomial heap
5127:
5125:
5122:
5121:
5120:
5117:
5113:
5110:
5108:
5105:
5103:
5100:
5098:
5095:
5093:
5090:
5089:
5088:
5085:
5083:
5080:
5079:
5077:
5075:
5071:
5065:
5062:
5060:
5057:
5055:
5052:
5050:
5047:
5045:
5042:
5041:
5039:
5037:
5033:
5027:
5026:Sparse matrix
5024:
5022:
5019:
5017:
5014:
5012:
5011:Dynamic array
5009:
5007:
5004:
5002:
4999:
4998:
4996:
4994:
4990:
4982:
4979:
4977:
4974:
4973:
4972:
4969:
4965:
4962:
4961:
4960:
4957:
4953:
4950:
4949:
4948:
4945:
4943:
4940:
4938:
4935:
4931:
4928:
4926:
4923:
4922:
4921:
4918:
4917:
4915:
4913:
4909:
4903:
4900:
4898:
4895:
4894:
4892:
4888:
4884:
4877:
4872:
4870:
4865:
4863:
4858:
4857:
4854:
4848:
4845:
4843:
4840:
4838:
4834:
4831:
4829:
4825:
4822:
4821:
4809:
4805:
4801:
4797:
4793:
4789:
4782:
4775:
4767:
4763:
4759:
4755:
4748:
4740:
4736:
4732:
4728:
4724:
4720:
4713:
4705:
4701:
4697:
4691:
4687:
4683:
4679:
4672:
4664:
4657:
4650:
4646:
4641:
4633:
4629:
4625:
4621:
4614:
4606:
4602:
4597:
4592:
4588:
4584:
4580:
4576:
4572:
4565:
4558:
4553:
4545:
4539:
4535:
4534:
4529:
4525:
4521:
4517:
4511:
4509:
4507:
4500:
4493:
4485:
4484:
4476:
4468:
4461:
4453:
4449:
4445:
4441:
4437:
4433:
4426:
4419:
4417:
4413:
4409:
4405:
4401:
4397:
4393:
4387:
4383:
4379:
4373:
4368:
4363:
4359:
4355:
4349:
4347:
4337:
4332:
4328:
4324:
4320:
4316:
4310:
4308:
4299:
4295:
4290:
4285:
4281:
4277:
4273:
4269:
4265:
4259:
4257:
4255:
4246:
4242:
4238:
4234:
4230:
4229:Ullman, J. D.
4226:
4220:
4211:
4207:
4202:
4197:
4193:
4189:
4188:
4183:
4179:
4175:
4169:
4161:
4157:
4152:
4147:
4143:
4139:
4135:
4131:
4127:
4121:
4119:
4117:
4115:
4113:
4111:
4106:
4097:
4094:
4091:
4088:
4087:
4081:
4079:
4074:
4072:
4068:
4064:
4060:
4055:
4053:
4049:
4045:
4041:
4032:
4023:
4021:
4003:
3986:
3983:
3980:
3977:
3974:
3970:
3966:
3963:
3960:
3954:
3930:
3927:
3924:
3921:
3918:
3914:
3910:
3907:
3904:
3898:
3878:
3875:
3872:
3869:
3866:
3843:
3840:
3837:
3831:
3824:(i.e., it is
3808:
3805:
3802:
3788:
3784:
3783:Union by rank
3765:
3752:
3746:
3743:
3738:
3734:
3730:
3724:
3721:
3716:
3712:
3708:
3703:
3699:
3695:
3690:
3686:
3682:
3679:
3670:
3657:
3654:
3651:
3646:
3642:
3638:
3635:
3632:
3625:
3621:
3616:
3613:
3605:
3601:
3595:
3591:
3587:
3582:
3578:
3569:
3565:
3560:
3547:
3542:
3538:
3532:
3528:
3519:
3516:
3511:
3507:
3503:
3500:
3493:
3489:
3484:
3480:
3470:
3457:
3452:
3448:
3444:
3441:
3438:
3435:
3432:
3427:
3423:
3402:
3380:
3376:
3372:
3369:
3366:
3361:
3357:
3353:
3348:
3344:
3296:
3292:
3288:
3284:
3277:
3271:
3267:
3263:
3256:
3250:
3237:
3232:
3228:
3224:
3219:
3215:
3211:
3206:
3202:
3198:
3195:
3182:
3162:
3158:
3154:
3149:
3145:
3118:
3114:
3110:
3105:
3101:
3074:
3070:
3066:
3061:
3057:
3048:
3025:
3018:
3014:
3009:
3006:
3000:
2993:
2990:
2985:
2981:
2976:
2972:
2967:
2964:
2961:
2954:
2951:
2948:
2944:
2940:
2935:
2928:
2925:
2922:
2918:
2914:
2909:
2902:
2898:
2894:
2871:
2867:
2864:
2859:
2855:
2851:
2848:
2844:
2835:
2834:
2817:
2813:
2808:
2805:
2781:
2777:
2774:
2769:
2765:
2761:
2758:
2754:
2745:
2728:
2724:
2721:
2714:
2710:
2705:
2701:
2696:
2692:
2687:
2665:
2661:
2658:
2653:
2649:
2645:
2642:
2638:
2629:
2628:
2626:
2620:
2619:
2618:
2597:
2594:
2589:
2585:
2578:
2569:
2565:
2552:
2548:
2544:
2541:
2536:
2532:
2528:
2525:
2521:
2497:
2494:
2491:
2488:
2485:
2479:
2475:
2471:
2468:
2463:
2459:
2455:
2452:
2448:
2433:
2429:
2416:
2409:
2405:
2401:
2373:
2369:
2338:
2334:
2326:has at least
2317:
2308:
2295:
2288:
2284:
2280:
2262:
2257:
2241:
2238:
2235:
2231:
2227:
2222:
2218:
2214:
2209:
2205:
2194:
2189:
2188:Union by Rank
2178:has at least
2164:
2148:
2144:
2136:has at least
2125:
2124:fact either.
2122:
2121:Union by Rank
2112:
2110:
2109:find function
2105:
2103:
2093:
2089:
2085:
2059:
2049:
2030:
2024:
1998:
1992:
1960:
1954:
1940:
1918:
1912:
1909:
1892:of which are
1882:
1877:of which are
1853:
1850:
1847:
1844:
1825:
1807:
1803:
1800:
1795:
1791:
1787:
1784:
1781:
1777:
1773:
1770:
1766:
1762:
1759:
1756:
1753:
1735:
1725:
1712:
1708:
1704:
1689:
1685:
1666:
1663:
1659:
1655:
1651:
1644:
1640:
1620:
1617:
1614:
1601:
1598:
1594:
1590:
1587:
1583:
1579:
1576:
1573:
1570:
1566:
1563:
1560:
1556:
1552:
1548:
1544:
1540:
1536:
1532:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1508:
1504:
1501:
1497:
1493:
1489:
1485:
1482:
1479:
1475:
1471:
1467:
1463:
1438:
1433:Union by rank
1430:
1422:
1418:
1414:
1410:
1407:
1404:
1400:
1397:
1394:
1390:
1386:
1382:
1378:
1374:
1370:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1338:
1335:
1331:
1327:
1323:
1319:
1316:
1313:
1309:
1305:
1301:
1297:
1283:Union by size
1280:
1278:
1277:union by rank
1274:
1273:union by size
1269:
1265:
1261:
1241:
1237:
1206:
1203:
1200:
1197:
1194:
1191:
1188:
1185:
1182:
1179:
1157:
1113:
1109:
1094:
1083:
1073:
1070:
1067:
1064:
1060:
1056:
1052:
1048:
1045:
1042:
1038:
1035:
1032:
1028:
1024:
1020:
1018:
1013:
1010:
1007:
1004:
1000:
996:
992:
988:
984:
981:
977:
974:
971:
967:
963:
959:
957:
948:
944:
939:
936:
933:
930:
927:
923:
920:
916:
912:
908:
905:
902:
898:
895:
892:
888:
884:
881:
878:
874:
871:
868:
864:
861:
857:
853:
849:
844:
841:
838:
835:
832:
828:
825:
821:
817:
814:
811:
807:
804:
801:
797:
793:
789:
787:
778:
755:Performing a
753:
725:
723:
722:dynamic array
712:In practice,
710:
707:
703:
699:
688:
685:
682:
678:
675:
671:
668:
664:
661:
657:
654:
651:
647:
643:
639:
632:
616:
608:
600:
596:
588:
580:
578:
568:
564:
562:
559:
555:
550:
547:
544:
542:
523:
520:
517:
511:
485:
479:
465:
461:
457:
435:
429:
426:
420:
412:
411:Robert Tarjan
408:
404:
388:
380:
358:
352:
347:
343:
336:
328:
324:
314:
312:
307:
303:
298:
296:
290:
284:
278:
270:
266:
262:
261:
247:
243:
239:
234:
232:
228:
224:
220:
216:
212:
208:
204:
200:
196:
181:
177:
173:
169:
165:
161:
157:
154:
150:
145:
141:
137:
133:
129:
123:
119:
115:
110:
106:
102:
98:
95:
92:
90:
87:
83:
80:
76:
72:
68:
65:
61:
58:
54:
50:
46:
43:multiway tree
42:
40:
36:
31:
19:
4981:Disjoint-set
4980:
4791:
4787:
4774:
4757:
4753:
4747:
4722:
4718:
4712:
4677:
4671:
4662:
4656:
4640:
4623:
4619:
4613:
4578:
4574:
4564:
4552:
4532:
4492:
4482:
4475:
4466:
4460:
4435:
4431:
4425:
4415:
4411:
4407:
4403:
4399:
4395:
4391:
4389:
4357:
4326:
4322:
4279:
4275:
4236:
4232:
4219:
4191:
4185:
4180:(May 1964).
4168:
4133:
4129:
4075:
4073:of a graph.
4069:to find the
4056:
4037:
4026:Applications
4019:
4009:
3786:
3782:
3776:
3671:
3561:
3471:
3297:
3290:
3286:
3282:
3275:
3272:
3265:
3261:
3254:
3251:
3183:
3049:
3042:
2624:
2616:
2434:
2431:
2313:
2266:
2192:
2169:
2127:
2117:
2106:
2100:denotes the
2091:
2087:
2083:
2065:
1883:
1881:operations.
1826:
1733:
1723:
1713:
1706:
1702:
1687:
1683:
1672:
1664:
1657:
1653:
1649:
1642:
1638:
1603:
1600:end function
1599:
1596:
1592:
1588:
1585:
1581:
1577:
1574:
1571:
1568:
1564:
1561:
1558:
1554:
1550:
1546:
1542:
1538:
1534:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1502:
1499:
1495:
1491:
1487:
1483:
1480:
1477:
1473:
1469:
1465:
1436:
1424:
1421:end function
1420:
1416:
1412:
1408:
1405:
1402:
1398:
1395:
1392:
1388:
1384:
1380:
1376:
1372:
1368:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1336:
1333:
1329:
1325:
1321:
1317:
1314:
1311:
1307:
1303:
1299:
1286:
1276:
1272:
1270:
1263:
1259:
1239:
1235:
1219:and execute
1158:
1111:
1107:
1103:
1072:end function
1071:
1068:
1065:
1062:
1061:.parent
1058:
1054:
1050:
1046:
1043:
1040:
1036:
1033:
1030:
1026:
1022:
1017:Path halving
1016:
1015:
1012:end function
1011:
1008:
1005:
1002:
998:
994:
990:
986:
982:
979:
975:
972:
969:
965:
961:
955:
941:
938:end function
937:
934:
931:
928:
925:
921:
918:
914:
910:
906:
903:
900:
896:
893:
890:
889:.parent
886:
882:
879:
876:
872:
869:
866:
862:
859:
855:
851:
846:
843:end function
842:
839:
836:
833:
830:
829:.parent
826:
823:
819:
815:
812:
809:
805:
802:
799:
795:
791:
785:
779:
754:
731:
711:
708:
701:
697:
690:
687:end function
686:
683:
680:
676:
673:
669:
666:
662:
659:
655:
652:
649:
645:
641:
633:
622:
614:
598:
594:
586:
581:
574:
565:
551:
548:
545:
540:
466:showed that
320:
299:
288:
276:
268:
264:
259:
237:
235:
206:
202:
198:
192:
179:
175:
167:
163:
143:
135:
121:
117:
108:
104:
93:
88:
5124:Binary heap
5049:Linked list
4410:Find's and
4354:Fredman, M.
4052:unification
3672:Therefore,
3472:Therefore,
2885:is at most
2795:is at most
2271:is at most
2081:objects is
1549:) := (
1533:.rank <
1383:) := (
1367:.size <
1228:Union(2, 3)
1222:Union(1, 2)
1152:'s root to
1144:'s root to
1128:first uses
947:Van Leeuwen
409:. In 1975,
126:(amortized)
113:(amortized)
56:Invented by
5226:Categories
5112:Splay tree
5016:Hash table
4897:Collection
4835:, part of
4794:: 93–124.
4695:1581130678
4377:0897913078
4102:References
2613:Union Find
2174:with rank
1039:.parent ≠
978:.parent ≠
899:.parent ≠
875:.parent ≠
808:.parent ≠
611:Operations
554:persistent
313:problems.
94:Worst case
5168:Hash tree
5054:Skip list
5001:Bit array
4902:Container
4596:1813/5942
4452:207160759
4151:1813/5942
3984:
3978:
3964:
3928:
3922:
3908:
3841:
3806:
3797:Θ
3744:
3739:∗
3652:
3647:∗
3633:≤
3592:∑
3588:≤
3529:∑
3517:−
3494:∑
3490:≤
3439:−
3433:−
3370:…
3188:finds is
3159:∑
3115:∑
3071:∑
3001:≤
2991:−
2965:⋯
2865:−
2775:−
2722:−
2659:−
2595:
2590:∗
2571:Proof of
2542:−
2495:−
2469:−
2025:α
1993:α
1987:Ω
1955:α
1949:Θ
1913:α
1904:Θ
1851:
1839:Θ
1801:
1763:⋅
1748:Θ
1641:(log log
1624:⌋
1618:
1612:⌊
1198:…
1063:end while
1057: :=
1003:end while
997:.parent,
929:end while
924: :=
909: :=
891:end while
885: :=
865: :=
748:itself.
521:
480:α
474:Ω
430:α
353:
348:∗
85:Operation
5097:AVL tree
4976:Multiset
4925:Multimap
4912:Abstract
4808:14619034
4739:12767012
4665:: 32–38.
4605:11105749
4386:13470414
4317:(1979).
4270:(1984).
4160:11105749
4084:See also
4006:Deletion
3313:, where
2679:will be
2096:, where
1656:log log
1580:.rank =
1466:function
1415:.size +
1300:function
1023:function
962:function
852:function
792:function
644:MakeSet(
642:function
403:Hopcroft
273:, where
215:disjoint
48:Invented
5151:R+ tree
5146:R* tree
5092:AA tree
4298:5363073
4210:9034016
4020:current
3401:Lemma 1
3332:). Fix
2316:lemma 2
2256:nodes.
2163:nodes.
2046:is the
1894:MakeSet
1879:MakeSet
1719:MakeSet
1255:Find(1)
1231:, ...,
1086:MakeSet
714:MakeSet
636:MakeSet
629:MakeSet
625:MakeSet
460:Fredman
317:History
227:subsets
209:, is a
89:Average
5180:Graphs
5141:R-tree
5082:B-tree
5036:Linked
4993:Arrays
4806:
4737:
4704:100111
4702:
4692:
4603:
4540:
4450:
4384:
4374:
4296:
4208:
4158:
4046:of an
1711:time.
1597:end if
1584:.rank
1559:end if
1557:)
1537:.rank
1519:end if
1513:return
1498:)
1490:)
1468:Union(
1419:.size
1393:end if
1391:)
1371:.size
1353:end if
1347:return
1332:)
1324:)
1302:Union(
1234:Union(
1106:Union(
1066:return
1006:return
943:Tarjan
932:return
926:parent
907:parent
840:end if
834:return
824:return
706:time.
684:end if
585:Θ(log
407:Ullman
377:, the
242:forest
131:Insert
100:Search
5074:Trees
4947:Queue
4942:Stack
4890:Types
4804:S2CID
4784:(PDF)
4735:S2CID
4700:S2CID
4601:S2CID
4448:S2CID
4382:S2CID
4294:S2CID
4206:S2CID
4156:S2CID
2314:From
2311:Proof
2167:Proof
2115:Proof
2075:Union
1729:Union
1698:Union
1679:Union
1238:- 1,
1162:Union
1126:Union
1098:Union
1034:while
1025:Find(
973:while
964:Find(
894:while
870:while
854:Find(
794:Find(
401:, by
231:union
159:Space
5163:Trie
5119:Heap
4937:List
4690:ISBN
4647:and
4538:ISBN
4372:ISBN
4076:The
4016:Find
4012:Find
3779:Find
3566:and
3445:<
3317:and
3298:For
3043:Let
2090:log
2071:Find
1869:for
1829:Find
1738:Find
1696:and
1694:Find
1675:Find
1586:then
1539:then
1510:then
1460:Find
1453:and
1445:and
1439:rank
1373:then
1344:then
1291:and
1156:'s.
1136:and
1130:Find
951:Find
945:and
935:root
919:root
901:root
887:root
883:root
877:root
873:root
863:root
831:else
813:then
782:Find
774:Find
769:Find
765:Find
761:Find
757:Find
750:Find
734:Find
732:The
660:then
623:The
597:log
464:Saks
462:and
405:and
325:and
219:sets
197:, a
62:and
51:1964
39:Type
4971:Set
4796:doi
4762:doi
4758:412
4727:doi
4682:doi
4628:doi
4591:hdl
4583:doi
4440:doi
4362:doi
4331:doi
4284:doi
4241:doi
4196:doi
4146:hdl
4138:doi
3981:log
3975:log
3961:log
3925:log
3919:log
3905:log
3838:log
3803:log
3789:is
3785:or
3735:log
3643:log
3309:to
3289:log
2623:log
2586:log
2392:is
2195:+ 1
2098:log
2073:or
1848:log
1778:log
1726:− 1
1615:log
1275:or
1257:is
561:Coq
541:any
518:log
381:of
344:log
205:or
193:In
146:(1)
138:(1)
120:(α(
107:(α(
77:in
5228::
4802:.
4792:21
4790:.
4786:.
4756:.
4733:.
4723:11
4721:.
4698:.
4688:.
4622:.
4599:.
4589:.
4579:22
4577:.
4573:.
4526:;
4522:;
4518:;
4505:^
4446:.
4436:23
4434:.
4402:,
4398:α(
4388:.
4380:.
4370:.
4345:^
4327:18
4325:.
4321:.
4306:^
4292:.
4280:31
4278:.
4274:.
4266:;
4253:^
4235:.
4227:;
4204:.
4190:.
4184:.
4176:;
4154:.
4144:.
4134:22
4132:.
4109:^
4054:.
3295:.
3281:=
3270:.
3260:=
2104:.
1824:.
1575:if
1553:,
1545:,
1528:if
1505:=
1500:if
1478:is
1476:)
1472:,
1387:,
1379:,
1362:if
1339:=
1334:if
1312:is
1310:)
1306:,
1268:.
1225:,
1110:,
1044:do
1031:is
1029:)
989:,
983:do
970:is
968:)
904:do
880:do
860:is
858:)
803:if
800:is
798:)
653:if
650:is
648:)
607:.
593:Θ(
287:α(
275:α(
271:))
267:α(
124:))
111:))
4875:e
4868:t
4861:v
4810:.
4798::
4768:.
4764::
4741:.
4729::
4706:.
4684::
4634:.
4630::
4624:2
4607:.
4593::
4585::
4546:.
4454:.
4442::
4416:n
4412:n
4408:m
4404:n
4400:m
4396:m
4392:n
4364::
4339:.
4333::
4300:.
4286::
4247:.
4243::
4237:2
4212:.
4198::
4192:7
4162:.
4148::
4140::
3990:)
3987:n
3971:/
3967:n
3958:(
3955:O
3934:)
3931:n
3915:/
3911:n
3902:(
3899:O
3879:n
3876:o
3873:i
3870:n
3867:u
3847:)
3844:n
3835:(
3832:O
3812:)
3809:n
3800:(
3753:.
3750:)
3747:n
3731:m
3728:(
3725:O
3722:=
3717:3
3713:T
3709:+
3704:2
3700:T
3696:+
3691:1
3687:T
3683:=
3680:T
3658:.
3655:n
3639:n
3636:2
3626:B
3622:2
3617:n
3614:2
3606:B
3602:2
3596:B
3583:3
3579:T
3568:2
3564:1
3548:.
3543:B
3539:2
3533:u
3523:]
3520:1
3512:B
3508:2
3504:,
3501:B
3498:[
3485:3
3481:T
3458:.
3453:B
3449:2
3442:B
3436:1
3428:B
3424:2
3413:B
3409:u
3405:k
3397:v
3381:k
3377:v
3373:,
3367:,
3362:2
3358:v
3354:,
3349:1
3345:v
3334:u
3329:1
3327:T
3323:v
3319:v
3315:u
3311:v
3307:u
3302:3
3300:T
3293:)
3291:n
3287:m
3285:(
3283:O
3279:2
3276:T
3268:)
3266:m
3264:(
3262:O
3258:1
3255:T
3238:.
3233:3
3229:T
3225:+
3220:2
3216:T
3212:+
3207:1
3203:T
3199:=
3196:T
3186:m
3163:F
3155:=
3150:3
3146:T
3119:F
3111:=
3106:2
3102:T
3075:F
3067:=
3062:1
3058:T
3045:F
3026:.
3019:B
3015:2
3010:n
3007:2
2994:1
2986:B
2982:2
2977:2
2973:n
2968:+
2962:+
2955:2
2952:+
2949:B
2945:2
2941:n
2936:+
2929:1
2926:+
2923:B
2919:2
2915:n
2910:+
2903:B
2899:2
2895:n
2872:]
2868:1
2860:B
2856:2
2852:,
2849:B
2845:[
2818:B
2814:2
2809:n
2806:2
2782:]
2778:1
2770:B
2766:2
2762:,
2759:B
2755:[
2729:]
2725:1
2715:B
2711:2
2706:2
2702:,
2697:B
2693:2
2688:[
2666:]
2662:1
2654:B
2650:2
2646:,
2643:B
2639:[
2625:n
2601:)
2598:n
2582:(
2579:O
2553:.
2549:]
2545:1
2537:R
2533:2
2529:,
2526:R
2522:[
2501:]
2498:1
2492:R
2489:,
2486:r
2483:[
2480:=
2476:]
2472:1
2464:r
2460:2
2456:,
2453:r
2449:[
2438:B
2417:.
2410:r
2406:2
2402:n
2390:r
2374:r
2370:2
2359:r
2355:r
2339:r
2335:2
2324:r
2320:u
2296:.
2289:r
2285:2
2281:n
2269:r
2242:1
2239:+
2236:r
2232:2
2228:=
2223:r
2219:2
2215:+
2210:r
2206:2
2193:r
2184:r
2180:2
2176:r
2172:u
2149:r
2145:2
2134:r
2130:u
2094:)
2092:n
2088:m
2086:(
2084:O
2079:n
2068:m
2056:n
2052:4
2034:)
2031:n
2028:(
2005:)
2002:)
1999:n
1996:(
1990:(
1967:)
1964:)
1961:n
1958:(
1952:(
1925:)
1922:)
1919:n
1916:(
1910:m
1907:(
1890:n
1886:m
1875:n
1871:m
1857:)
1854:n
1845:m
1842:(
1812:)
1808:)
1804:n
1796:n
1792:/
1788:f
1785:+
1782:2
1774:+
1771:1
1767:(
1760:f
1757:+
1754:n
1751:(
1734:f
1724:n
1716:n
1709:)
1707:n
1705:(
1703:O
1690:)
1688:n
1686:(
1684:O
1660:)
1658:n
1654:n
1652:(
1650:O
1645:)
1643:n
1639:O
1621:n
1593:x
1589:x
1582:y
1578:x
1569:x
1565:y
1555:x
1551:y
1547:y
1543:x
1541:(
1535:y
1531:x
1507:y
1503:x
1496:y
1492:y
1488:x
1484:x
1474:y
1470:x
1455:y
1451:x
1447:y
1443:x
1427:n
1417:y
1413:x
1409:x
1403:x
1399:y
1389:x
1385:y
1381:y
1377:x
1375:(
1369:y
1365:x
1341:y
1337:x
1330:y
1326:y
1322:x
1318:x
1308:y
1304:x
1293:y
1289:x
1266:)
1264:n
1262:(
1260:O
1251:n
1247:n
1242:)
1240:n
1236:n
1207:,
1204:n
1201:,
1195:,
1192:3
1189:,
1186:2
1183:,
1180:1
1170:y
1166:x
1154:x
1150:y
1146:y
1142:x
1138:y
1134:x
1122:y
1118:x
1114:)
1112:y
1108:x
1069:x
1059:x
1055:x
1051:x
1047:x
1041:x
1037:x
1027:x
1009:x
999:x
995:x
991:x
987:x
985:(
980:x
976:x
966:x
922:x
915:x
911:x
897:x
867:x
856:x
837:x
827:x
820:x
816:x
810:x
806:x
796:x
746:x
742:x
738:x
718:x
704:)
702:n
700:(
698:O
693:n
677:x
670:x
667:x
663:x
656:x
646:x
605:n
601:)
599:n
595:n
589:)
587:n
527:)
524:n
515:(
512:O
492:)
489:)
486:n
483:(
477:(
454:(
442:)
439:)
436:n
433:(
427:m
424:(
421:O
389:n
365:)
362:)
359:n
356:(
340:(
337:O
291:)
289:n
279:)
277:n
269:n
265:m
263:(
260:O
254:n
250:m
182:)
180:n
178:(
176:O
170:)
168:n
166:(
164:O
144:O
136:O
122:n
118:O
109:n
105:O
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.