Struktur data Himpunan Lepas (UFDS) digunakan untuk memodelkan sebuah kumpulan dari himpunan-himpunan yang saling lepas, dan dapat menentukan di himpunan mana sebuah item berada, mengecek apakah dua item-item berasal dari himpunan yang sama, dan menggabungkan dua himpunan berbeda menjadi satu jika diperlukan. Himpunan Lepas dapat digunakan untuk menemukan komponen yang terhubung dalam sebuah graf tak berarah, sehingga dapat digunakan sebagai bagian dari algoritma Kruskal untuk masalah Pohon Perentang Minimum (MST).
Lihatlah visualisasi dari contoh UFDS (Himpunan Lepas) di sini!
Setiap pohon melambangkan sebuah himpunan lepas (maka sebuah kumpulan dari himpunan-himpunan lepas tersebut membentuk sebuah hutan) dan akar (root) dari setiap pohon adalah item representatif dari himpunan lepas ini.
Sekarang berhenti dan lihatlah pohon-pohon yang sekarang sedang divisualisasikan. Ada berapa jumlah item-item disana? Berapa jumlah himpunan lepas di sana? Siapa saja anggota dari setiap himpunan lepas tersebut? Apakah item representasi dari setiap himpunan lepas yang ada?
Kita bisa dengan mudah mengingat hutan pohon dengan sebuah larik p dengan ukuran N anggota-anggota dimana p[i] menyimpan orang tua dari item i dan jika p[i] = i, maka i adalah akar dari pohon ini dan juga adalah item representatif dari himpunan yang mengandung item i.
Sekali lagi, lihatlah visualisasi diatas dan tentukan nilai-nilai didalam larik p ini.
Pada contoh tetap yang sama, jawaban-jawaban anda harusnya p = [1, 3, 3, 3, 3, 5, 6, 5, 5, 6, 4, 8,12] dengan ukuran N = 13 untuk p[0] sampai p[12].
Anda dapat mengecek bahwa p[3] = 3, p[5] = 5, p[6] = 6, dan p[12] = 12, yang adalah konsisten dengan fakta bahwa {3,5,6,12} adalah item-item representatif (dari himpunan lepas mereka sendiri).
Kita juga menyimpan satu lagi informasi di dalam larik rank juga dengan ukuran N. Nilai dari rank[i] adalah batas-atas dari tinggi sub-pohon yang berakar pada simpul i yang akan digunakan sebagai heuristik pembimbing untuk operasi UnionSet(i, j). Anda akan menyadari nanti bahwa setelah heuristik 'kompresi-jalur' (akan dijelaskan segera) mengkompres sebuah jalur, nilai-nilai peringkat tidak lagi merefleksikan tinggi sesungguhnya dari sub-pohon tersebut.
Karena banyak item-item dengan peringkat 0, kami mengatur visualisasi sebagai berikut untuk mengurangi kekacauan: Hanya jika peringkat dari sebuah simpul i lebih besar dari 0, maka VisuAlgo akan menunjukkan nilai dari rank[i] (disingkat sebagai satu karakter r) sebagai teks berwarna merah dibawah simpul i.
Pada contoh tetap yang sama, verifikasi bahwa {1,4,6,8} memiliki peringkat 1 dan {3,5} memiliki peringkat 2, dan yang lainnya memiliki peringkat 0 (tidak ditunjukkan).
Pada saat ini, semua nilai-nilai peringkat adalah benar, yaitu mereka benar-benar mendeskripsikan tinggi dari sub-pohon yang berakar pada simpul tersebut. Kita akan segera melihat bahwa mereka tidak akan selalu benar di beberapa slide-slide berikutnya.
Terdapat lima operasi-operasi UFDS (Himpunan Lepas) dalam halaman visualisasi ini:
Contoh-Contoh, Inisialisasi(N), FindSet(i), IsSameSet(i, j), dan UnionSet(i, j).
Operasi pertama (Contoh-Contoh) adalah sederhana: Berikan daftar struktur-struktur Himpunan Lepas dengan berbagai karakteristik-karakteristik untuk titik permulaan anda. Mode kuliah maya ini selalu menggunakan contoh 'Empat Himpunan Lepas' sebagai titik permulaan.
Juga sadari bahwa tidak ada satupun dari contoh-contoh yang memiliki 'pohon yang tinggi'. Anda akan segera mengerti alasannya setelah kami menjelaskan dua heuristik-heuristik yang dipakai.
Inisialisasi(N): Membuat N himpunan lepas, semuanya dengan p[i] = i dan rank[i] = 0 (pada awalnya, nilai-nilai rank ini tidak ditunjukkan).
Kompleksitas waktu dari operasi ini jelas sekali adalah O(N).
Dikarenakan terbatasnya ukuran layar, kami mengatur 1 ≤ N ≤ 16.
FindSet(i): Dari simpul i, pergi ke arah atas di dalam pohon secara rekursif. Yaitu, dari simpul i, kita pergi ke simpul p[i]) hingga kita sampai pada akar dari pohon tersebut, yang adalah item representasi dengan p[i] = i dari himpunan lepas ini.
Dalam operasi FindSet(i), kami menggunakan heuristik kompresi-jalur setelah setiap panggilan kepada FindSet(i) karena sekarang setiap simpul yang terdapat dalam jalur dari simpul i ke akar dari pohon ini mengetahui bahwa akar tersebut adalah item representatif mereka dan dapat langsung menunjuk kepada akar tersebut secara langsung dalam O(1).
Jika kita melakukan FindSet(12), kita akan dengan segera mendapat simpul 12. Jika kita melakukan FindSet(9), kita akan mendapat simpul 6 setelah 1 langkah dan tidak ada perubahan apapun.
Sekarang coba eksekusi . Jika ini adalah panggilan pertama anda pada contoh default Himpunan Lepas ini, maka fungsi tersebut akan mengembalikan simpul 3 setelah 2 langkah dan lalu mengubah struktur Himpuna Lepas karena aksi dari kompresi-jalur (yaitu, simpul 0 langsung menunjuk kepada simpul 3 secara langsung). Sadari bahwa nilai peringkat dari rank[1] = 1 sekarang menjadi salah karena simpul 1 menjadi sebuah daun baru. Tetapi, kita tidak akan mempedulikan untuk memutakhirkan nilai peringkat ini.
Sadari bahwa kali berikutnya anda mengeksekusi lagi, fungsi tersebut akan menjadi jauh lebih cepat karena jalurnya telah terkompres. Untuk saat ini, kita asumsikan bahwa FindSet(i) berjalan dalam O(1).
IsSameSet(i, j): Cek saja apakah FindSet(i) == FindSet(j). Fungsi ini digunakan secara ektensif pada algoritma MST Kruskal. Karena fungsi ini hanya memanggil operasi FindSet dua kali, kita akan mengasumsikan bahwa fungsi ini juga berjalan dalam O(1).
Perlu diingat bahwa fungsi FindSet dipanggil di dalam fungsi isSameSet, maka heuristik kompresi-jalur juga digunakan secara tidak langsung.
Jika kita memanggil IsSameSet(3, 5), kita harusnya mendapatkan false karena simpul 3 dan simpul 5 adalah item-item representatif dari himpunan-himpunan lepas mereka dan mereka berbeda.
Sekarang cobalah padah contoh default yang sama untuk melihat kompresi-jalur secara tidak langsung pada simpul 0 dan simpul 11. Kita harusnya mendapatkan false karena dua item-item representatif: simpul 3 dan simpul 5, adalah berbeda. Sadari bahwa nilai-nilai peringkat pada simpul {1, 5, 8} sekarang semuanya salah. Tetapi kita tidak akan memperbaikinya.
UnionSet(i, j): Bila i dan j berasal dari dua himpunan lepas yang berbeda pada awalnya, kita menghubungkan item representatif dari pohon/himpunan lepas yang lebih pendek dengan item representatif dari pohon/himpunan lepas yang lebih tinggi (kalau tidak, kita tidak berbuat apa-apa). Ini juga dilakukan dalam O(1).
Ini adalah efek dari heuristik penggabungan-berdasarkan-peringkat (union-by-rank) dan akan mengakibatkan pohon yang dihasilkan secara relatif pendek. Hanya jika kedua pohon-pohon memiliki tinggi yang sama sebelum digabungkan (dengan membandingkan nilai-nilai peringkat mereka secara heuristik — catat bahwa kita tidak membandingkan tinggi-tinggi mereka yang sebenarnya), maka peringkat dari pohon yang dihasilkan akan meningkat sebanyak satu unit.
Pada contoh default yang sama, cobalah . Karena pohon yang merepresentasikan himpunan lepas {6, 9} saat ini lebih tinggi (menurut nilai dari rank[6] = 1), maka pohon yang lebih pendek yang merepresentasikan himpunan lepas {12} akan ditaruh dibawah simpul 6, tanpa meningkatkan tinggi dari pohon gabungan sama sekali.
Pada contoh default yang sama, cobalah . Sadari bahwa peringkat-peringkat dari simpul 3 dan simpul 5 adalah sama, yaitu rank[3] = rank[5] = 2. Oleh karena itu, kita bisa menaruh simpul 3 dibawah simpul 5 (implementasi kami) atau simpul 5 dibawah simpul 3 (kedua opsi akan meningkatkan tinggi dari pohon gabungan sebesar 1). Sadari heuristik kompresi-jalur dipkai secara tidak langsung.
Quiz: Starting with N=8 disjoint sets, how tall (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?
Quiz: Starting with N=8 disjoint sets, how short (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?
Diskusi: Kenapa?
So far, we say that FindSet(i), IsSameSet(i, j), and UnionSet(i, j) runs in O(1). Actually they run in O(α(N)) if the UFDS is implemented with both path-compression and union-by-rank heuristics.
This α(N) is called the inverse Ackermann function that grows extremely slowly. For practical usage of this UFDS data structure (assuming N ≤ 1M), we have α(1M) ≈ 1.
For a few more interesting questions about this data structure, please practice on Union-Find Disjoint Sets training module.