پاورپوینت نمایش مجموعه ها با درخت

پاورپوینت نمایش مجموعه ها با درخت

چکیده:

مجموعه

به دسته ای از اشیا که در یک یا چند خصوصیت مشترک هستند .

مجموعه مجزا :
اگر sj , si دو مجموعه باشند وi≠j باشد ، آن گاه   هیچ عضو مشترکی بین این دو مجموعه وجود ندارد.

مثال

به عنوان مثال عناصر0 تا 9 را می توان به سه مجموعه مجزای زیر تفكیك کرد:

       S1={0,6,7,8}

       S2={1,4,9}

S3={2,3,5}            

نمایش مجموعه با درخت

هر مجموعه را می توان به صورت یک درخت نمایش داد:

در این درخت ها اشاره گرها از فرزندان به والد متصل شده اند .

نمایش مجموعه ها  …

ابتدا گره های درخت را با یك آرایه به نام Parent[Maxsize] نشان می دهیم.

i  امین عنصر این آرایه  نشان دهنده گره i درخت است.

اجتماع مجموعه ها

اگرSi,Sj  دو مجموعه مجزا باشند ، آن گاه اجتماع آن ها به صورت زیر تعریف می شود :

}همه عناصر X به صورتی که X یا عضو Si  باشد یا عضو Sj SiUSj={   
اجتماع مجموعه ها...

تجزیه و تحلیل تابع SimpleUnion ...

این الگوریتم در اجرا چندان خوب عمل نمی كند.

 به دنباله های زیر توجه كنید :

Union(0,1) , Union(1,2) , Union(2,3) , Union(3,4) , ...  ,Union(n-2,n-1)

   این دنباله از عملكردها درخت از هم پاشیده(تبهگون) زیر را ایجاد می كند .

تجزیه و تحلیل تابع SimpleUnion ...

زمان صرف شده برای یك عمل اجتماع ثابت است

عمل اجتماع در زمان O(n) انجام می شود .

اجتناب از ایجاد درختان از هم پاشیده

قانون وزن (Weighting)

پیاده سازی قانون وزن برای union(i,j)...

باید تعداد گره ها در هر درخت معلوم باشد

فیلد count

اگر i یک گره ریشه باشد، count[i] برابر تعداد گره ها در آن درخت می باشد .

می توانیم از فیلد parent ریشه برای نگهداری مقدار count  به صورت یک عدد منفی استفاده کنیم .

در ابتدا فیلد parent  تمام گره ها برابر -1 است .