زمان کنونی: ۰۲ آبان ۱۳۹۹, ۰۹:۳۴ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مرتبه ایجاد درخت

ارسال:
  

rad.bahar پرسیده:

مرتبه ایجاد درخت

سوال اول
در چه زمانی (بهترین زمان) می توان با n کلید دلخواه، یک درخت AVL ایجاد کرد
n)o)
n^2)o)
nlogn)o)
logn)o)

سوال دوم
در چه زمانی (بهترین زمان) می توان با n کلید دلخواه، یک درخت max heap ایجاد کرد
logn)o)
n^2)o)
n)o)
logn)o)
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

rad.bahar پاسخ داده:

RE: مرتبه ایجاد درخت

سلام دوستان
هیچ کدام که جواب ندادید. من یک جواب تخمینی می دهم ببینید به نظرتان درست هست یا نه؟

سوال اول :
مرتبه ساخت درخت AVL با n عنصر :
ازا انجایی که درخت AVL درختی اختلاف زیر درخت های هر نود کمتر از ۲ است. اگر بتوانیم با n نود یک درخت کامل ایجاد کنیم خود به خود avl هم هست.
به نظرم اول عناصر مرتب کنیم و در یک ارایه درج کنیم
با این ارایه مرتب یک درخت جستجوی دودویی کامل ایجاد کنیم به این صورت که
وسط ارایه را ریشه می گیریم عنصر وسط عناصر سمت چپ به عنوان فرزند چپ ریشه و عنصر وسط عناصر سمت راست را به عنوان فرزند راست ریشه انتخاب می کنیم و همین کار را به صورت بازگشتی انجام دهیم تا تمام عناصر به درخت اضافه شوند.
t(n)=2*t(n/2)+1
مرتبه این کار: مرتب سازی (nlogn) - ایجاد درخت n - پس در کل nlogn

سوال دوم :
مرتبه ساخت درخت heap
در کتاب پوران نوشته بود که اگر عناصر را در ارایه درج کنیم و با شروع از اخرین گره میانی تا ریشه، هر گره را با بچه اش مقایسه کنیم و عنصر بزرگتر را در گره قرار بدهیم. تعداد مقایسه در هر نود دو عدد است و از انجایی که موقعیت اخرین گره میانی درخت در وسط ارایه قراردارد. و این کار را برای عنصر وسط تا عنصر یکم ارایه انجام بدهیم در کل ۲ * (n/2) تا مقایسه انجام میشه و درخت heap میشه. مرتبه الگوریتم n هست ولی نگفته بود بهترین حالت هم با حالت متوسط برابر یا نه.
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مرتبه شبه کد rad.bahar ۱ ۶۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۳ ۱۱۲ ۱۱ مهر ۱۳۹۹ ۰۳:۴۷ ب.ظ
آخرین ارسال: عزیز دادخواه
  عمق درخت ???? rad.bahar ۱ ۷۸ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۸,۰۴۹ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۲,۹۶۸ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی Sanazzz ۱۷ ۵,۵۶۰ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  تعداد درخت فراگیر ss311 ۰ ۳۷۱ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  ایجاد شغل در زمینه خدمات hiradupvc ۱ ۹۳۵ ۲۱ دى ۱۳۹۸ ۰۵:۱۴ ب.ظ
آخرین ارسال: parisa1140
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۱,۰۶۶ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۲ ۱,۴۸۸ ۰۷ مهر ۱۳۹۸ ۰۶:۴۵ ب.ظ
آخرین ارسال: hamzadebaroon

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close