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

درخت دودویی

ارسال:
  

sharareh_moradi پرسیده:

درخت دودویی

سلام
لطفا این سوال رو حل میکنید


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

MiladCr7 پاسخ داده:

RE: درخت دودویی

سلام!!!راستش این سوال حذف شده علتش هم ابهام در صورت سوال بودهHuhHuh
فک کنم به دلیلی که الان میگم این سوال از طرف دکتر قدسی ابهام دار تلقی شده.
ابهام سوال:
اگه همه حالت های درخت های جست و جوی دودویی با اختلاف عمق ۱ برای برگاش رو بخوایم مد نظر بگیریم این سوال فک کنم پاسخش تو گزینه ها نیست ولی طراح سوال تو گزینه ها حرکت جالبی انجام داده و تو همه گزینه ها جایگشت ۵ عنصر از یه تعداد حالت رو حساب کرده!!!این حالت وقتی توی شرایطی پیش میاد که توی هر سطح ماکزیمم نود رو داشته باشیم.یا همون درخت متوازن باشه حالا با هم انجام میدیم ببینید(احتمالا به خاطر همین سوال حذف شده!!جواب داره ولی مبهمه صورت سوال چون درخت موربم جز حالات مورد نظر ما هستش)
قبلش چند تا تعریفم مرور میکنیم:
ببینید گفته درخت دودویی جست و جو یعنی مقدار هر گره از فرزند سمت چپش بیشتره و از فرزند سمت راستش کمتره!!
خب نکته ای که تو صورت سوال گفته اینه که اختلاف عمق برگ ها باید حداکثر یک باشه یعنی یا هم سطح باشن یا یه واحد اختلاف داشته باشند
عمق رو هم فاصله گره تا ریشه در نظر میگیریم !خب حالا این حالتی که گفته ما رو یاد چه نوع درختی میندازه؟؟گفته شده اختلاف عمق برگ حداکثر ۱
خب ما هم همین کارو میکنیم ببینیم چی میشه
سطح اول ریشه
سطح دوم، ۲ تا نود
سطح سوم، ۴ تا نود
سطح چهارم ،۸ تا نود
سطح پنجم ،۱۶ تا نود
خب دیگه نمیتونیم سطح بعدی رو کامل نود بذاریم چون تا اینجا ۳۱ تا نود مصرف کردیم و فقط ۵ تا مونده.خب الان دقت کنید ما توی سطح پنجم ۱۶ تا نود قرار دادیم پس الان ۳۲ تا حالت برای قرار دادن این ۵ تا گره داریم درسته؟؟؟و ترتیب قرار گرفتن این ۵ تا نود هم مهمه چون برامون مهمه
چه نودی چپ باشه یا چه نودی راست باشه(باید شرایط درخت جست و جوی دودویی رو حفظ کنه)پس میشه ترتیب [tex]\binom{32}{5}[/tex]

دقت کنید که اون ۳۱ تا نود که گذاشتیم نمیتونن با هم جا به جا شن چون BST رو به هم میزنن پس فقط یه حالت میتونن داشته باشن
نقل قول این ارسال در یک پاسخ

ارسال:
  

artmiss پاسخ داده:

RE: درخت دودویی

(۱۶ دى ۱۳۹۳ ۰۹:۳۹ ب.ظ)miladcr7 نوشته شده توسط:  سلام!!!راستش این سوال حذف شده علتش هم ابهام در صورت سوال بودهHuhHuh
فک کنم به دلیلی که الان میگم این سوال از طرف دکتر قدسی ابهام دار تلقی شده.

ابهام سوال
۱- گفته درخت دودوی جستجو یا همون BST ولی منظوره سوال درخت دودویی بوده و راه حلی هم که شما رفتی واسه درخت دودویی بود نه BST به همون دلیلی که ره های میانی ممکنه ترتیب BST رو به هم بریزه گره های پایانی هم ممکنه بهم بریزه و نمیتونی هر ۳۲ مکان سطح آخرو بگیره.
۲-این که اختلاف برگ ها حداکثر یک باشه مفهوم پر بودن درخت تا عمق یکی مونده به آخر رو نمیده برای اینکه مطمئن شی میتونی درخت اریب چپ یا راست را در نظر بیگیری که هر دو میتونن درخت دودویی جستجو هم باشن

پس گزینه ای که سنجش داده یعنی همون جوابی که شما دادین با دو فرض درسته یکی اینکه درخت دودویی باشه (نه درخت دودویی جستجو)
دوم اینکه درخت تا عمق یکی مونده به آخر پر باشه ( نمیدونم اسم خاص داره یه نه)

یا میشد گفت درخت دودویی محض باشه و اختلاف گره های برگ حداکثر یک باشه. ( فک کنم با این شرایط هم درست باشه مطمئن نیستم بقیه در این مورد نظر بدن بهتره)

ولی با همون شرایطی که سوال گفته این سوال امروز روزگار منو سیاه کرد و همه کتابا هم به همین جواب غلط بسنده کردن الا نصیر اونم بدون هیچ توضیحی یه جوابی داده که آخرش معلوم نیس چیو میخواد ثابت کنه!
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

sharareh_moradi پاسخ داده:

RE: درخت دودویی

چقد راحت بودBig Grin
دستتون درد نکنه
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۴,۹۱۱ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۶۴۷ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۷۹۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۴۱۴ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۴۲۹ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۸,۱۶۳ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  تعداد درخت فراگیر ss311 ۰ ۲,۳۳۷ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  درخت دسترس پذیری برای شبکه های پتری αɾια ۱ ۲,۴۲۳ ۰۹ تیر ۱۳۹۸ ۰۶:۳۰ ب.ظ
آخرین ارسال: αɾια
  سطح و عمق و ارتفاع درخت remove ۵ ۱۱,۴۶۴ ۱۹ اسفند ۱۳۹۷ ۰۴:۲۴ ب.ظ
آخرین ارسال: mstfvi
  الگوریتم درخت porseshgar ۰ ۱,۷۰۶ ۱۷ بهمن ۱۳۹۷ ۱۲:۲۴ ب.ظ
آخرین ارسال: porseshgar

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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