نه!
برای ساختش کافیه مثل درخت دودویی معمولی ند هارو اضافه کنی ینی به برگ ها حالا اگه توازن به هم خورد چرخش انجام بدی. که هر اضافه کردن زمان log n می بره و چون nتاس می شه nlogn . دیگه کم تر از این نمی شه.

(۱۳ بهمن ۱۳۹۱ ۰۹:۴۹ ب.ظ)mehdi.nine نوشته شده توسط:  نه!
برای ساختش کافیه مثل درخت دودویی معمولی ند هارو اضافه کنی ینی به برگ ها حالا اگه توازن به هم خورد چرخش انجام بدی. که هر اضافه کردن زمان log n می بره و چون nتاس می شه nlogn . دیگه کم تر از این نمی شه.

ولی گزینه a نادرست است. با این توصیف شما که درست درمی آد!!!

درخت دودویی متوازن خودش log n هست.

(۱۳ بهمن ۱۳۹۱ ۰۲:۰۳ ب.ظ)ana_12345 نوشته شده توسط:  برای ساخت درخت دودویی متوازن با داشتن ارایه مرتب باید عنصر وسط رو انتخاب کرد ارایه رو نصف کرد و همین کار رو برای دو طرف ادامه داد . اینجوری می شه o(N؟ راهشو درست می گم ؟ یا راه دیگه ای داره ؟

---

پاسخ ماهان اینه

کاملا حرف ماهان درسته و این کار با on انجام میشه. فقط اون چیزی که تو سوال گفته "در مدل مقایسه ای ساخت"
این مفهومش چیه دیگه؟!!

---

با این الگوریتمی که شما گفتین هیچ عمل مقایسه ای انجام نمیشه و فقط اونا رو به صورت تقسیم بر دو در درخت می چینیم. البته یه مقایسه ای برای ادغام آرایه ها با هم داریم. کلا هر چی آدم بیشتر بدونه گیج تر میشه.)

(۱۴ بهمن ۱۳۹۱ ۱۲:۵۱ ق.ظ)mahdiii نوشته شده توسط:  کاملا حرف ماهان درسته و این کار با on انجام میشه. فقط اون چیزی که تو سوال گفته "در مدل مقایسه ای ساخت"
این مفهومش چیه دیگه؟!!

---

با این الگوریتمی که شما گفتین هیچ عمل مقایسه ای انجام نمیشه و فقط اونا رو به صورت تقسیم بر دو در درخت می چینیم. البته یه مقایسه ای برای ادغام آرایه ها با هم داریم. کلا هر چی آدم بیشتر بدونه گیج تر میشه.)

پس چه جوری میشه On ؟؟

منظورم Onlogn بود در حالی که گزینه یک گفته امگای nlogn بعدشم حرف ماهان غلطه چون گفته درخت دودویی کامل اما درخت جست و جو ی متوازن می تونه کامل نباشه.

(۱۴ بهمن ۱۳۹۱ ۱۰:۳۱ ب.ظ)mehdi.nine نوشته شده توسط:  

(14 بهمن ۱۳۹۱ ۱۲:۳۶ ق.ظ)reza7788 نوشته شده توسط:  

منظورم Onlogn بود در حالی که گزینه یک گفته امگای nlogn بعدشم حرف ماهان غلطه چون گفته درخت دودویی کامل اما درخت جست و جو ی متوازن می تونه کامل نباشه.

ببینید به اون درخت کامل گیر ندید اما خیلی راحت میشه این کارو کرد. محاسبه با on
ابتدا سه آرایه مرتب با On در هم ادغام میشن که فکر نکنم جای بحث داشته باشه پس حالا یک آرایه مرتب داریم.
بعدش اگر وسط آرایه رو بگیریم و اونو به عنوان ریشه درنظر بگیریم و فرزند چپش بشه وسط آرایه تقسیم شده سمت چپ و فرزند راستش بشه وسط آرایه تقسیم شده راست و این کارو ادامه بدیم خوب مرتبش که on هست و درخت جستجوی متوازن AVL در آخر خواهیم داشت با مثالم می گم که اصلا جای بحث نداشته باشه.
"درسته که خروجی درخت کامل نیست (یعنی ممکنه نباشه) اما حتما درخت جستجوی دودویی متوازن AVL هست"
سه آرایه به صورت
۱ ۵ ۶ ۸ ۹
۳ ۷ ۱۳
۴ ۱۰ ۲۱ ۲۸ ۳۰
خوب در هم ادغام بشن میشن
۱ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۳ ۲۱ ۲۸ ۳۰
در شکل زیر هم درخت رو می بینید که بر اساس الگوریتم بالا تشکیل شده

مرسی از توضیحتون
جالا اگه ارایه ها مرتب نبودن چی ؟ باید چی کار می کردیم ؟ از مرتبه چند می شد ؟

(۱۵ بهمن ۱۳۹۱ ۰۱:۰۴ ق.ظ)ana_12345 نوشته شده توسط:  مرسی از توضیحتون
جالا اگه ارایه ها مرتب نبودن چی ؟ باید چی کار می کردیم ؟ از مرتبه چند می شد ؟

احتمالا همون nlogn میشه

این مرتب سازی در زمان n log3 انجام میگیره که از مرتبه ی n هست... اگه کتاب مقسمی رو داشته باشین از صفحات ۲۸۸ تا ۲۹۰ اش رو یه دور بزنین دست گیرتون میشه ... اگه هم ندارین فقط میتونم بهتون بگم که با درخت برنده ها که برای مسابقات تورنمنت استفاده میشه (فکر کنم بهش درخت تورنمنت هم بگن) حل میشه...

دقیقا همین طوره. مرتبش میشه nlogk
اگه k تا آرایه مرتبو بخواهیم ادغام کنیم.