سلام
میشه این سوال Treap رو توضیح بدید؟! جواب پاسخ نامه رو متوجه نشدم !!
![[تصویر: 247136_060220141485.jpg]](https://img.manesht.ir/247136_060220141485.jpg)
(۱۸ بهمن ۱۳۹۲ ۰۴:۲۶ ب.ظ)hosein_khoshdel نوشته شده توسط:(17 بهمن ۱۳۹۲ ۰۲:۱۴ ب.ظ)helena نوشته شده توسط: سلام
میشه این سوال Treap رو توضیح بدید؟! جواب پاسخ نامه رو متوجه نشدم !!
سلام
الویت S برابر ۲۰ـه دیگه؟ خط روش باعث شده نبینم درست.
به هر حال، در treap اگر کلید ها و اولویت ها متمایز باشن درخت حاصل یکتا خواهد بود. حالا وقتی سه تا اولویت ۶ ، دو تا اولویت ۳ و دو تا اولویت ۱۰ داریم( با فرض این که اولویت S برابر ۲۰ ـه)می تونیم ۶ ها رو با !۳ ، ۳ ها رو با !۲ و ۱۰ ها رو هم با !۲ بچینیم که ضربشون یعنی ۶ *۲*۲ برابر ۲۴ می شه.
این که چرا treap با کلید ها و الویت های متمایز یکتاس رو دقیقا نمی دونم.اگه یکی پیدا بشه دلیل این موضوع رو بگه ممنون می شم.
![[تصویر: 247136_59220317097559582175.jpg]](https://img.manesht.ir/247136_59220317097559582175.jpg)
خیلی ممنون
اولویت S هم ۱۰ ! ولی جواب پاسخ نامه گزینه ۲ یعنی ۲۰ بود...
جواب [tex]2^2 ^{ }2^2 2^3[/tex] میشه؟ گزینه ۳؟
(۲۰ بهمن ۱۳۹۲ ۰۵:۵۶ ب.ظ)mohammad.ardeshiri نوشته شده توسط: جواب [tex]2^2 ^{ }2^2 2^3[/tex] میشه؟ گزینه ۳؟
جواب گزینه ۲ هستش
ولی نمی دونم چطوری بدست می یاد
(۲۰ بهمن ۱۳۹۲ ۰۵:۵۶ ب.ظ)mohammad.ardeshiri نوشته شده توسط: جواب [tex]2^2 ^{ }2^2 2^3[/tex] میشه؟ گزینه ۳؟
این دو تا توضیحات پاسخ نامه است :
[attachment=15325]
[attachment=15326]
حالا یه شیر پاک خورده این توضیح رو توضیح بده!
خوب عکس دوم برای من باز نشد اما با توجه به عکس اول ۳ تا نودی که اولیت ۱۰ دارن بالاتر از همه قرار می گیرن
ترتیب قرار گیریشون می شه عدد کاتالان (با توجه به این که به صورت BST قرار می گیرن)
گره های با اولویت ۳ تو یک قسمت قرار می گیرن عدد کاتالانش می شه ۲
اما گره های با اولویت ۶ به دو دسته تقسیم می شون ۲ به دوقسمت (تقسیم شدنشون بر حسب خاصیت BST هستش چون T حرف اخر هستش و S دارای اولویت ۱۰ هستش باعث می شه از دوتای دیگه جدا بشن) اون دوتا هم خودشوت بر حسب عدد کاتالان توی ۲ حالت قرار می گیرن
اخرش می شه ۲*۲*۵ که ۲۰ می شه
terap اول بر اساس اولویت مرتب میکنه بعد انقدر دوران میده تا درست شه کلیدش
اینجا دوران نیاز نیست
کلا ۳تا اولویت ۱۰ برای ریشه وجود داره پس میشه کاتالان تا حالت برای ریشه
t , a ,f که یکتاست پس یه حالت داره
pr و db هم به همون قاعده