Content deleted Content added
AmirOnWiki (talk | contribs) |
AmirOnWiki (talk | contribs) →Other structures: backtracking |
||
Line 260:
The regular implementation as disjoint-set forests does not react favorably to the deletion of elements,
in the sense that the time for <code>Find</code> 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 <code>Find</code> depends on the ''current'' number of elements<ref>{{cite journal |last1=Alstrup |first1=Stephen |last2=Thorup |first2=Mikkel |last3=Gørtz |first3=Inge Li |last4=Rauhe |first4=Theis |last5=Zwick |first5=Uri |title=Union-Find with Constant Time Deletions |journal= ACM Transactions on Algorithms|date=2014 |volume=11 |issue=1 |pages=6:1–6:28|doi=10.1145/2636922 |s2cid=12767012 }}</ref><ref>{{cite journal |last1=Ben-Amram |first1=Amir M. |last2=Yoffe |first2=Simon |title=A simple and efficient Union-Find-Delete algorithm |journal=Theoretical Computer Science |date=2011 |volume=412 |issue=4–5 |pages=487–492|doi=10.1016/j.tcs.2010.11.005 }}</ref>
==Backtracking==
It is possible to extend certain disjoint-set forest structures to allow backtracking. The basic form of backtracking is to allow a
<code>Backtrack(1)</code> operation, that undoes the last <code>Union</code>. A more advanced form allows <code>Backtrack(i)</code>,
which undoes the last i unions. The following complexity result is known: there is a data structure which supports <code>Union</code>
and <code>Find</code> in <math>O(\log n / \log \log n)</math> time per operation, and <code>Backtrack</code> in <math>O(1)</math> time.<ref name="WT">{{Cite journal
| last1 = Westbrook
| first1 = Jeffery R.
| last2 = Tarjan
| first2 = Robert E.
| title = Amortized Analysis of Algorithms for Set Union with Backtracking
| journal = SIAM Journal on Computing
| volume = 18
| issue = 1
| pages = 1-11
| date =
| year = 1989
| doi = 10.1137/0218001
| pmid =
| url =
}}</ref>. In this result, the freedom of <code>Union</code> to choose the representative of the formed set is essential.
Better amortized time cannot be achieved within the class of separable [[pointer algorithm]]s<ref name="WT"/>.
== Applications ==
| |||