ডিসজয়েন্ট সেট ডাটা স্ট্রাকচার
MakeSet creates 8 singletons.
Union, some sets are grouped together.কম্পিউটার বিজ্ঞানে, ডিসজয়েন্ট-সেট ডাটা স্ট্রাকচার, বা ইউনিয়ন-ফাইন্ড ডাটা স্ট্রাকচার, বা মার্জ-ফাইন্ড সেট, হচ্ছে একধরনের ডাটা স্ট্রাকচার যা কতগুলো ডিসজয়েন্ট (নিশ্চেদ) সেটের কালেকশন। এটা একটা সেটকে কতগুলো ভাগে ভাগ করে ডিসজয়েন্ট সেট তৈরী করে। এতে তিনটা অপারেশন ঘটাতে পারে- একটা নতুন সেট তৈরি, দুইটা সেটকে মার্জ করে একটা সেট করা এবং একটা সেটকে প্রতিনিধিত্বকারী সদস্য (সেটের রুট) বের করা। শেষ অপারেশনের মাধ্যমে দুইটা নাম্বার (ইলেমেন্ট) একই সেটে আছে কি না তা ইফিশিয়েন্টলি জানা যায়।
অপারেশন
[সম্পাদনা]নতুন সেট তৈরি
[সম্পাদনা]MakeSet অপারেশন একটা নতুন ইলেমেন্ট (নাম্বার) যোগ করে। এই ইলেমেন্টটা একটা নতুন সেটে যুক্ত হয়, যেই সেট শুধুমাত্র সেই নতুন ইলেমেন্ট দিয়ে তৈরি এবং নতুন সেট ডাটা স্ট্রাকচারে যুক্ত হয়ে যায়। যদি ডাটা স্ট্রাকচারকে সেটের পার্টিশন হিশেবে দেখা হয়, তবে MakeSet অপারেশন নতুন ইলেমেন্ট যোগ করে সেটের সাইজ বাড়িয়ে দেয়, এবং এটা পার্টিশন বাড়িয়ে নতুন একটা সাবসেট তৈরি করে যেখানে শুধুমাত্র সেই নতুন যুক্ত ইলেমেন্ট থাকে।
ডিসজয়েন্ট-সেট ফরেস্টে, MakeSet নোডের parent পয়েন্টার এবং নোডের size পয়েন্টার ইনিশিয়ালাইজ করে। নিচের সুডোকোড অনুযায়ী নতুন সেট তৈরি করা যেতে পারে:
function MakeSet(x) is
যদি x যদি ফরেস্টে না থাকে তবে
x.parent := x
x.size := 1 // নোড যদি সাইজ স্টোর করে
end if
end function
এই অপারেশনের টাইম কমপ্লেক্সিটি O(n), যেখানে n হচ্ছে ইলেমেন্ট সংখ্যা।