لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت نمایش مجموعه ها با درخت توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت نمایش مجموعه ها با درخت قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

   مجموعه

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

Øمجموعه مجزا :
اگر sj , si دو مجموعه باشند وij باشد ، آن گاه   هيچ عضو مشترکي بين اين دو مجموعه وجود ندارد.

اسلاید ۲ :

مثال

به عنوان مثال عناصر۰ تا ۹ را مي توان به سه مجموعه مجزاي زير تفكيك کرد:

l

       S1={0,6,7,8}              

       S2={1,4,9}            

       S3={2,3,5}             

اسلاید ۳ :

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

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

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

اسلاید ۴ :

نمايش مجموعه ها  

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

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

اسلاید ۵ :

عملكردهاي روي مجموعه ها

اجتماع دو مجموعه مجزا(Union(i,j))

عضويت i در يک مجموعه (Find(i))

اسلاید ۶ :

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

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

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

اسلاید ۷ :

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

 براي به دست آوردن اجتماع  S1,S2  

Øيکي از درختها زير درخت ديگري

Øفيلد والد يكي از ريشه ها را در ريشه ديگري قرار دهيم.

اسلاید ۸ :

قانون وزن براي union(i,j)

تعريف :

Øاگر تعداد گره ها در درختي با ريشه i کمتر از تعداد گره هاي درختي با ريشه j باشد ، آنگاه j را والد i و در غيراين صورت i را والد j قرار مي دهيم .

اسلاید ۹ :

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

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

Øفيلد count

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

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

Øدر ابتدا فيلد parent  تمام گره ها برابر است .

اسلاید ۱۰ :

قضيه (به دست آوردن حداکثر عمق درخت ):

Øفرض کنيد که کارخود را با درختاني که هر کدام فقط يک گره دارند آغاز کنيم و T درختي با  m گره باشد که حاصل اجتماع با استفاده از تابع WeightedUnion  است.

Øدر اين صورت عمق T حداکثر برابر [log2m]+1 خواهد بود