جستجوی موفق و ناموفق در درخت چیه؟ایا برگها ناموفق و گرههای داخلی موفق به حساب میان؟!!!
سلام
در جستجوی دودویی اگر کلید مورد نظر که داریم تو درخت دنبالش میکردیم پیدا بشه جستجو موفق هست و اگر پیدا نشه، ناموفق.
میشه این جستجوی دودویی رو با درخت دودویی نشون داد.
این درختی که میکشیم درخت تصمیم بهش میگن.
داخل هر نود مقدار mid نوشته میشه.
وقتی که به برگ ها برسیم یعنی جستجو ناموفق بوده (گره های مستطیلی)
و اگر در گره های داخلی کار تموم بشه یعنی جستجو موفق بود.
فرمولهایی که کاربردی هستن:
[tex]E=I 2n[/tex]
[tex]s(n)=\frac{I n}{n}[/tex]
[tex]u(n)=\frac{E}{n 1}[/tex]
[tex]s(n)=(1 \frac{1}{n})u(n)-1[/tex]
میانگین تعداد مقایسه در جستجوی موفق رو با [tex]s(n)[/tex] و میانگین تعداد مقایسه در جستجوی ناموفق رو با [tex]u(n)[/tex] نمایش میدن.
[tex]I[/tex] مجموع فاصله ی گره های داخلی از ریشه هست و [tex]E[/tex] مجموع طول مسیرهای خارجی.
[tex]n[/tex] تعداد گره های داخلی
یه عکس از کتاب پوران کشیدم پیوست کردم، که بهتر متوجه بشید.
[attachment=17716]
(۲۴ دى ۱۳۹۳ ۱۰:۰۸ ق.ظ)Ametrine نوشته شده توسط: سلام
در درخت جستجوی دودویی اگر کلید مورد نظر که داریم تو درخت دنبالش میکردیم پیدا بشه جستجو موفق هست و اگر پیدا نشه، ناموفق.
میانگین جستجوی موفق رو با [tex]s(n)[/tex] و میانگین جستجوی ناموفق رو با [tex]u(n)[/tex] نمایش میدن.
[tex]s(n)=(1 \frac{1}{n})u(n)-1[/tex]
دستت طلا
خواهش میکنم
جوابم رو ویرایش کردم و یه درخت برا نمونه گذاشتم.
(۲۴ دى ۱۳۹۳ ۰۳:۲۲ ب.ظ)Ametrine نوشته شده توسط: خواهش میکنم
جوابم رو ویرایش کردم و یه درخت برا نمونه گذاشتم.
بازم ممنون کاملا اوکی شدم