۳۷-۲
۳۸-۱
۴۰-۲
۴۱-۳
۴۲-۲
۴۴-۳
(۲۰ بهمن ۱۳۹۱ ۰۵:۰۵ ب.ظ)IT86 نوشته شده توسط: بله همون سوال ۳۷ خود سوال گفته درخته دودویی یکی از دوستانم گفته avl منظورشه یکی هم گفته درخت انتخابی
این درخت اصلا شبیه به درخت دودویی متوازن AVL نیست. درخت AVL که یک درخت جسجوی دودویی متوازن است، درختی است که هر گره از فرزند راستش کوچکتر و از فرزند چپش بزرگتر باشد که این درخت این مساله این ویژگی را ندارد. درخت AVL لازم نیست که کامل باشد. این همه تفاوت با این درخت صورت مساله.
شما برای پیدا کردن گره ای که می خواهید آن را حذف کنید باید با on تمام برگها رو چک کنید.
بله این درخت شبیه به درخت انتخابی است.
[/quote]
شما داری رو سوال ۳۷ بحث می کنی؟ کجا گفته AVL کجا اصلا گفته درخت دودویی؟!!!
[/quote]
دوست عزیز صورت سئوال گفته درخت دودویی کامل پس avl هم هست
منم گزینه ۴ رو زدم
من یکبار دیگه اینو گذاشتم.
درخت AVL که یک درخت جسجوی دودویی متوازن است
شما یه منبع بگذارین که درخت دودویی رو با درخت جستجوی دودویی یکی گرفته و از اون بدتر درخت دودویی که می تونه کامل باشه یانه رو با درخت AVL یکی گرفته؟
شما به تعاریف مسلط نیستین و پافشاری هم می کنید که درخت دودویی کامل حتما AVL هست که کاملا اشتباهه
نه دوست عزیز صورت سئوال رو خوب بخون!
گفته اگر گره های سطح اخر رو برداریم کاملا متوازن میشه
میشه تعریف درخت متوازن و کاملا متوازن رو بگید؟؟؟؟
بله دوست عزیز گفته شده اگرسطح آخر رو بردارین میشه درخت دودویی متوازن
درثانی کی حرف از جستجو زد؟
خود سوال گفته شده درخت دودویی کامل هستش اگر سطح آخر رو برداری میشه متوازن
این تعریف واضحه
دوست عزیز شما بیشتر گویا پافشاری میکنی و صورت سوالو متوجه نشدی!
(۲۰ بهمن ۱۳۹۱ ۰۴:۳۶ ب.ظ)IT86 نوشته شده توسط: دوستان اگر avl هم درنظربگیریم حذف و درج و جستجو میشه log n
برای کاهش فک کنم بشه بازم log n آخه گفته شده کوچکترین فرزند در ریشه هستش ااگرکاهش بدیم یک مقداررو ممکنه اون مقدارازریشه کمترشه و باید جابه جابشه
ازطرفیم ممکنه باز پدراون ریشه هم بزرگترباشه و بازهم جابه جامیشه
بازم میشه log n
پس هرشه بازم میشه اگرهیپ درنظرنگیریم
هیپ درنظربگیریمم میشه هرسه
مگر اینکه درخت انتخابی بگیریم ک بستگی داره به تعداد آرایه ها که باتوجه به سوال ک ذکرنکرده از ارایه پس انتخابی نمیشه
شما داری میگی AVL. شما لطفا تعریفتو از AVL بکن.
اگه این درخت AVL بود میشد با log درج و حذفو انجام داد اما این درخت مساله AVL نیست.
(۲۰ بهمن ۱۳۹۱ ۰۶:۰۶ ب.ظ)IT86 نوشته شده توسط: بله دوست عزیز گفته شده اگرسطح آخر رو بردارین میشه درخت دودویی متوازن
درثانی کی حرف از جستجو زد؟
خود سوال گفته شده درخت دودویی کامل هستش اگر سطح آخر رو برداری میشه متوازن
این تعریف واضحه
دوست عزیز شما بیشتر گویا پافشاری میکنی و صورت سوالو متوجه نشدی!
شما خودت گفتی AVLهست.
الآن داری میگی کی گفته درخت جستجوی دودویی(BST)؟!!!
من تعریف AVL رو گفتم. گویا شما تعریف درستی از AVL ندارید.
شما متنمو با دقت بخون !!
دوستان گفته بودن درخت متوازنه منم گفتم :
(۲۰ بهمن ۱۳۹۱ ۰۷:۱۷ ب.ظ)mahdiii نوشته شده توسط: [quote='IT86' pid='160212' dateline='1360325183']
دوستان اگر avl هم درنظربگیریم حذف و درج و جستجو میشه log n
نوشتم اگر هم متوازن درنطر بگیریم!!!
اینبارگویا شما متنارو بادقت نمیخونی!
هرسه میشد اما من مثه هیپ گرفتم
شما داری رو سوال ۳۷ بحث می کنی؟ کجا گفته AVL کجا اصلا گفته درخت دودویی؟!!!
[/quote]
دوست عزیز صورت سئوال گفته درخت دودویی کامل پس avl هم هست
منم گزینه ۴ رو زدم
[/quote]
شما دارای می گی درخت دودویی کامل AVL هست یا اینم نگفتین؟!!
کجای درخت دودویی کامل AVL هست؟ تو کدوم منبع اینو نوشته.
AVL یک درخت خاصه. درختی دودویی که هم متوازن باشه و هم هر گره اش از بچه سمت راستش کوچکتر و از بچه سمت چپش بزرگتر باشه(BST)
شما راه حلتونو لطفا بگین چطور حذف کردن یک عنصر دلخواه log شد در این درخت؟
(۲۱ بهمن ۱۳۹۱ ۰۱:۲۶ ق.ظ)IT86 نوشته شده توسط: شما متنمو با دقت بخون !!
دوستان گفته بودن درخت متوازنه منم گفتم :
(۲۰ بهمن ۱۳۹۱ ۰۷:۱۷ ب.ظ)mahdiii نوشته شده توسط: [quote='IT86' pid='160212' dateline='1360325183']
دوستان اگر avl هم درنظربگیریم حذف و درج و جستجو میشه log n
نوشتم اگر هم متوازن درنطر بگیریم!!!
اینبارگویا شما متنارو بادقت نمیخونی!
شما فکر می کنید هر درخت متوازن AVL هست؟ اگه این جوری فکر می کنید اشتباه فکر می کنین.
هرسه اصلا نمیشه.
درج log n
حذف هم که مشخصه نیست
اما تغییر چون گفته دلخواه یکم شک برانگیزه
باتوجه به اینکه ریشه ها هیچ کمکی بما درمورد جستجو نمیکنن باید همه گرهها بررسی بشهه بنظرم
حالا یا اینم log n میشه یا n.
من گزینه ۲ زدم
خداروشکر یکی اینجا پیدا شد طرف منو گرفت
. IT86 , xani اصرار دارن بگن این درخت AVL هست و میشه با log درج و حذف رو انجام داد.
درخت AVL چه ربطی به این سوال داره من نمیدونم
(۲۱ بهمن ۱۳۹۱ ۰۲:۲۱ ق.ظ)saho نوشته شده توسط: هرسه اصلا نمیشه.
درج log n
حذف هم که مشخصه نیست
اما تغییر چون گفته دلخواه یکم شک برانگیزه
باتوجه به اینکه ریشه ها هیچ کمکی بما درمورد جستجو نمیکنن باید همه گرهها بررسی بشهه بنظرم
حالا یا اینم log n میشه یا n.
من گزینه ۲ زدم
ببینید این گفته کاهش یک عنصر موجود. پس ما می خواهیم یک عنصری که در این ساختار وجود داره رو کم کنیم اما جاشو که نمیدونیم. پس باید برگها رو بگردیم و اونو پیدا کنیم و بعدش عملیات دیگرو انجام بدیم. تعداد برگها از مرتبه n هست.n/2 میشه
(۲۱ بهمن ۱۳۹۱ ۰۲:۲۵ ق.ظ)mahdiii نوشته شده توسط: خداروشکر یکی اینجا پیدا شد طرف منو گرفتکجایه سوال گفته AVL ??????????
IT86 , xani اصرار دارن بگن این درخت AVL هست و میشه با log درج و حذف رو انجام داد.
درخت AVL چه ربطی به این سوال داره من نمیدونم
اصلا ریشه هیییییییییچ کمکی نمیکنه توجستجوکردن.
بنظرم منطقی فقط درج درسته
اما ازاونجاییک طراحا منظورشونومیخان بچیچونن شاید اون تغییر (دلخواه) منظورخاصی داشته
اگه منظورخاصی نباشه که میشه همون درج
به نظر من که خیلی واضحه و این تستو میشد در مدت ۱۰ ثانیه جواب داد.
ما مکان عنصر رو نمی دونیم در سوال هم که نگفته پس باید اونو پیدا کنیم. خیلی واضحه.
(۲۱ بهمن ۱۳۹۱ ۰۲:۳۳ ق.ظ)mahdiii نوشته شده توسط: به نظر من که خیلی واضحه و این تستو میشد در مدت ۱۰ ثانیه جواب داد.
ما مکان عنصر رو نمی دونیم در سوال هم که نگفته پس باید اونو پیدا کنیم. خیلی واضحه.
ازخدامه که اینجوری باشه
تحلیل من در مورد سوال ۳۷ اینه که اولا هیپ نیست و هرچند متوازنه ولی BST نیست که اعمال logn باشه ولی شبیه درخت مسابقات حذفی بین n شرکت کننده هست.
چون اعداد در برگها هستند برای حذف یک عدد باید از مکان n/2 (اگر ذخیره سازی آرایه ای باشد) جستجو کنیم پس تا اینجا (o(n تازه بعد باید بعد حذف ساختار درخت رو درست کنیم چون ممکنه این عدد درسطرهای بالاتر تکرار شده باشد و هم شکل درخت دوباره کامل شود، اگه ازساختار گره پیوندی هم استفاده بشه از logn بیشتر میشه.
برای درج چون باید عدد باید به عنوان یک برگ درج بشه بهترین حالت اینه که آخرین گره غیر برگ فرزند راست نداشته باشه و به جای فرزند راست آخرین گره غیر برگ درج خواهد شد و بعد هم باید با برادرش مقایسه شود تا در صورت کوچکتر بودن در والد تکرار شود تا ریشه ، پس logn ولی این بهترین حالت بود در حالتی که همه ی گره های داخلی دو فرزندی باشد باید ۲ گره به درخت اضافه بشه پس یا باید برگها رو یه واحد شیفت بدیم یا از اول درخت رو بسازیم که در هر صورت و با هر شیوه ذخیره سازی (o(n میشه.
برای کاهش یک عدد با فرض اینکه مکان مشخص باشد در بدترین حالت اگر عدد مینیموم باشد تا ریشه تکرار شده و باید اصلاح شود پس logn
امیدوارم این یکی گزینه ۲ باشه!
