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

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

ارسال:
  

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 ۴ ۳,۸۴۱ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۴۲ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۳ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۲۰۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۳ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۱۳۵ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  تعداد درخت فراگیر ss311 ۰ ۲,۰۵۷ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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