دسته | ریاضی |
---|---|
حجم | 25/94 کیلوبایت |
صفحه | 36 |
فرمت | pptx |
قیمت | 24000 تومان |
دانلود پاورپوينت نمایش مجموعه ها با درخت
هر مجموعه را مي توان به صورت يک درخت نمايش داد در اين درخت ها اشاره گرها از فرزندان به والد متصل شده اند .
ابتدا گره هاي درخت را با يك آرايه به نام Parent[Maxsize] نشان مي دهيم. i امين عنصر اين آرايه نشان دهنده گره i درخت است.
اين الگوريتم در اجرا چندان خوب عمل نمي كند.
به دنباله هاي زير توجه كنيد :
Union(0,1) , Union(1,2) , Union(2,3) , Union(3,4) , ... ,Union(n-2,n-1)
اين دنباله از عملكردها درخت از هم پاشيده(تبهگون) زير را ايجاد مي كند .
بايد تعداد گره ها در هر درخت معلوم باشد فيلد count
اگر i يک گره ريشه باشد، count[i] برابر تعداد گره ها در آن درخت مي باشد .
مي توانيم از فيلد parent ريشه براي نگهداري مقدار count به صورت يک عدد منفي استفاده کنيم .
در ابتدا فيلد parent تمام گره ها برابر -1 است .
فهرست مطالب
مجموعه
نمايش مجموعه با درخت
نمايش مجموعه ها …
عملكردهاي روي مجموعه ها
اجتماع مجموعه ها
تجزيه و تحليل تابع SimpleUnion ...
قانون وزن براي union(i,j)...
پياده سازي قانون وزن براي
تجزيه و تحليل توابع
قضيه (به دست آوردن حداکثر عمق درخت )
اثبات
عضويت i در يک مجموعه
پيدا كردن
تجزيه و تحليل تابع
قانون تخريب
تجزيه و تحليل