Disjoint-set data structure: Difference between revisions

Revision as of 10:51, 7 July 2023

Revision as of 12:07, 11 July 2023

Line 6:

|invented_year=1964

|

|space_avg = ={{math|O(''n'')}}<ref name="tarjan1975">{{cite journal|last1=Tarjan|first1=Robert Endre|author1-link=Robert E. Tarjan|year=1975|title=Efficiency of a Good But Not Linear Set Union Algorithm|journal=Journal of the ACM|volume=22|issue=2|pages=215&ndash;225|doi=10.1145/321879.321884|hdl=1813/5942|s2cid=11105749|hdl-access=free }}</ref>

|space_worst ={{math|O(''n'')}}<ref name="tarjan1975"/>

|search_avg ={{math|O(''α''(''n''))}}<ref name="tarjan1975"/>

|search_worst={{math|O(''α''(''n''))}}<ref name="tarjan1975"/>

|merge_avg insert_avg ={{math|O(''α''(''n'')1)}}<ref name="tarjan1975"/>

|merge_worstinsert_worst ={{math|O(''α''(''n'')1)}}<ref name="tarjan1975"/>

}}