121:
5656:
are uniquely mapped into the edges of this multilevel partition. There may be some edges in the multilevel partition that do not correspond to any node in the top tree, these are the edges which represent only a single child in the level below it, i.e. a simple cluster. Only the edges that correspond
3587:
Similar task could be formulated for graph with edges with nonunit lengths. In that case the distance could address an edge or a vertex between two edges. We could define Choose such that the edge leading to the vertex is returned in the latter case. There could be defined update increasing all edge
124:
An image depicting a top tree built on an underlying tree (black nodes). A tree divided into edge clusters and the complete top-tree for it. Filled nodes in the top-tree are path-clusters, while small circle nodes are leaf-clusters. The big circle node is the root. Capital letters denote clusters,
3240:
queries and reorganization of the top tree (using the
Internal operations) such that it locates the only edge in intersection of all selected clusters. Sometimes the search should be limited to a path. There is a variant of nonlocal search for such purposes. If there are two external boundary
5485:
Amortized implementations are more simple, and with small multiplicative factors in time complexity. On the contrary the worst case implementations allow speeding up queries by switching off unneeded info updates during the query (implemented by
3812:
2440:
2238:
2077:
845:
811:
5328:
1375:
allowing the user a wide variety of flexibility and productivity without going into the details of the internal workings of the data structure, something which is also referred to as the
6028:
1992:
time. It may happen that during a tree update, a leaf cluster may change to a path cluster and the converse. Updates to top tree are done exclusively by these internal operations.
5793:
5743:
5130:
5088:
4937:
4850:
4235:
3909:
2928:
1990:
1951:
948:
5252:
4298:
718:
3542:
3296:
437:
357:
5450:
3233:
3195:
3033:
2379:
2340:
312:
6062:
Holm, J.; De
Lichtenberg, K.; Thorup, M. (2001). "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity".
5930:
Holm, J.; De
Lichtenberg, K.; Thorup, M. (2001). "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity".
5553:
5408:
4132:
3509:
3125:
2994:
2752:
2719:
2686:
2653:
2539:
2506:
2473:
2304:
2271:
2026:
1114:
2620:
5631:
4544:
4373:
4064:
3747:
1896:
1313:
1239:
1164:
619:
5704:
5601:
5577:
5520:
5044:
5020:
4996:
4786:
4730:
4663:
4639:
4615:
4591:
4567:
4517:
4493:
4469:
4445:
4421:
4397:
4346:
4322:
4262:
3971:
3770:
3714:
3686:
3478:
3401:
3373:
3263:
3149:
3057:
2862:
2776:
2563:
2403:
2201:
2177:
2153:
2125:
2101:
1862:
1723:
1696:
1649:
1483:
1456:
1362:
1038:
1011:
980:
909:
773:
749:
682:
654:
561:
489:
461:
381:
276:
224:
87:
5375:
5197:
252:
1586:
1263:
1188:
588:
112:
3997:
3944:
2837:
1625:
4099:
3092:
2962:
2897:
5678:
4969:
4762:
1672:
1528:
5752:
If a lower level is changed by an update then we should be able to update the one immediately above it using at most a constant number of insertions and deletions.
5654:
2583:
1769:
1746:
1547:
1506:
1338:
1286:
1212:
1137:
1078:
1058:
885:
180:
60:
3838:
5917:. Section 10.4: Representing rooted trees, pp. 214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253–320.
4855:
Proof outline: This requires maintaining additional information about the maximum weight non cluster path edge in a cluster under the Merge and Split operations.
4706:
3454:
4898:
4878:
4811:
4683:
4196:
4176:
4156:
4037:
4017:
3858:
3661:
3638:
3618:
3582:
3562:
3431:
3348:
3328:
1838:
1818:
1798:
1432:
1412:
3868:
A number of interesting applications originally implemented by other methods have been easily implemented using the top tree's interface. Some of them include
3298:. It is sufficient to do following modification: If only one of root cluster children is path cluster, it is selected by default without calling the
5145:, the graph is subject to edge deletions and insertions, as well as queries asking whether a pair of vertices are two-edge connected, or there is a
182:
can be called as
External Boundary Vertices, they can be thought of as Boundary Vertices of the cluster which represents the entire top tree.
6418:
6625:
5335:
The graph could be maintained allowing to update the edge set and ask queries on vertex 2-connectivity. Amortized complexity of updates is
3949:
Proof outline: It involves maintaining at each node the maximum weight (max_wt) on its cluster path, if it is a point cluster then max_wt(
3999:
When a cluster is a union of two clusters then it is the maximum value of the two merged clusters. If we have to find the max wt between
6142:
6169:
5914:
5882:
1317:
Sibling clusters are neighbours in the sense that they intersect in a single vertex, and then their parent cluster is their union.
6285:
5872:
5855:
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
3840:. To support the operation the maximal distance in the cluster subtree from a boundary vertex should be maintained in the
2786:. If Split does not use Clean subroutine, and Clean is required, its effect could be achieved with overhead by combining
5490:
techniques). After the query is answered the original state of the top tree is used and the query version is discarded.
5259:
3775:
2408:
2206:
2037:
32:
5479:
5093:
The Center and Median can me maintained under Link(Merge) and Cut(Split) operations and queried by non local search in
816:
782:
5474:(Top-trees and dynamic graph algorithms Jacob Holm and Kristian de Lichtenberg. Technical Report), and even by using
5255:
5150:
6250:
5905:
3588:
lengths along a path by a constant. In such scenario these updates are done in constant time just in root cluster.
5269:
6635:
5487:
1372:
6191:
3198:
operation which for a root (nonleaf) cluster selects one of its child clusters. The top tree blackbox provides
1800:
contains at most 2 vertices. It makes original external vertices to be normal vertices and makes vertices from
5982:
5482:(with worst case time bounds) (Alstrup et al. Maintaining Information in Fully Dynamic Trees with Top Trees).
3663:
could be done by finding either bicenter edge or edge with center as one endpoint. The edge could be found by
515:
A Leaf in the original
Cluster is represented by a Cluster with just a single Boundary Vertex and is called a
5759:
5709:
5096:
5054:
4903:
4816:
4201:
3875:
2902:
1956:
1917:
914:
5202:
4267:
687:
6162:
5458:
3514:
3268:
409:
329:
5413:
3203:
3165:
3003:
2349:
6681:
6329:
6178:
6097:
Bille, Philip; Gørtz, Inge Li; Landau, Gad M.; Weimann, Oren (2015). "Tree
Compression with Top Trees".
5146:
2309:
955:
281:
36:
28:
5525:
5380:
4104:
3483:
3097:
2966:
2724:
2691:
2658:
2625:
2511:
2478:
2445:
2276:
2243:
1998:
1086:
2595:
6319:
6274:
5892:
5819:
5609:
5142:
4522:
4351:
4042:
3725:
1867:
1291:
1217:
1142:
597:
5685:
5582:
5558:
5501:
5025:
5001:
4977:
4767:
4711:
4644:
4620:
4596:
4572:
4548:
4498:
4474:
4450:
4426:
4402:
4378:
4327:
4303:
4243:
3952:
3911:
time per link and cut, supporting queries about the maximum edge weight between any two vertices in
3751:
3695:
3667:
3459:
3382:
3354:
3244:
3130:
3038:
2843:
2757:
2544:
2384:
2182:
2158:
2134:
2106:
2082:
1843:
1704:
1677:
1630:
1464:
1437:
1368:
A tree with a single vertex has an empty top tree, and one with just an edge is just a single node.
1343:
1019:
992:
961:
890:
754:
730:
663:
635:
542:
470:
442:
362:
257:
205:
68:
6433:
6209:
5338:
5160:
229:
6289:
5470:
Top trees have been implemented in a variety of ways, some of them include implementation using a
1554:
1243:
1168:
568:
92:
6600:
6559:
6385:
6375:
6254:
6106:
6079:
6045:
5947:
6032:
Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on
Discrete Algorithms, {SODA} 2018
3976:
3914:
6494:
6195:
6155:
5910:
5878:
5814:
5138:
2805:
1596:
6585:
6116:
6071:
6035:
5939:
5896:
5888:
5858:
5840:
4069:
3062:
2932:
2867:
1080:
represents a cluster that is formed due to the union of the clusters that are its children.
5660:
4942:
4735:
1654:
1513:
6529:
6279:
5809:
5639:
2568:
1754:
1731:
1532:
1491:
1323:
1271:
1197:
1122:
1063:
1043:
870:
165:
45:
3817:
4688:
3436:
6482:
6477:
6360:
6294:
5900:
4883:
4863:
4796:
4793:(). We can ask for the maximum weight in the underlying tree containing a given vertex
4668:
4181:
4161:
4141:
4022:
4002:
3843:
3646:
3623:
3603:
3567:
3547:
3416:
3333:
3313:
2028:
is updated by calling a user defined function associated with each internal operation.
1823:
1803:
1783:
1417:
1397:
24:
4998:) of the cluster path. The length is maintained as the maximum weight except that, if
2797:
The next two functions are analogous to the above two and are used for base clusters.
6675:
6630:
6610:
6453:
6342:
6269:
5850:
5832:
5804:
5475:
5263:
5154:
6204:
6049:
6590:
6554:
6370:
6365:
6347:
6259:
6083:
5951:
5867:
2754:
such that it's known there is no pending update needed in its children. Than the
6640:
6605:
6595:
6509:
6443:
6438:
6428:
6337:
6186:
1780:: Is called as a subroutine for implementing most of the queries on a top tree.
865:
5979:
Holm, Jacob; Rotenberg, Eva; Thorup, Mikkel (2018), "Dynamic Bridge-Finding in
5457:
Top trees can be used to compress trees in a way that is never much worse than
6650:
6620:
6580:
6423:
6352:
6299:
6219:
6040:
5967:
Proceedings of the Thirty-Second Annual {ACM} Symposium on Theory of
Computing
5749:
The number of edges in subsequent levels should decrease by a constant factor.
35:. It has since been augmented to maintain dynamically various properties of a
6120:
4138:(). In the scenario of the above application we can also add a common weight
6655:
6615:
6462:
6390:
6380:
6138:
Maintaining
Information in Fully Dynamic Trees with Top Trees. Alstrup et al
5844:
5756:
The above partitioning strategy ensures the maintenance of the top tree in
6544:
6234:
6075:
5943:
5862:
5377:. Queries could be implemented even faster. The algorithm is not trivial,
5051:
Queries regarding diameter of a tree and its subsequent maintenance takes
31:
that is used mainly for various path-related operations. It allows simple
6534:
6514:
6487:
6472:
6224:
1016:
There is a one-to-one correspondence with the edges of the original tree
5965:
Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity",
6645:
6549:
6524:
6467:
6314:
6244:
6239:
6214:
6147:
6137:
6564:
6539:
6519:
6504:
6413:
6304:
6229:
5706:
into clusters. Only a careful strategy ensures that we end up in an
120:
6143:
Self-Adjusting Top Trees. Tarjan and
Werneck, Proc. 16th SoDA, 2005
6408:
6309:
6264:
6111:
5137:
Top trees are used in state-of-the-art algorithms for dynamic two-
3592:
is required to distribute the delayed update to the children. The
1953:
Internal Operations, the sequence of which is computed in further
887:
of logarithmic height in the number of nodes in the original tree
5839:, ACM Transactions on Algorithms (TALG), Vol. 1 (2005), 243–264,
5682:
A partitioning strategy is important while we partition the Tree
5636:
We would notice that all the nodes of the corresponding top tree
6400:
3860:. That requires maintenance of the cluster path length as well.
3564:. To support the operation the length must be maintained in the
6151:
858:
are used for maintaining a Dynamic forest (set of trees) under
154:
if it is connected to a vertex outside the subtree by an edge.
3872:(). We can maintain a dynamic collection of weighted trees in
813:
is a singleton set (they have exactly one node in common) and
5837:
Maintaining information in fully dynamic trees with top trees
4665:) := 0. Finally, to find the maximum weight on the path
1364:
itself, with a set of at most two External Boundary Vertices.
5765:
5715:
5691:
5615:
5588:
5564:
5534:
5507:
5392:
5102:
5060:
5031:
5007:
4983:
4909:
4822:
4773:
4717:
4650:
4626:
4602:
4578:
4554:
4528:
4504:
4480:
4456:
4432:
4408:
4384:
4357:
4333:
4309:
4279:
4249:
4207:
4113:
4048:
3958:
3881:
3757:
3731:
3701:
3673:
3526:
3465:
3388:
3360:
3280:
3250:
3212:
3174:
3136:
3109:
3044:
3012:
2978:
2849:
2763:
2736:
2703:
2670:
2637:
2604:
2550:
2523:
2490:
2457:
2424:
2414:
2390:
2358:
2321:
2288:
2255:
2222:
2212:
2188:
2164:
2140:
2112:
2088:
2056:
2046:
2010:
1962:
1923:
1849:
1710:
1683:
1636:
1470:
1443:
1349:
1297:
1223:
1148:
1092:
1025:
998:
967:
920:
896:
832:
822:
798:
788:
760:
736:
699:
669:
641:
603:
548:
476:
448:
421:
368:
341:
293:
263:
211:
74:
5857:, Journal of the ACM, Vol. 48 Issue 4(July 2001), 723–760,
5745:
height Multilevel Partition ( and therefore the top tree).
1387:
The following three are the user allowable Forest Updates.
5849:
Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and
5831:
Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and
5657:
to composite clusters correspond to nodes in the top tree
5157:
give a deterministic algorithm with amortized update time
2203:
and with boundary vertices as the boundary vertices of
1820:
the new External Boundary Vertices of the top tree. If
5046:) is the sum of lengths stored with its path children.
5985:
5762:
5712:
5688:
5663:
5642:
5633:
This is done recursively till only one edge remains.
5612:
5585:
5561:
5528:
5504:
5416:
5383:
5341:
5272:
5205:
5163:
5099:
5057:
5028:
5004:
4980:
4945:
4906:
4886:
4866:
4819:
4799:
4770:
4738:
4714:
4691:
4671:
4647:
4623:
4599:
4575:
4551:
4525:
4501:
4477:
4453:
4429:
4405:
4381:
4354:
4330:
4306:
4270:
4246:
4204:
4184:
4164:
4144:
4107:
4072:
4045:
4025:
4005:
3979:
3955:
3917:
3878:
3846:
3820:
3778:
3754:
3728:
3698:
3670:
3649:
3626:
3620:
would in that case require to maintain unitlength in
3606:
3570:
3550:
3517:
3486:
3462:
3439:
3419:
3385:
3357:
3336:
3316:
3271:
3247:
3206:
3168:
3133:
3100:
3065:
3041:
3006:
2969:
2935:
2905:
2870:
2846:
2808:
2778:
is discarded without calling user defined functions.
2760:
2727:
2694:
2661:
2628:
2598:
2571:
2547:
2514:
2481:
2448:
2411:
2387:
2352:
2312:
2279:
2246:
2209:
2185:
2161:
2137:
2109:
2085:
2040:
2001:
1959:
1920:
1870:
1846:
1826:
1806:
1786:
1757:
1734:
1707:
1680:
1657:
1633:
1599:
1557:
1535:
1516:
1494:
1467:
1440:
1420:
1400:
1346:
1326:
1294:
1274:
1246:
1220:
1200:
1171:
1145:
1125:
1089:
1066:
1046:
1022:
995:
964:
917:
893:
873:
819:
785:
757:
733:
690:
666:
638:
600:
571:
545:
473:
445:
412:
365:
332:
284:
260:
232:
208:
168:
95:
71:
48:
5579:
by an edge. If we use a strategy P for partitioning
6573:
6452:
6399:
6328:
6185:
5909:, Second Edition. MIT Press and McGraw-Hill, 2001.
6022:
5787:
5737:
5698:
5672:
5648:
5625:
5595:
5571:
5547:
5522:can be represented by a Cluster Partition Tree CPT
5514:
5444:
5402:
5369:
5322:
5246:
5191:
5124:
5082:
5038:
5014:
4990:
4963:
4931:
4892:
4872:
4844:
4805:
4780:
4756:
4724:
4700:
4677:
4657:
4633:
4609:
4585:
4561:
4538:
4511:
4487:
4463:
4439:
4415:
4391:
4367:
4340:
4316:
4292:
4256:
4240:Proof outline: We introduce a weight called extra(
4229:
4190:
4170:
4150:
4126:
4093:
4058:
4031:
4011:
3991:
3965:
3938:
3903:
3852:
3832:
3807:{\displaystyle a\in \partial {A}\cap \partial {B}}
3806:
3764:
3741:
3708:
3680:
3655:
3632:
3612:
3576:
3556:
3536:
3503:
3472:
3448:
3425:
3395:
3367:
3342:
3322:
3290:
3257:
3227:
3189:
3143:
3119:
3086:
3051:
3027:
2988:
2956:
2922:
2891:
2856:
2831:
2770:
2746:
2713:
2680:
2647:
2614:
2577:
2557:
2533:
2500:
2467:
2435:{\displaystyle {\mathcal {A}}\cup {\mathcal {B}}.}
2434:
2397:
2373:
2334:
2298:
2265:
2233:{\displaystyle {\mathcal {A}}\cup {\mathcal {B}}.}
2232:
2195:
2171:
2147:
2119:
2095:
2072:{\displaystyle ({\mathcal {A}},{\mathcal {B}}){:}}
2071:
2020:
1984:
1945:
1890:
1856:
1832:
1812:
1792:
1763:
1740:
1717:
1690:
1666:
1643:
1619:
1580:
1541:
1522:
1500:
1477:
1450:
1426:
1406:
1356:
1332:
1307:
1280:
1257:
1233:
1206:
1182:
1158:
1131:
1108:
1083:The top tree data structure can be initialized in
1072:
1052:
1032:
1005:
974:
942:
903:
879:
839:
805:
767:
743:
712:
676:
648:
613:
582:
555:
483:
455:
431:
375:
351:
314:and give methods to maintain it under the various
306:
270:
246:
218:
174:
106:
81:
54:
4974:Proof outline:We will maintain the length length(
840:{\displaystyle {\mathcal {A}}\cup {\mathcal {B}}}
806:{\displaystyle {\mathcal {A}}\cap {\mathcal {B}}}
527:Edge Clusters with two Boundary Nodes are called
503:A Cluster containing a single edge is called an
4300:Which is maintained appropriately ; split(
1901:fails if the vertices are from different trees.
115:
2782:is often required for queries without need to
2622:method which calls user method for updates of
6163:
5461:compression, but may be exponentially better.
5266:improves this to an amortized update time of
1914:are all carried out by a sequence of at most
278:the user may associate some meta information
8:
5323:{\displaystyle O(\log ^{2}n\log ^{2}\log n)}
1840:is nonempty it returns the new Root cluster
1488:. It returns a single top tree representing
27:based on a binary tree for unrooted dynamic
3094:User defined function is called to process
6170:
6156:
6148:
6110:
6039:
6005:
5987:
5986:
5984:
5764:
5763:
5761:
5714:
5713:
5711:
5690:
5689:
5687:
5662:
5641:
5614:
5613:
5611:
5587:
5586:
5584:
5563:
5562:
5560:
5533:
5532:
5527:
5506:
5505:
5503:
5427:
5415:
5391:
5390:
5382:
5352:
5340:
5299:
5283:
5271:
5221:
5204:
5174:
5162:
5101:
5100:
5098:
5059:
5058:
5056:
5030:
5029:
5027:
5006:
5005:
5003:
4982:
4981:
4979:
4944:
4908:
4907:
4905:
4885:
4865:
4821:
4820:
4818:
4798:
4772:
4771:
4769:
4737:
4716:
4715:
4713:
4690:
4670:
4649:
4648:
4646:
4625:
4624:
4622:
4601:
4600:
4598:
4577:
4576:
4574:
4553:
4552:
4550:
4527:
4526:
4524:
4503:
4502:
4500:
4479:
4478:
4476:
4455:
4454:
4452:
4431:
4430:
4428:
4407:
4406:
4404:
4383:
4382:
4380:
4356:
4355:
4353:
4332:
4331:
4329:
4308:
4307:
4305:
4278:
4277:
4269:
4248:
4247:
4245:
4206:
4205:
4203:
4183:
4163:
4143:
4112:
4111:
4106:
4071:
4047:
4046:
4044:
4024:
4004:
3978:
3957:
3956:
3954:
3916:
3880:
3879:
3877:
3845:
3819:
3799:
3788:
3777:
3756:
3755:
3753:
3730:
3729:
3727:
3700:
3699:
3697:
3672:
3671:
3669:
3648:
3643:Finding center of tree containing vertex
3625:
3605:
3569:
3549:
3525:
3524:
3516:
3496:
3485:
3464:
3463:
3461:
3438:
3418:
3387:
3386:
3384:
3359:
3358:
3356:
3335:
3315:
3279:
3278:
3270:
3249:
3248:
3246:
3220:
3211:
3210:
3205:
3182:
3173:
3172:
3167:
3135:
3134:
3132:
3108:
3107:
3099:
3064:
3043:
3042:
3040:
3020:
3011:
3010:
3005:
2977:
2976:
2968:
2934:
2909:
2904:
2869:
2848:
2847:
2845:
2824:
2807:
2762:
2761:
2759:
2735:
2734:
2726:
2702:
2701:
2693:
2669:
2668:
2660:
2636:
2635:
2627:
2603:
2602:
2597:
2570:
2549:
2548:
2546:
2522:
2521:
2513:
2489:
2488:
2480:
2456:
2455:
2447:
2423:
2422:
2413:
2412:
2410:
2389:
2388:
2386:
2366:
2357:
2356:
2351:
2320:
2319:
2311:
2287:
2286:
2278:
2254:
2253:
2245:
2221:
2220:
2211:
2210:
2208:
2187:
2186:
2184:
2163:
2162:
2160:
2139:
2138:
2136:
2111:
2110:
2108:
2087:
2086:
2084:
2064:
2055:
2054:
2045:
2044:
2039:
2009:
2008:
2000:
1961:
1960:
1958:
1922:
1921:
1919:
1874:
1869:
1848:
1847:
1845:
1825:
1805:
1785:
1756:
1733:
1709:
1708:
1706:
1682:
1681:
1679:
1656:
1635:
1634:
1632:
1600:
1598:
1561:
1556:
1534:
1515:
1493:
1469:
1468:
1466:
1442:
1441:
1439:
1419:
1399:
1348:
1347:
1345:
1325:
1296:
1295:
1293:
1273:
1250:
1245:
1222:
1221:
1219:
1199:
1175:
1170:
1147:
1146:
1144:
1124:
1091:
1090:
1088:
1065:
1045:
1024:
1023:
1021:
997:
996:
994:
966:
965:
963:
919:
918:
916:
895:
894:
892:
872:
864:The basic idea is to maintain a balanced
831:
830:
821:
820:
818:
797:
796:
787:
786:
784:
759:
758:
756:
735:
734:
732:
698:
697:
689:
668:
667:
665:
640:
639:
637:
602:
601:
599:
575:
570:
547:
546:
544:
475:
474:
472:
447:
446:
444:
420:
419:
411:
367:
366:
364:
340:
339:
331:
292:
291:
283:
262:
261:
259:
236:
231:
210:
209:
207:
167:
162:Up to a pair of vertices in the top tree
99:
94:
73:
72:
70:
47:
6023:{\displaystyle {\tilde {O}}(\log ^{2}n)}
5478:(typically with amortized time bounds),
3265:, the edge is searched only on the path
315:
194:is a connected subtree with at most two
119:
5922:
5885:. Section 2.3: Trees, pp. 308–423.
5877:, Third Edition. Addison-Wesley, 1997.
5498:Any partitioning of clusters of a tree
1911:
859:
5788:{\displaystyle {\mathcal {O}}(\log n)}
5738:{\displaystyle {\mathcal {O}}(\log n)}
5555:by replacing each cluster in the tree
5125:{\displaystyle {\mathcal {O}}(\log n)}
5083:{\displaystyle {\mathcal {O}}(\log n)}
4932:{\displaystyle {\mathcal {O}}(\log n)}
4845:{\displaystyle {\mathcal {O}}(\log n)}
4230:{\displaystyle {\mathcal {O}}(\log n)}
3904:{\displaystyle {\mathcal {O}}(\log n)}
3722:. The choose selects between children
3310:Finding i-th edge on longer path from
2923:{\displaystyle \partial {C}=\partial }
1985:{\displaystyle {\mathcal {O}}(\log n)}
1946:{\displaystyle {\mathcal {O}}(\log n)}
943:{\displaystyle {\mathcal {O}}(\log n)}
5247:{\displaystyle O(\log n/\log \log n)}
4324:) requires that, for each path child
4293:{\displaystyle \pi ({\mathcal {C}}).}
713:{\displaystyle \pi ({\mathcal {C}}).}
150:A vertex in a connected subtree is a
39:such as diameter, center and median.
7:
5022:is created by a join(Merge), length(
3864:Interesting Results and Applications
3537:{\displaystyle \pi ({\mathcal {A}})}
3413:we use global variable representing
3291:{\displaystyle \pi ({\mathcal {C}})}
629:
464:
432:{\displaystyle \pi ({\mathcal {C}})}
352:{\displaystyle \pi ({\mathcal {C}})}
199:
195:
140:
5445:{\displaystyle \Theta (\log ^{2}n)}
3228:{\displaystyle ({\mathcal {C}}){:}}
3190:{\displaystyle ({\mathcal {C}}){:}}
3028:{\displaystyle ({\mathcal {C}}){:}}
2589:Split is usually implemented using
2374:{\displaystyle ({\mathcal {C}}){:}}
1040:and the leaf nodes of the top tree
5664:
5643:
5417:
4860:The distance between two vertices
4264:) to be added to all the edges in
3983:
3796:
3785:
3600:is invoked. To maintain length in
3493:
2917:
2906:
2572:
2335:{\displaystyle I({\mathcal {B}}).}
1871:
1758:
1735:
1674:thereby turning it into two trees
1658:
1536:
1495:
1327:
1275:
1247:
1201:
1172:
1126:
1067:
1047:
874:
572:
307:{\displaystyle I({\mathcal {C}}),}
233:
169:
114:of at most two vertices called as
96:
49:
14:
5548:{\displaystyle ({\mathcal {T}}),}
5403:{\displaystyle I({\mathcal {C}})}
4127:{\displaystyle ({\mathcal {C}}).}
3814:the child with higher maxdistance
3504:{\displaystyle v\in \partial {A}}
3433:and global variable representing
3120:{\displaystyle I({\mathcal {C}})}
2989:{\displaystyle I({\mathcal {C}})}
2747:{\displaystyle I({\mathcal {C}})}
2714:{\displaystyle I({\mathcal {C}})}
2681:{\displaystyle I({\mathcal {B}})}
2648:{\displaystyle I({\mathcal {A}})}
2534:{\displaystyle I({\mathcal {C}})}
2501:{\displaystyle I({\mathcal {B}})}
2468:{\displaystyle I({\mathcal {A}})}
2299:{\displaystyle I({\mathcal {A}})}
2266:{\displaystyle I({\mathcal {C}})}
2021:{\displaystyle I({\mathcal {C}})}
1109:{\displaystyle {\mathcal {O}}(n)}
396:
5141:. In this problem, similarly to
4375:we set max_wt(A) := max_wt(
2615:{\displaystyle ({\mathcal {C}})}
2541:and than it deletes the cluster
1434:are vertices in different trees
359:contains at least one edge then
5873:The Art of Computer Programming
5626:{\displaystyle {\mathcal {T}}.}
5254:query time. Subsequent work by
4539:{\displaystyle {\mathcal {A}},}
4368:{\displaystyle {\mathcal {C}},}
4059:{\displaystyle {\mathcal {C}}=}
3742:{\displaystyle {\mathcal {A}},}
1891:{\displaystyle \partial {C}=S.}
1308:{\displaystyle {\mathcal {T}};}
1234:{\displaystyle {\mathcal {T}},}
1159:{\displaystyle {\mathcal {T}},}
614:{\displaystyle {\mathcal {C}}.}
439:does not contain any edge i.e.
6017:
5998:
5992:
5782:
5770:
5732:
5720:
5699:{\displaystyle {\mathcal {T}}}
5596:{\displaystyle {\mathcal {T}}}
5572:{\displaystyle {\mathcal {T}}}
5539:
5529:
5515:{\displaystyle {\mathcal {T}}}
5439:
5420:
5397:
5387:
5364:
5345:
5317:
5276:
5241:
5209:
5186:
5167:
5119:
5107:
5077:
5065:
5039:{\displaystyle {\mathcal {C}}}
5015:{\displaystyle {\mathcal {C}}}
4991:{\displaystyle {\mathcal {C}}}
4958:
4946:
4926:
4914:
4839:
4827:
4781:{\displaystyle {\mathcal {C}}}
4751:
4739:
4725:{\displaystyle {\mathcal {C}}}
4658:{\displaystyle {\mathcal {C}}}
4634:{\displaystyle {\mathcal {B}}}
4610:{\displaystyle {\mathcal {A}}}
4586:{\displaystyle {\mathcal {C}}}
4562:{\displaystyle {\mathcal {B}}}
4512:{\displaystyle {\mathcal {C}}}
4488:{\displaystyle {\mathcal {C}}}
4464:{\displaystyle {\mathcal {A}}}
4440:{\displaystyle {\mathcal {A}}}
4416:{\displaystyle {\mathcal {C}}}
4392:{\displaystyle {\mathcal {A}}}
4341:{\displaystyle {\mathcal {A}}}
4317:{\displaystyle {\mathcal {C}}}
4284:
4274:
4257:{\displaystyle {\mathcal {C}}}
4224:
4212:
4118:
4108:
4085:
4073:
3966:{\displaystyle {\mathcal {C}}}
3933:
3921:
3898:
3886:
3827:
3821:
3765:{\displaystyle {\mathcal {B}}}
3709:{\displaystyle {\mathcal {C}}}
3681:{\displaystyle {\mathcal {C}}}
3531:
3521:
3473:{\displaystyle {\mathcal {A}}}
3396:{\displaystyle {\mathcal {C}}}
3368:{\displaystyle {\mathcal {C}}}
3285:
3275:
3258:{\displaystyle {\mathcal {C}}}
3217:
3207:
3179:
3169:
3144:{\displaystyle {\mathcal {C}}}
3114:
3104:
3078:
3066:
3052:{\displaystyle {\mathcal {C}}}
3017:
3007:
2983:
2973:
2948:
2936:
2883:
2871:
2857:{\displaystyle {\mathcal {C}}}
2821:
2809:
2771:{\displaystyle {\mathcal {C}}}
2741:
2731:
2708:
2698:
2675:
2665:
2642:
2632:
2609:
2599:
2558:{\displaystyle {\mathcal {C}}}
2528:
2518:
2495:
2485:
2462:
2452:
2398:{\displaystyle {\mathcal {C}}}
2363:
2353:
2326:
2316:
2293:
2283:
2260:
2250:
2196:{\displaystyle {\mathcal {B}}}
2172:{\displaystyle {\mathcal {A}}}
2148:{\displaystyle {\mathcal {C}}}
2120:{\displaystyle {\mathcal {B}}}
2096:{\displaystyle {\mathcal {A}}}
2061:
2041:
2015:
2005:
1979:
1967:
1940:
1928:
1857:{\displaystyle {\mathcal {C}}}
1718:{\displaystyle {\mathcal {T}}}
1691:{\displaystyle {\mathcal {T}}}
1644:{\displaystyle {\mathcal {T}}}
1613:
1601:
1574:
1562:
1478:{\displaystyle {\mathcal {T}}}
1451:{\displaystyle {\mathcal {T}}}
1357:{\displaystyle {\mathcal {T}}}
1103:
1097:
1033:{\displaystyle {\mathcal {T}}}
1013:may have weight on its edges.
1006:{\displaystyle {\mathcal {T}}}
975:{\displaystyle {\mathcal {T}}}
937:
925:
904:{\displaystyle {\mathcal {T}}}
768:{\displaystyle {\mathcal {B}}}
744:{\displaystyle {\mathcal {A}}}
704:
694:
677:{\displaystyle {\mathcal {C}}}
649:{\displaystyle {\mathcal {C}}}
556:{\displaystyle {\mathcal {C}}}
484:{\displaystyle {\mathcal {C}}}
456:{\displaystyle {\mathcal {C}}}
426:
416:
376:{\displaystyle {\mathcal {C}}}
346:
336:
298:
288:
271:{\displaystyle {\mathcal {C}}}
219:{\displaystyle {\mathcal {C}}}
125:non-capital letters are nodes.
82:{\displaystyle {\mathcal {T}}}
1:
5494:Using Multilevel Partitioning
5480:Frederickson's Topology Trees
5370:{\displaystyle O(\log ^{5}n)}
5192:{\displaystyle O(\log ^{4}n)}
4158:to all edges on a given path
3241:vertices in the root cluster
3151:is deleted from the top tree.
1190:) is a binary tree such that
247:{\displaystyle \partial {C}.}
33:divide-and-conquer algorithms
3596:should be called before the
3306:Examples of non local search
1728:and returning two top trees
1581:{\displaystyle \cup {(v,w)}}
1258:{\displaystyle \partial {T}}
1183:{\displaystyle \partial {T}}
983:
583:{\displaystyle \partial {C}}
107:{\displaystyle \partial {T}}
3456:Choose selects the cluster
954:essentially represents the
6698:
5906:Introduction to Algorithms
1060:and each internal node of
158:External Boundary Vertices
116:External Boundary Vertices
6041:10.1137/1.9781611975031.3
5603:then the CPT would be CPT
3992:{\displaystyle -\infty .}
3939:{\displaystyle O(\log n)}
3236:routine, which organizes
2996:is computed from scratch.
2155:as the parent cluster of
6626:Left-child right-sibling
6121:10.1016/j.ic.2014.12.012
5875:: Fundamental Algorithms
5476:Sleator-Tarjan s-t trees
2832:{\displaystyle (v,w){:}}
860:link and cut operations.
6456:data partitioning trees
6414:C-trie (compressed ADT)
5845:10.1145/1103963.1103966
1620:{\displaystyle {(v,w)}}
1371:These trees are freely
1119:Therefore the top tree
6024:
5789:
5739:
5700:
5674:
5650:
5627:
5597:
5573:
5549:
5516:
5446:
5404:
5371:
5330:, also using top trees
5324:
5248:
5193:
5153:, de Lichtenberg, and
5126:
5084:
5040:
5016:
4992:
4965:
4933:
4894:
4874:
4846:
4807:
4782:
4758:
4726:
4702:
4679:
4659:
4635:
4611:
4593:) := max {max_wt(
4587:
4563:
4540:
4513:
4489:
4465:
4441:
4417:
4393:
4369:
4342:
4318:
4294:
4258:
4231:
4192:
4172:
4152:
4128:
4095:
4094:{\displaystyle (v,w),}
4060:
4033:
4013:
3993:
3967:
3940:
3905:
3854:
3834:
3808:
3766:
3743:
3710:
3682:
3657:
3634:
3614:
3578:
3558:
3538:
3505:
3474:
3450:
3427:
3397:
3369:
3344:
3324:
3292:
3259:
3229:
3191:
3145:
3121:
3088:
3087:{\displaystyle (v,w).}
3053:
3029:
2990:
2958:
2957:{\displaystyle (v,w).}
2924:
2893:
2892:{\displaystyle (v,w).}
2858:
2833:
2772:
2748:
2715:
2682:
2649:
2616:
2579:
2559:
2535:
2502:
2469:
2436:
2399:
2375:
2336:
2300:
2267:
2234:
2197:
2173:
2149:
2121:
2097:
2073:
2022:
1986:
1947:
1892:
1858:
1834:
1814:
1794:
1765:
1742:
1719:
1692:
1668:
1645:
1621:
1582:
1543:
1524:
1502:
1479:
1452:
1428:
1408:
1358:
1334:
1309:
1282:
1259:
1235:
1208:
1184:
1160:
1133:
1110:
1074:
1054:
1034:
1007:
976:
944:
905:
881:
841:
807:
769:
745:
714:
678:
650:
615:
584:
557:
485:
457:
433:
377:
353:
308:
272:
248:
220:
176:
126:
108:
83:
56:
6076:10.1145/502090.502095
6025:
5944:10.1145/502090.502095
5863:10.1145/502090.502095
5790:
5740:
5701:
5675:
5673:{\displaystyle \Re .}
5651:
5628:
5598:
5574:
5550:
5517:
5447:
5405:
5372:
5325:
5249:
5194:
5127:
5085:
5041:
5017:
4993:
4966:
4964:{\displaystyle (v,w)}
4939:time as length(Expose
4934:
4895:
4875:
4847:
4808:
4783:
4759:
4757:{\displaystyle (v,w)}
4727:
4703:
4680:
4660:
4636:
4612:
4588:
4564:
4541:
4514:
4490:
4466:
4442:
4418:
4394:
4370:
4343:
4319:
4295:
4259:
4232:
4193:
4173:
4153:
4129:
4096:
4061:
4034:
4014:
3994:
3968:
3941:
3906:
3855:
3835:
3809:
3767:
3744:
3711:
3683:
3658:
3635:
3615:
3579:
3559:
3539:
3506:
3475:
3451:
3428:
3398:
3370:
3345:
3325:
3293:
3260:
3230:
3192:
3146:
3127:and than the cluster
3122:
3089:
3054:
3030:
2991:
2959:
2925:
2894:
2859:
2834:
2773:
2749:
2716:
2683:
2650:
2617:
2580:
2560:
2536:
2503:
2470:
2437:
2400:
2376:
2337:
2301:
2268:
2235:
2198:
2174:
2150:
2122:
2098:
2074:
2023:
1987:
1948:
1893:
1859:
1835:
1815:
1795:
1766:
1743:
1720:
1693:
1669:
1667:{\displaystyle \Re ,}
1646:
1622:
1583:
1544:
1525:
1523:{\displaystyle \cup }
1503:
1480:
1453:
1429:
1409:
1359:
1335:
1310:
1283:
1260:
1236:
1209:
1185:
1161:
1134:
1111:
1075:
1055:
1035:
1008:
977:
958:of the original tree
956:recursive subdivision
945:
906:
882:
842:
808:
770:
746:
715:
684:and it is denoted by
679:
651:
628:The path between the
616:
585:
558:
486:
458:
434:
378:
354:
309:
273:
249:
221:
177:
123:
109:
84:
57:
6636:Log-structured merge
6179:Tree data structures
5983:
5893:Charles E. Leiserson
5820:Dynamic connectivity
5760:
5710:
5686:
5661:
5649:{\displaystyle \Re }
5640:
5610:
5583:
5559:
5526:
5502:
5472:Multilevel Partition
5414:
5381:
5339:
5270:
5203:
5161:
5143:dynamic connectivity
5097:
5055:
5026:
5002:
4978:
4943:
4904:
4884:
4864:
4817:
4797:
4768:
4736:
4712:
4689:
4669:
4645:
4621:
4597:
4573:
4549:
4523:
4499:
4475:
4451:
4427:
4403:
4379:
4352:
4328:
4304:
4268:
4244:
4202:
4182:
4162:
4142:
4105:
4070:
4043:
4023:
4003:
3977:
3973:) is initialised as
3953:
3915:
3876:
3844:
3818:
3776:
3752:
3726:
3696:
3668:
3647:
3624:
3604:
3568:
3548:
3515:
3484:
3460:
3437:
3417:
3383:
3355:
3334:
3314:
3269:
3245:
3204:
3166:
3131:
3098:
3063:
3059:is the edge cluster
3039:
3004:
2967:
2933:
2903:
2868:
2844:
2806:
2758:
2725:
2692:
2659:
2626:
2596:
2578:{\displaystyle \Re }
2569:
2545:
2512:
2479:
2446:
2409:
2405:is the root cluster
2385:
2350:
2310:
2277:
2244:
2207:
2183:
2159:
2135:
2107:
2083:
2038:
1999:
1957:
1918:
1868:
1844:
1824:
1804:
1784:
1764:{\displaystyle \Re }
1755:
1741:{\displaystyle \Re }
1732:
1705:
1678:
1655:
1631:
1597:
1555:
1542:{\displaystyle \Re }
1533:
1514:
1501:{\displaystyle \Re }
1492:
1465:
1438:
1418:
1398:
1344:
1333:{\displaystyle \Re }
1324:
1292:
1281:{\displaystyle \Re }
1272:
1244:
1218:
1207:{\displaystyle \Re }
1198:
1169:
1143:
1132:{\displaystyle \Re }
1123:
1087:
1073:{\displaystyle \Re }
1064:
1053:{\displaystyle \Re }
1044:
1020:
993:
989:In general the tree
962:
915:
891:
880:{\displaystyle \Re }
871:
817:
783:
755:
731:
688:
664:
636:
598:
569:
543:
471:
443:
410:
363:
330:
282:
258:
230:
206:
175:{\displaystyle \Re }
166:
93:
69:
55:{\displaystyle \Re }
46:
3833:{\displaystyle (a)}
3409:. To implement the
1906:Internal Operations
1593:: Removes the edge
316:internal operations
202:of a given cluster
6601:Fractal tree index
6196:associative arrays
6064:Journal of the ACM
6020:
5932:Journal of the ACM
5785:
5735:
5696:
5670:
5646:
5623:
5593:
5569:
5545:
5512:
5442:
5400:
5367:
5320:
5244:
5189:
5122:
5080:
5036:
5012:
4988:
4961:
4929:
4890:
4870:
4842:
4803:
4778:
4764:and return max_wt(
4754:
4722:
4701:{\displaystyle w,}
4698:
4675:
4655:
4631:
4607:
4583:
4559:
4536:
4509:
4485:
4461:
4437:
4413:
4389:
4365:
4338:
4314:
4290:
4254:
4227:
4188:
4168:
4148:
4124:
4091:
4056:
4029:
4009:
3989:
3963:
3936:
3901:
3850:
3830:
3804:
3762:
3739:
3706:
3678:
3653:
3630:
3610:
3574:
3554:
3534:
3501:
3470:
3449:{\displaystyle i.}
3446:
3423:
3393:
3365:
3340:
3320:
3288:
3255:
3225:
3187:
3141:
3117:
3084:
3049:
3025:
2986:
2954:
2920:
2889:
2854:
2840:Creates a cluster
2829:
2768:
2744:
2711:
2678:
2645:
2612:
2575:
2555:
2531:
2498:
2465:
2432:
2395:
2371:
2332:
2296:
2263:
2230:
2193:
2169:
2145:
2129:Mergeable Clusters
2117:
2093:
2069:
2018:
1982:
1943:
1888:
1854:
1830:
1810:
1790:
1761:
1738:
1715:
1688:
1664:
1641:
1617:
1578:
1539:
1520:
1498:
1475:
1448:
1424:
1404:
1383:Dynamic Operations
1354:
1330:
1305:
1278:
1255:
1231:
1204:
1180:
1156:
1129:
1106:
1070:
1050:
1030:
1003:
972:
940:
901:
877:
837:
803:
765:
741:
723:Mergeable Clusters
710:
674:
646:
611:
580:
553:
481:
453:
429:
373:
349:
304:
268:
254:With each cluster
244:
216:
172:
127:
104:
79:
62:is defined for an
52:
6669:
6668:
6030:Amortized Time",
5995:
5815:Dynamic algorithm
5149:separating them.
5139:edge connectivity
4893:{\displaystyle w}
4873:{\displaystyle v}
4806:{\displaystyle v}
4678:{\displaystyle v}
4569:), we set max_wt(
4191:{\displaystyle w}
4171:{\displaystyle v}
4151:{\displaystyle x}
4101:and report max_wt
4032:{\displaystyle w}
4012:{\displaystyle v}
3853:{\displaystyle I}
3718:with appropriate
3656:{\displaystyle v}
3633:{\displaystyle I}
3613:{\displaystyle I}
3577:{\displaystyle I}
3557:{\displaystyle i}
3426:{\displaystyle v}
3405:with appropriate
3350:could be done by
3343:{\displaystyle w}
3323:{\displaystyle v}
1833:{\displaystyle S}
1813:{\displaystyle S}
1793:{\displaystyle S}
1427:{\displaystyle w}
1407:{\displaystyle v}
1288:are the edges of
1214:are clusters of (
950:time) ; the
630:Boundary Vertices
529:Path Edge Cluster
523:Path Edge Cluster
517:Leaf Edge Cluster
511:Leaf Edge Cluster
200:Boundary Vertices
196:Boundary Vertices
6689:
6172:
6165:
6158:
6149:
6125:
6124:
6114:
6094:
6088:
6087:
6059:
6053:
6052:
6043:
6029:
6027:
6026:
6021:
6010:
6009:
5997:
5996:
5988:
5976:
5970:
5969:
5962:
5956:
5955:
5927:
5897:Ronald L. Rivest
5889:Thomas H. Cormen
5794:
5792:
5791:
5786:
5769:
5768:
5744:
5742:
5741:
5736:
5719:
5718:
5705:
5703:
5702:
5697:
5695:
5694:
5679:
5677:
5676:
5671:
5655:
5653:
5652:
5647:
5632:
5630:
5629:
5624:
5619:
5618:
5602:
5600:
5599:
5594:
5592:
5591:
5578:
5576:
5575:
5570:
5568:
5567:
5554:
5552:
5551:
5546:
5538:
5537:
5521:
5519:
5518:
5513:
5511:
5510:
5451:
5449:
5448:
5443:
5432:
5431:
5409:
5407:
5406:
5401:
5396:
5395:
5376:
5374:
5373:
5368:
5357:
5356:
5329:
5327:
5326:
5321:
5304:
5303:
5288:
5287:
5253:
5251:
5250:
5245:
5225:
5198:
5196:
5195:
5190:
5179:
5178:
5131:
5129:
5128:
5123:
5106:
5105:
5089:
5087:
5086:
5081:
5064:
5063:
5045:
5043:
5042:
5037:
5035:
5034:
5021:
5019:
5018:
5013:
5011:
5010:
4997:
4995:
4994:
4989:
4987:
4986:
4970:
4968:
4967:
4962:
4938:
4936:
4935:
4930:
4913:
4912:
4900:can be found in
4899:
4897:
4896:
4891:
4879:
4877:
4876:
4871:
4851:
4849:
4848:
4843:
4826:
4825:
4812:
4810:
4809:
4804:
4787:
4785:
4784:
4779:
4777:
4776:
4763:
4761:
4760:
4755:
4731:
4729:
4728:
4723:
4721:
4720:
4707:
4705:
4704:
4699:
4684:
4682:
4681:
4676:
4664:
4662:
4661:
4656:
4654:
4653:
4640:
4638:
4637:
4632:
4630:
4629:
4616:
4614:
4613:
4608:
4606:
4605:
4592:
4590:
4589:
4584:
4582:
4581:
4568:
4566:
4565:
4560:
4558:
4557:
4545:
4543:
4542:
4537:
4532:
4531:
4518:
4516:
4515:
4510:
4508:
4507:
4494:
4492:
4491:
4486:
4484:
4483:
4470:
4468:
4467:
4462:
4460:
4459:
4447:) := extra(
4446:
4444:
4443:
4438:
4436:
4435:
4422:
4420:
4419:
4414:
4412:
4411:
4398:
4396:
4395:
4390:
4388:
4387:
4374:
4372:
4371:
4366:
4361:
4360:
4347:
4345:
4344:
4339:
4337:
4336:
4323:
4321:
4320:
4315:
4313:
4312:
4299:
4297:
4296:
4291:
4283:
4282:
4263:
4261:
4260:
4255:
4253:
4252:
4236:
4234:
4233:
4228:
4211:
4210:
4197:
4195:
4194:
4189:
4177:
4175:
4174:
4169:
4157:
4155:
4154:
4149:
4133:
4131:
4130:
4125:
4117:
4116:
4100:
4098:
4097:
4092:
4065:
4063:
4062:
4057:
4052:
4051:
4038:
4036:
4035:
4030:
4018:
4016:
4015:
4010:
3998:
3996:
3995:
3990:
3972:
3970:
3969:
3964:
3962:
3961:
3945:
3943:
3942:
3937:
3910:
3908:
3907:
3902:
3885:
3884:
3859:
3857:
3856:
3851:
3839:
3837:
3836:
3831:
3813:
3811:
3810:
3805:
3803:
3792:
3771:
3769:
3768:
3763:
3761:
3760:
3748:
3746:
3745:
3740:
3735:
3734:
3715:
3713:
3712:
3707:
3705:
3704:
3687:
3685:
3684:
3679:
3677:
3676:
3662:
3660:
3659:
3654:
3639:
3637:
3636:
3631:
3619:
3617:
3616:
3611:
3583:
3581:
3580:
3575:
3563:
3561:
3560:
3555:
3543:
3541:
3540:
3535:
3530:
3529:
3510:
3508:
3507:
3502:
3500:
3479:
3477:
3476:
3471:
3469:
3468:
3455:
3453:
3452:
3447:
3432:
3430:
3429:
3424:
3402:
3400:
3399:
3394:
3392:
3391:
3374:
3372:
3371:
3366:
3364:
3363:
3349:
3347:
3346:
3341:
3329:
3327:
3326:
3321:
3297:
3295:
3294:
3289:
3284:
3283:
3264:
3262:
3261:
3256:
3254:
3253:
3234:
3232:
3231:
3226:
3224:
3216:
3215:
3196:
3194:
3193:
3188:
3186:
3178:
3177:
3160:User can define
3156:Non local search
3150:
3148:
3147:
3142:
3140:
3139:
3126:
3124:
3123:
3118:
3113:
3112:
3093:
3091:
3090:
3085:
3058:
3056:
3055:
3050:
3048:
3047:
3034:
3032:
3031:
3026:
3024:
3016:
3015:
2995:
2993:
2992:
2987:
2982:
2981:
2963:
2961:
2960:
2955:
2929:
2927:
2926:
2921:
2913:
2898:
2896:
2895:
2890:
2863:
2861:
2860:
2855:
2853:
2852:
2838:
2836:
2835:
2830:
2828:
2777:
2775:
2774:
2769:
2767:
2766:
2753:
2751:
2750:
2745:
2740:
2739:
2720:
2718:
2717:
2712:
2707:
2706:
2687:
2685:
2684:
2679:
2674:
2673:
2654:
2652:
2651:
2646:
2641:
2640:
2621:
2619:
2618:
2613:
2608:
2607:
2584:
2582:
2581:
2576:
2564:
2562:
2561:
2556:
2554:
2553:
2540:
2538:
2537:
2532:
2527:
2526:
2507:
2505:
2504:
2499:
2494:
2493:
2474:
2472:
2471:
2466:
2461:
2460:
2441:
2439:
2438:
2433:
2428:
2427:
2418:
2417:
2404:
2402:
2401:
2396:
2394:
2393:
2380:
2378:
2377:
2372:
2370:
2362:
2361:
2341:
2339:
2338:
2333:
2325:
2324:
2305:
2303:
2302:
2297:
2292:
2291:
2272:
2270:
2269:
2264:
2259:
2258:
2239:
2237:
2236:
2231:
2226:
2225:
2216:
2215:
2202:
2200:
2199:
2194:
2192:
2191:
2178:
2176:
2175:
2170:
2168:
2167:
2154:
2152:
2151:
2146:
2144:
2143:
2126:
2124:
2123:
2118:
2116:
2115:
2102:
2100:
2099:
2094:
2092:
2091:
2078:
2076:
2075:
2070:
2068:
2060:
2059:
2050:
2049:
2027:
2025:
2024:
2019:
2014:
2013:
1991:
1989:
1988:
1983:
1966:
1965:
1952:
1950:
1949:
1944:
1927:
1926:
1897:
1895:
1894:
1889:
1878:
1863:
1861:
1860:
1855:
1853:
1852:
1839:
1837:
1836:
1831:
1819:
1817:
1816:
1811:
1799:
1797:
1796:
1791:
1770:
1768:
1767:
1762:
1747:
1745:
1744:
1739:
1724:
1722:
1721:
1716:
1714:
1713:
1697:
1695:
1694:
1689:
1687:
1686:
1673:
1671:
1670:
1665:
1650:
1648:
1647:
1642:
1640:
1639:
1626:
1624:
1623:
1618:
1616:
1587:
1585:
1584:
1579:
1577:
1548:
1546:
1545:
1540:
1529:
1527:
1526:
1521:
1507:
1505:
1504:
1499:
1484:
1482:
1481:
1476:
1474:
1473:
1457:
1455:
1454:
1449:
1447:
1446:
1433:
1431:
1430:
1425:
1413:
1411:
1410:
1405:
1363:
1361:
1360:
1355:
1353:
1352:
1339:
1337:
1336:
1331:
1314:
1312:
1311:
1306:
1301:
1300:
1287:
1285:
1284:
1279:
1264:
1262:
1261:
1256:
1254:
1240:
1238:
1237:
1232:
1227:
1226:
1213:
1211:
1210:
1205:
1189:
1187:
1186:
1181:
1179:
1165:
1163:
1162:
1157:
1152:
1151:
1138:
1136:
1135:
1130:
1115:
1113:
1112:
1107:
1096:
1095:
1079:
1077:
1076:
1071:
1059:
1057:
1056:
1051:
1039:
1037:
1036:
1031:
1029:
1028:
1012:
1010:
1009:
1004:
1002:
1001:
981:
979:
978:
973:
971:
970:
949:
947:
946:
941:
924:
923:
910:
908:
907:
902:
900:
899:
886:
884:
883:
878:
846:
844:
843:
838:
836:
835:
826:
825:
812:
810:
809:
804:
802:
801:
792:
791:
774:
772:
771:
766:
764:
763:
750:
748:
747:
742:
740:
739:
719:
717:
716:
711:
703:
702:
683:
681:
680:
675:
673:
672:
655:
653:
652:
647:
645:
644:
620:
618:
617:
612:
607:
606:
589:
587:
586:
581:
579:
562:
560:
559:
554:
552:
551:
490:
488:
487:
482:
480:
479:
462:
460:
459:
454:
452:
451:
438:
436:
435:
430:
425:
424:
382:
380:
379:
374:
372:
371:
358:
356:
355:
350:
345:
344:
313:
311:
310:
305:
297:
296:
277:
275:
274:
269:
267:
266:
253:
251:
250:
245:
240:
225:
223:
222:
217:
215:
214:
181:
179:
178:
173:
113:
111:
110:
105:
103:
88:
86:
85:
80:
78:
77:
61:
59:
58:
53:
6697:
6696:
6692:
6691:
6690:
6688:
6687:
6686:
6672:
6671:
6670:
6665:
6569:
6448:
6395:
6324:
6320:Weight-balanced
6275:Order statistic
6189:
6181:
6176:
6134:
6129:
6128:
6096:
6095:
6091:
6061:
6060:
6056:
6001:
5981:
5980:
5978:
5977:
5973:
5964:
5963:
5959:
5929:
5928:
5924:
5828:
5810:Euler tour tree
5801:
5758:
5757:
5708:
5707:
5684:
5683:
5659:
5658:
5638:
5637:
5608:
5607:
5606:
5581:
5580:
5557:
5556:
5524:
5523:
5500:
5499:
5496:
5468:
5423:
5412:
5411:
5379:
5378:
5348:
5337:
5336:
5295:
5279:
5268:
5267:
5201:
5200:
5170:
5159:
5158:
5095:
5094:
5053:
5052:
5024:
5023:
5000:
4999:
4976:
4975:
4941:
4940:
4902:
4901:
4882:
4881:
4862:
4861:
4815:
4814:
4795:
4794:
4766:
4765:
4734:
4733:
4732: := Expose
4710:
4709:
4687:
4686:
4667:
4666:
4643:
4642:
4619:
4618:
4595:
4594:
4571:
4570:
4547:
4546:
4521:
4520:
4497:
4496:
4473:
4472:
4449:
4448:
4425:
4424:
4401:
4400:
4377:
4376:
4350:
4349:
4326:
4325:
4302:
4301:
4266:
4265:
4242:
4241:
4200:
4199:
4180:
4179:
4160:
4159:
4140:
4139:
4103:
4102:
4068:
4067:
4041:
4040:
4021:
4020:
4001:
4000:
3975:
3974:
3951:
3950:
3913:
3912:
3874:
3873:
3866:
3842:
3841:
3816:
3815:
3774:
3773:
3750:
3749:
3724:
3723:
3694:
3693:
3666:
3665:
3645:
3644:
3622:
3621:
3602:
3601:
3566:
3565:
3546:
3545:
3513:
3512:
3482:
3481:
3458:
3457:
3435:
3434:
3415:
3414:
3381:
3380:
3353:
3352:
3332:
3331:
3312:
3311:
3308:
3267:
3266:
3243:
3242:
3202:
3201:
3164:
3163:
3158:
3129:
3128:
3096:
3095:
3061:
3060:
3037:
3036:
3002:
3001:
2965:
2964:
2931:
2930:
2901:
2900:
2866:
2865:
2842:
2841:
2804:
2803:
2756:
2755:
2723:
2722:
2690:
2689:
2657:
2656:
2624:
2623:
2594:
2593:
2567:
2566:
2543:
2542:
2510:
2509:
2477:
2476:
2444:
2443:
2407:
2406:
2383:
2382:
2348:
2347:
2308:
2307:
2275:
2274:
2242:
2241:
2205:
2204:
2181:
2180:
2157:
2156:
2133:
2132:
2105:
2104:
2081:
2080:
2036:
2035:
1997:
1996:
1955:
1954:
1916:
1915:
1908:
1866:
1865:
1842:
1841:
1822:
1821:
1802:
1801:
1782:
1781:
1773:
1753:
1752:
1750:
1730:
1729:
1727:
1703:
1702:
1700:
1676:
1675:
1653:
1652:
1629:
1628:
1595:
1594:
1553:
1552:
1551:
1531:
1530:
1512:
1511:
1510:
1490:
1489:
1487:
1463:
1462:
1460:
1436:
1435:
1416:
1415:
1396:
1395:
1385:
1342:
1341:
1322:
1321:
1290:
1289:
1270:
1269:
1242:
1241:
1216:
1215:
1196:
1195:
1167:
1166:
1141:
1140:
1121:
1120:
1085:
1084:
1062:
1061:
1042:
1041:
1018:
1017:
991:
990:
960:
959:
913:
912:
889:
888:
869:
868:
853:
815:
814:
781:
780:
753:
752:
729:
728:
725:
686:
685:
662:
661:
634:
633:
626:
596:
595:
567:
566:
541:
540:
537:
525:
513:
501:
469:
468:
465:Boundary Vertex
441:
440:
408:
407:
404:
393:
361:
360:
328:
327:
324:
280:
279:
256:
255:
228:
227:
204:
203:
188:
164:
163:
160:
152:Boundary Vertex
148:
146:Boundary Vertex
141:Boundary Vertex
137:
132:
91:
90:
67:
66:
64:underlying tree
44:
43:
17:
12:
11:
5:
6695:
6693:
6685:
6684:
6674:
6673:
6667:
6666:
6664:
6663:
6658:
6653:
6648:
6643:
6638:
6633:
6628:
6623:
6618:
6613:
6608:
6603:
6598:
6593:
6588:
6583:
6577:
6575:
6571:
6570:
6568:
6567:
6562:
6557:
6552:
6547:
6542:
6537:
6532:
6527:
6522:
6517:
6512:
6507:
6502:
6485:
6480:
6475:
6470:
6465:
6459:
6457:
6450:
6449:
6447:
6446:
6441:
6436:
6434:Ternary search
6431:
6426:
6421:
6416:
6411:
6405:
6403:
6397:
6396:
6394:
6393:
6388:
6383:
6378:
6373:
6368:
6363:
6358:
6350:
6345:
6340:
6334:
6332:
6326:
6325:
6323:
6322:
6317:
6312:
6307:
6302:
6297:
6292:
6282:
6277:
6272:
6267:
6262:
6257:
6247:
6242:
6237:
6232:
6227:
6222:
6217:
6212:
6207:
6201:
6199:
6183:
6182:
6177:
6175:
6174:
6167:
6160:
6152:
6146:
6145:
6140:
6133:
6132:External links
6130:
6127:
6126:
6089:
6054:
6019:
6016:
6013:
6008:
6004:
6000:
5994:
5991:
5971:
5957:
5921:
5920:
5919:
5918:
5901:Clifford Stein
5886:
5865:
5847:
5827:
5824:
5823:
5822:
5817:
5812:
5807:
5800:
5797:
5784:
5781:
5778:
5775:
5772:
5767:
5754:
5753:
5750:
5734:
5731:
5728:
5725:
5722:
5717:
5693:
5669:
5666:
5645:
5622:
5617:
5604:
5590:
5566:
5544:
5541:
5536:
5531:
5509:
5495:
5492:
5467:
5466:Implementation
5464:
5463:
5462:
5454:
5453:
5441:
5438:
5435:
5430:
5426:
5422:
5419:
5399:
5394:
5389:
5386:
5366:
5363:
5360:
5355:
5351:
5347:
5344:
5332:
5331:
5319:
5316:
5313:
5310:
5307:
5302:
5298:
5294:
5291:
5286:
5282:
5278:
5275:
5243:
5240:
5237:
5234:
5231:
5228:
5224:
5220:
5217:
5214:
5211:
5208:
5188:
5185:
5182:
5177:
5173:
5169:
5166:
5134:
5133:
5121:
5118:
5115:
5112:
5109:
5104:
5091:
5079:
5076:
5073:
5070:
5067:
5062:
5049:
5048:
5047:
5033:
5009:
4985:
4960:
4957:
4954:
4951:
4948:
4928:
4925:
4922:
4919:
4916:
4911:
4889:
4869:
4858:
4857:
4856:
4841:
4838:
4835:
4832:
4829:
4824:
4802:
4791:
4790:
4789:
4775:
4753:
4750:
4747:
4744:
4741:
4719:
4697:
4694:
4674:
4652:
4628:
4604:
4580:
4556:
4535:
4530:
4519: := join(
4506:
4482:
4458:
4434:
4410:
4386:
4364:
4359:
4335:
4311:
4289:
4286:
4281:
4276:
4273:
4251:
4226:
4223:
4220:
4217:
4214:
4209:
4187:
4167:
4147:
4136:
4135:
4134:
4123:
4120:
4115:
4110:
4090:
4087:
4084:
4081:
4078:
4075:
4055:
4050:
4028:
4008:
3988:
3985:
3982:
3960:
3935:
3932:
3929:
3926:
3923:
3920:
3900:
3897:
3894:
3891:
3888:
3883:
3865:
3862:
3849:
3829:
3826:
3823:
3802:
3798:
3795:
3791:
3787:
3784:
3781:
3759:
3738:
3733:
3703:
3675:
3652:
3629:
3609:
3573:
3553:
3533:
3528:
3523:
3520:
3511:iff length of
3499:
3495:
3492:
3489:
3467:
3445:
3442:
3422:
3390:
3375:=Expose({v,w})
3362:
3339:
3319:
3307:
3304:
3287:
3282:
3277:
3274:
3252:
3223:
3219:
3214:
3209:
3185:
3181:
3176:
3171:
3157:
3154:
3153:
3152:
3138:
3116:
3111:
3106:
3103:
3083:
3080:
3077:
3074:
3071:
3068:
3046:
3023:
3019:
3014:
3009:
2997:
2985:
2980:
2975:
2972:
2953:
2950:
2947:
2944:
2941:
2938:
2919:
2916:
2912:
2908:
2888:
2885:
2882:
2879:
2876:
2873:
2851:
2827:
2823:
2820:
2817:
2814:
2811:
2765:
2743:
2738:
2733:
2730:
2710:
2705:
2700:
2697:
2677:
2672:
2667:
2664:
2644:
2639:
2634:
2631:
2611:
2606:
2601:
2587:
2586:
2574:
2552:
2530:
2525:
2520:
2517:
2497:
2492:
2487:
2484:
2464:
2459:
2454:
2451:
2431:
2426:
2421:
2416:
2392:
2369:
2365:
2360:
2355:
2342:
2331:
2328:
2323:
2318:
2315:
2295:
2290:
2285:
2282:
2262:
2257:
2252:
2249:
2229:
2224:
2219:
2214:
2190:
2166:
2142:
2114:
2090:
2067:
2063:
2058:
2053:
2048:
2043:
2017:
2012:
2007:
2004:
1981:
1978:
1975:
1972:
1969:
1964:
1942:
1939:
1936:
1933:
1930:
1925:
1912:Forest updates
1907:
1904:
1903:
1902:
1887:
1884:
1881:
1877:
1873:
1851:
1829:
1809:
1789:
1775:
1771:
1760:
1748:
1737:
1725:
1712:
1698:
1685:
1663:
1660:
1651:with top tree
1638:
1615:
1612:
1609:
1606:
1603:
1588:
1576:
1573:
1570:
1567:
1564:
1560:
1549:
1538:
1519:
1508:
1497:
1485:
1472:
1458:
1445:
1423:
1403:
1384:
1381:
1366:
1365:
1351:
1329:
1318:
1315:
1304:
1299:
1277:
1268:The leaves of
1266:
1253:
1249:
1230:
1225:
1203:
1178:
1174:
1155:
1150:
1128:
1105:
1102:
1099:
1094:
1069:
1049:
1027:
1000:
969:
939:
936:
933:
930:
927:
922:
898:
876:
852:
849:
847:is a Cluster.
834:
829:
824:
800:
795:
790:
762:
738:
724:
721:
709:
706:
701:
696:
693:
671:
656:is called the
643:
625:
622:
610:
605:
578:
574:
550:
536:
533:
524:
521:
512:
509:
500:
497:
478:
450:
428:
423:
418:
415:
403:
400:
392:
389:
370:
348:
343:
338:
335:
323:
320:
303:
300:
295:
290:
287:
265:
243:
239:
235:
226:is denoted as
213:
187:
184:
171:
159:
156:
147:
144:
136:
133:
131:
128:
102:
98:
76:
51:
25:data structure
16:Data structure
15:
13:
10:
9:
6:
4:
3:
2:
6694:
6683:
6680:
6679:
6677:
6662:
6659:
6657:
6654:
6652:
6649:
6647:
6644:
6642:
6639:
6637:
6634:
6632:
6629:
6627:
6624:
6622:
6619:
6617:
6614:
6612:
6611:Hash calendar
6609:
6607:
6604:
6602:
6599:
6597:
6594:
6592:
6589:
6587:
6584:
6582:
6579:
6578:
6576:
6572:
6566:
6563:
6561:
6558:
6556:
6553:
6551:
6548:
6546:
6543:
6541:
6538:
6536:
6533:
6531:
6528:
6526:
6523:
6521:
6518:
6516:
6513:
6511:
6508:
6506:
6503:
6500:
6498:
6492:
6490:
6486:
6484:
6481:
6479:
6476:
6474:
6471:
6469:
6466:
6464:
6461:
6460:
6458:
6455:
6451:
6445:
6442:
6440:
6437:
6435:
6432:
6430:
6427:
6425:
6422:
6420:
6417:
6415:
6412:
6410:
6407:
6406:
6404:
6402:
6398:
6392:
6389:
6387:
6386:van Emde Boas
6384:
6382:
6379:
6377:
6376:Skew binomial
6374:
6372:
6369:
6367:
6364:
6362:
6359:
6357:
6355:
6351:
6349:
6346:
6344:
6341:
6339:
6336:
6335:
6333:
6331:
6327:
6321:
6318:
6316:
6313:
6311:
6308:
6306:
6303:
6301:
6298:
6296:
6293:
6291:
6287:
6283:
6281:
6278:
6276:
6273:
6271:
6268:
6266:
6263:
6261:
6258:
6256:
6255:Binary search
6252:
6248:
6246:
6243:
6241:
6238:
6236:
6233:
6231:
6228:
6226:
6223:
6221:
6218:
6216:
6213:
6211:
6208:
6206:
6203:
6202:
6200:
6197:
6193:
6188:
6184:
6180:
6173:
6168:
6166:
6161:
6159:
6154:
6153:
6150:
6144:
6141:
6139:
6136:
6135:
6131:
6122:
6118:
6113:
6108:
6104:
6100:
6093:
6090:
6085:
6081:
6077:
6073:
6069:
6065:
6058:
6055:
6051:
6047:
6042:
6037:
6033:
6014:
6011:
6006:
6002:
5989:
5975:
5972:
5968:
5961:
5958:
5953:
5949:
5945:
5941:
5937:
5933:
5926:
5923:
5916:
5915:0-262-03293-7
5912:
5908:
5907:
5902:
5898:
5894:
5890:
5887:
5884:
5883:0-201-89683-4
5880:
5876:
5874:
5869:
5866:
5864:
5860:
5856:
5852:
5851:Mikkel Thorup
5848:
5846:
5842:
5838:
5834:
5833:Mikkel Thorup
5830:
5829:
5825:
5821:
5818:
5816:
5813:
5811:
5808:
5806:
5805:Link/cut tree
5803:
5802:
5798:
5796:
5779:
5776:
5773:
5751:
5748:
5747:
5746:
5729:
5726:
5723:
5680:
5667:
5634:
5620:
5542:
5493:
5491:
5489:
5483:
5481:
5477:
5473:
5465:
5460:
5456:
5455:
5436:
5433:
5428:
5424:
5384:
5361:
5358:
5353:
5349:
5342:
5334:
5333:
5314:
5311:
5308:
5305:
5300:
5296:
5292:
5289:
5284:
5280:
5273:
5265:
5261:
5257:
5238:
5235:
5232:
5229:
5226:
5222:
5218:
5215:
5212:
5206:
5183:
5180:
5175:
5171:
5164:
5156:
5152:
5148:
5144:
5140:
5136:
5135:
5116:
5113:
5110:
5092:
5074:
5071:
5068:
5050:
4973:
4972:
4955:
4952:
4949:
4923:
4920:
4917:
4887:
4867:
4859:
4854:
4853:
4836:
4833:
4830:
4800:
4792:
4748:
4745:
4742:
4695:
4692:
4672:
4641:)} and extra(
4533:
4362:
4287:
4271:
4239:
4238:
4221:
4218:
4215:
4185:
4165:
4145:
4137:
4121:
4088:
4082:
4079:
4076:
4053:
4026:
4006:
3986:
3980:
3948:
3947:
3930:
3927:
3924:
3918:
3895:
3892:
3889:
3871:
3870:
3869:
3863:
3861:
3847:
3824:
3800:
3793:
3789:
3782:
3779:
3736:
3721:
3717:
3689:
3650:
3641:
3627:
3607:
3599:
3595:
3591:
3585:
3571:
3551:
3518:
3497:
3490:
3487:
3443:
3440:
3420:
3412:
3408:
3404:
3376:
3337:
3317:
3305:
3303:
3301:
3272:
3239:
3235:
3221:
3197:
3183:
3155:
3101:
3081:
3075:
3072:
3069:
3035:
3021:
2998:
2970:
2951:
2945:
2942:
2939:
2914:
2910:
2886:
2880:
2877:
2874:
2864:for the edge
2839:
2825:
2818:
2815:
2812:
2800:
2799:
2798:
2795:
2793:
2789:
2785:
2781:
2728:
2695:
2662:
2629:
2592:
2515:
2482:
2449:
2429:
2419:
2367:
2346:
2343:
2329:
2313:
2280:
2247:
2227:
2217:
2131:, it returns
2130:
2065:
2051:
2034:
2031:
2030:
2029:
2002:
1993:
1976:
1973:
1970:
1937:
1934:
1931:
1913:
1905:
1900:
1899:Expose({v,w})
1885:
1882:
1879:
1875:
1827:
1807:
1787:
1779:
1776:
1661:
1610:
1607:
1604:
1592:
1589:
1571:
1568:
1565:
1558:
1517:
1421:
1401:
1393:
1390:
1389:
1388:
1382:
1380:
1378:
1374:
1369:
1319:
1316:
1302:
1267:
1251:
1228:
1194:The nodes of
1193:
1192:
1191:
1176:
1153:
1117:
1100:
1081:
1014:
987:
985:
957:
953:
934:
931:
928:
867:
862:
861:
857:
850:
848:
827:
793:
778:
727:Two Clusters
722:
720:
707:
691:
659:
631:
623:
621:
608:
593:
592:Internal Node
590:is called an
576:
565:
535:Internal Node
534:
532:
530:
522:
520:
518:
510:
508:
506:
498:
496:
494:
466:
463:has only one
413:
401:
399:
398:
391:Point Cluster
390:
388:
386:
333:
321:
319:
317:
301:
285:
241:
237:
201:
198:. The set of
197:
193:
185:
183:
157:
155:
153:
145:
143:
142:
135:Boundary Node
134:
129:
122:
118:
117:
100:
65:
40:
38:
34:
30:
26:
22:
6682:Binary trees
6660:
6496:
6488:
6353:
6286:Left-leaning
6192:dynamic sets
6187:Search trees
6102:
6098:
6092:
6067:
6063:
6057:
6031:
5974:
5966:
5960:
5935:
5931:
5925:
5904:
5871:
5868:Donald Knuth
5854:
5836:
5755:
5681:
5635:
5497:
5484:
5471:
5469:
4423:) and extra(
3867:
3719:
3691:
3690:followed by
3688:=Expose({v})
3664:
3642:
3597:
3593:
3589:
3586:
3544:is at least
3410:
3406:
3378:
3377:followed by
3351:
3309:
3299:
3237:
3199:
3161:
3159:
2999:
2801:
2796:
2791:
2787:
2783:
2779:
2721:and updates
2590:
2588:
2344:
2128:
2032:
1994:
1909:
1898:
1777:
1627:from a tree
1590:
1391:
1386:
1376:
1370:
1367:
1340:is the tree
1118:
1082:
1015:
988:
951:
863:
855:
854:
851:Introduction
776:
726:
658:cluster path
657:
627:
624:Cluster Path
591:
563:
538:
528:
526:
516:
514:
505:Edge Cluster
504:
502:
499:Edge Cluster
493:Leaf Cluster
492:
491:is called a
405:
402:Leaf Cluster
397:Leaf Cluster
394:
385:Path Cluster
384:
383:is called a
325:
322:Path Cluster
191:
189:
161:
151:
149:
138:
63:
41:
20:
18:
6586:Exponential
6574:Other trees
6105:: 166–177.
6099:Inf. Comput
5488:persistence
4039:then we do
3302:operation.
2442:It updates
1392:Link(v, w):
1373:augmentable
866:Binary tree
42:A top tree
6530:Priority R
6280:Palindrome
6070:(4): 723.
5938:(4): 723.
5826:References
4617:), max_wt(
4471:) + extra(
4399:) + extra(
911:( i.e. in
539:A node in
89:and a set
6616:iDistance
6495:implicit
6483:Hilbert R
6478:Cartesian
6361:Fibonacci
6295:Scapegoat
6290:Red–black
6112:1304.5702
6012:
5993:~
5777:
5727:
5665:ℜ
5644:ℜ
5434:
5418:Θ
5359:
5312:
5306:
5290:
5260:Rotenberg
5236:
5230:
5216:
5181:
5114:
5072:
4921:
4834:
4272:π
4219:
3984:∞
3981:−
3928:
3893:
3797:∂
3794:∩
3786:∂
3783:∈
3640:as well.
3519:π
3494:∂
3491:∈
3273:π
3000:Eradicate
2918:∂
2907:∂
2573:ℜ
2420:∪
2240:Computes
2218:∪
1974:
1935:
1872:∂
1778:Expose(S)
1759:ℜ
1736:ℜ
1659:ℜ
1591:Cut(v, w)
1559:∪
1537:ℜ
1518:∪
1496:ℜ
1377:Black Box
1328:ℜ
1276:ℜ
1248:∂
1202:ℜ
1173:∂
1127:ℜ
1068:ℜ
1048:ℜ
932:
875:ℜ
856:Top trees
828:∪
794:∩
777:Mergeable
692:π
573:∂
414:π
334:π
234:∂
170:ℜ
97:∂
50:ℜ
6676:Category
6631:Link/cut
6343:Binomial
6270:Interval
6050:33964042
5799:See also
1320:Root of
984:clusters
952:top tree
130:Glossary
21:top tree
6591:Fenwick
6555:Segment
6454:Spatial
6371:Pairing
6366:Leftist
6288:)
6260:Dancing
6253:)
6251:Optimal
6084:7273552
5952:7273552
4708:we set
4495:). For
3692:Search(
3379:Search(
192:cluster
186:Cluster
6641:Merkle
6606:Fusion
6596:Finger
6520:Octree
6510:Metric
6444:Y-fast
6439:X-fast
6429:Suffix
6348:Brodal
6338:Binary
6082:
6048:
5950:
5913:
5899:, and
5881:
5795:time.
5452:space.
5264:Thorup
5262:, and
5199:, and
5155:Thorup
5147:bridge
4852:time.
4237:time.
4066:Expose
3946:time.
3720:Choose
3598:Choose
3411:Choose
3407:Choose
3300:Choose
3238:Choose
3200:Search
3162:Choose
2802:Create
2688:using
2508:using
2273:using
1394:Where
1139:over (
1116:time.
6651:Range
6621:K-ary
6581:Cover
6424:Radix
6409:Ctrie
6401:Tries
6330:Heaps
6310:Treap
6300:Splay
6265:HTree
6220:(a,b)
6210:2–3–4
6107:arXiv
6080:S2CID
6046:S2CID
5948:S2CID
5410:uses
5132:time.
5090:time.
4685:· · ·
4178:· · ·
3772:with
3594:Clean
3590:Clean
3480:with
2899:Sets
2792:Split
2788:Merge
2784:Split
2780:Clean
2591:Clean
2565:from
2381:Here
2345:Split
2079:Here
2033:Merge
1864:with
982:into
467:then
29:trees
23:is a
6656:SPQR
6535:Quad
6463:Ball
6419:Hash
6391:Weak
6381:Skew
6356:-ary
5911:ISBN
5879:ISBN
5256:Holm
5151:Holm
4880:and
4019:and
2790:and
2655:and
2475:and
2306:and
2179:and
2127:are
2103:and
1995:The
1910:The
1751:and
1701:and
1461:and
1414:and
775:are
751:and
395:See
139:See
37:tree
6661:Top
6515:MVP
6473:BSP
6225:AVL
6205:2–3
6117:doi
6103:243
6072:doi
6036:doi
6003:log
5940:doi
5859:doi
5841:doi
5774:log
5724:log
5459:DAG
5425:log
5350:log
5309:log
5297:log
5281:log
5233:log
5227:log
5213:log
5172:log
5111:log
5069:log
4971:).
4918:log
4831:log
4813:in
4348:of
4216:log
4198:in
3925:log
3890:log
3330:to
1971:log
1932:log
929:log
779:if
660:of
632:of
594:of
406:If
326:If
6678::
6646:PQ
6560:VP
6550:R*
6545:R+
6525:PH
6499:-d
6491:-d
6468:BK
6315:UB
6240:B*
6235:B+
6215:AA
6115:.
6101:.
6078:.
6068:48
6066:.
6044:,
6034:,
5946:.
5936:48
5934:.
5903:.
5895:,
5891:,
5870:.
5853:,
5835:,
5258:,
4788:).
3584:.
2794:.
1379:.
1265:);
986:.
531:.
519:.
507:.
495:.
387:.
318:.
190:A
19:A
6565:X
6540:R
6505:M
6501:)
6497:k
6493:(
6489:k
6354:d
6305:T
6284:(
6249:(
6245:B
6230:B
6198:)
6194:/
6190:(
6171:e
6164:t
6157:v
6123:.
6119::
6109::
6086:.
6074::
6038::
6018:)
6015:n
6007:2
5999:(
5990:O
5954:.
5942::
5861::
5843::
5783:)
5780:n
5771:(
5766:O
5733:)
5730:n
5721:(
5716:O
5692:T
5668:.
5621:.
5616:T
5605:P
5589:T
5565:T
5543:,
5540:)
5535:T
5530:(
5508:T
5440:)
5437:n
5429:2
5421:(
5398:)
5393:C
5388:(
5385:I
5365:)
5362:n
5354:5
5346:(
5343:O
5318:)
5315:n
5301:2
5293:n
5285:2
5277:(
5274:O
5242:)
5239:n
5223:/
5219:n
5210:(
5207:O
5187:)
5184:n
5176:4
5168:(
5165:O
5120:)
5117:n
5108:(
5103:O
5078:)
5075:n
5066:(
5061:O
5032:C
5008:C
4984:C
4959:)
4956:w
4953:,
4950:v
4947:(
4927:)
4924:n
4915:(
4910:O
4888:w
4868:v
4840:)
4837:n
4828:(
4823:O
4801:v
4774:C
4752:)
4749:w
4746:,
4743:v
4740:(
4718:C
4696:,
4693:w
4673:v
4651:C
4627:B
4603:A
4579:C
4555:B
4534:,
4529:A
4505:C
4481:C
4457:A
4433:A
4409:C
4385:A
4363:,
4358:C
4334:A
4310:C
4288:.
4285:)
4280:C
4275:(
4250:C
4225:)
4222:n
4213:(
4208:O
4186:w
4166:v
4146:x
4122:.
4119:)
4114:C
4109:(
4089:,
4086:)
4083:w
4080:,
4077:v
4074:(
4054:=
4049:C
4027:w
4007:v
3987:.
3959:C
3934:)
3931:n
3922:(
3919:O
3899:)
3896:n
3887:(
3882:O
3848:I
3828:)
3825:a
3822:(
3801:B
3790:A
3780:a
3758:B
3737:,
3732:A
3716:)
3702:C
3674:C
3651:v
3628:I
3608:I
3572:I
3552:i
3532:)
3527:A
3522:(
3498:A
3488:v
3466:A
3444:.
3441:i
3421:v
3403:)
3389:C
3361:C
3338:w
3318:v
3286:)
3281:C
3276:(
3251:C
3222::
3218:)
3213:C
3208:(
3184::
3180:)
3175:C
3170:(
3137:C
3115:)
3110:C
3105:(
3102:I
3082:.
3079:)
3076:w
3073:,
3070:v
3067:(
3045:C
3022::
3018:)
3013:C
3008:(
2984:)
2979:C
2974:(
2971:I
2952:.
2949:)
2946:w
2943:,
2940:v
2937:(
2915:=
2911:C
2887:.
2884:)
2881:w
2878:,
2875:v
2872:(
2850:C
2826::
2822:)
2819:w
2816:,
2813:v
2810:(
2764:C
2742:)
2737:C
2732:(
2729:I
2709:)
2704:C
2699:(
2696:I
2676:)
2671:B
2666:(
2663:I
2643:)
2638:A
2633:(
2630:I
2610:)
2605:C
2600:(
2585:.
2551:C
2529:)
2524:C
2519:(
2516:I
2496:)
2491:B
2486:(
2483:I
2463:)
2458:A
2453:(
2450:I
2430:.
2425:B
2415:A
2391:C
2368::
2364:)
2359:C
2354:(
2330:.
2327:)
2322:B
2317:(
2314:I
2294:)
2289:A
2284:(
2281:I
2261:)
2256:C
2251:(
2248:I
2228:.
2223:B
2213:A
2189:B
2165:A
2141:C
2113:B
2089:A
2066::
2062:)
2057:B
2052:,
2047:A
2042:(
2016:)
2011:C
2006:(
2003:I
1980:)
1977:n
1968:(
1963:O
1941:)
1938:n
1929:(
1924:O
1886:.
1883:S
1880:=
1876:C
1850:C
1828:S
1808:S
1788:S
1774:.
1772:w
1749:v
1726:w
1711:T
1699:v
1684:T
1662:,
1637:T
1614:)
1611:w
1608:,
1605:v
1602:(
1575:)
1572:w
1569:,
1566:v
1563:(
1550:w
1509:v
1486:2
1471:T
1459:1
1444:T
1422:w
1402:v
1350:T
1303:;
1298:T
1252:T
1229:,
1224:T
1177:T
1154:,
1149:T
1104:)
1101:n
1098:(
1093:O
1026:T
999:T
968:T
938:)
935:n
926:(
921:O
897:T
833:B
823:A
799:B
789:A
761:B
737:A
708:.
705:)
700:C
695:(
670:C
642:C
609:.
604:C
577:C
564:\
549:C
477:C
449:C
427:)
422:C
417:(
369:C
347:)
342:C
337:(
302:,
299:)
294:C
289:(
286:I
264:C
242:.
238:C
212:C
101:T
75:T
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
