Disjoint-set data structure: Difference between revisions

Revision as of 18:33, 3 August 2023

Revision as of 17:13, 10 October 2023

Line 1:

{{Short description|Data structure for storing non-overlapping sets}}

{{Infobox data structure

| name = Disjoint-set/Union-find Forest

| type = multiway tree

| invented_by = [[Bernard A. Galler]] and [[Michael J. Fischer]]

| 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>

|

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

|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 search_avg = {{math|''O''(''α''(''n''))}}<ref name="tarjan1975"/> (amortized)

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

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

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

|insert_worst ={{math|O(1)}}<ref name="tarjan1975"/>

}}