چرا گزاره اول نا درسته؟! اگه ادغامشون کنیم، به اندازه n طول میشکه. حالت برای تبدیل به درخت avl مگه nlogn نباید طول بکشه؟!
سوال بالای صفحه!
![[تصویر: 243000_yge7e8up.jpg]](https://img.manesht.ir/243000_yge7e8up.jpg)
Sent from my SM-T210R using Tapatalk
(۰۹ بهمن ۱۳۹۲ ۰۸:۰۲ ب.ظ)hoomanab نوشته شده توسط: چرا گزاره اول نا درسته؟! اگه ادغامشون کنیم، به اندازه n طول میشکه. حالت برای تبدیل به درخت avl مگه nlogn نباید طول بکشه؟!
سوال بالای صفحه!
Sent from my SM-T210R using Tapatalk
من اینطوری فک میکنم:
ادغامشون که به اندازه n طول میکشه
از طرفی چون مرتب هستن، با میانه گیری میشه درخت رو ساخت که فک کنم به اندازه log n طول میکشه
پس در نهایت میشه از مرتبه O(n)
نمیدونم چقد استدلالم درست باشه
دوستان بیشتر واردن
ادغام ان
تبدیل به درخت بی اس تی هم با رابطه
(فقط وقتی ورودی مرتب باشه)
t(n)=2t(n\2)+1
میش ان
(۱۳ بهمن ۱۳۹۲ ۰۲:۱۸ ب.ظ)atharrashno نوشته شده توسط: پاسخ دودستمون کاملا درسته ادغام میشه او ان
و تبدیل به درخت بی اس تی هم با رابطه
(فقط وقتی ورودی مرتب باشه)
t(n)=t(n\2)+1
میشه لگاریتم ان
امکانش هست که بیشتر توضیح بدید؟! چطور با میانه گیری میشه logn?
(۱۳ بهمن ۱۳۹۲ ۰۵:۳۳ ب.ظ)hoomanab نوشته شده توسط:(13 بهمن ۱۳۹۲ ۰۲:۱۸ ب.ظ)atharrashno نوشته شده توسط: پاسخ دودستمون کاملا درسته ادغام میشه او ان
و تبدیل به درخت بی اس تی هم با رابطه
(فقط وقتی ورودی مرتب باشه)
t(n)=t(n\2)+1
میشه لگاریتم ان
امکانش هست که بیشتر توضیح بدید؟! چطور با میانه گیری میشه logn?
پیدا کردم میانه در ارایه مرتب او یک هست میانه را پیدا کردی میزاری ریشه ان دوم تا سمت راست ان دوم تا سمت چپ (البته یکی کمتر چون ریشه قبلا بردی بالا)
این کار تکرار کن میشه اون رابطه بالا
اون را بطه را مستر بزنید میشه ان
به نظرم این راه حل هم میتونه درست باشه
درخت جستجوی دودویی اول را به عنوان درخت اصلی در نظر میگیریم و بعد ریشه دو درخت دیگر را با عناصر درخت اولی مقایسه می کنیم و بعد جای عنصر ریشه درخت دوم و سوم را پیدا می کنیم و هر دو درخت را به ترتیب هر عنصر به درخت اول اضافه می کنیم و اگر درخت نامتوازن شد آن را متوازن می کنیم.
جستجوی ریشه که از مرتبه logn است و متوازن کردن درخت هم کمتر از n است که با این حساب مرتبه کلی الگوریتم برابر logn می شود
(۱۴ بهمن ۱۳۹۲ ۱۲:۵۲ ق.ظ)amir13 نوشته شده توسط: به نظرم این راه حل هم میتونه درست باشه
درخت جستجوی دودویی اول را به عنوان درخت اصلی در نظر میگیریم و بعد ریشه دو درخت دیگر را با عناصر درخت اولی مقایسه می کنیم و بعد جای عنصر ریشه درخت دوم و سوم را پیدا می کنیم و هر دو درخت را به ترتیب هر عنصر به درخت اول اضافه می کنیم و اگر درخت نامتوازن شد آن را متوازن می کنیم.
جستجوی ریشه که از مرتبه logn است و متوازن کردن درخت هم کمتر از n است که با این حساب مرتبه کلی الگوریتم برابر logn می شود
دوست من پیدا کردن ریشه در یک ارایه مرتب اگه منظور میانه باشه از مرتبه یک خواهد بود در ثانی شما با مقایسه ۳ میانه فقط به این نتیجه میرسی که چه تعداد عناصر از بزرگتیرین میانه دومین بزرگترین میانه و میانه اخر کوچیکتره
عمل اضافه کردن ان عنصر به درخت کم کم ان لگاریتم ان زمان میبره ما از محتوای دو ارایه دیگه خبر نداریم
راه حل
ادغام با مرتبه ان
رابطه بازگشتی که اصلاح شد با مرتبه ان
کلا با مرتبه ان
(۱۴ بهمن ۱۳۹۲ ۰۲:۱۶ ب.ظ)atharrashno نوشته شده توسط:من فکر کردم سه ارایه مرتب دودویی داریم که باید ادغام بشود ولی اگر سه ارایه فقط مرتب داشته باشیم مرتبه این الگوریتمی که در زیر نوشتم زیاد است.(14 بهمن ۱۳۹۲ ۱۲:۵۲ ق.ظ)amir13 نوشته شده توسط: به نظرم این راه حل هم میتونه درست باشه
درخت جستجوی دودویی اول را به عنوان درخت اصلی در نظر میگیریم و بعد ریشه دو درخت دیگر را با عناصر درخت اولی مقایسه می کنیم و بعد جای عنصر ریشه درخت دوم و سوم را پیدا می کنیم و هر دو درخت را به ترتیب هر عنصر به درخت اول اضافه می کنیم و اگر درخت نامتوازن شد آن را متوازن می کنیم.
جستجوی ریشه که از مرتبه logn است و متوازن کردن درخت هم کمتر از n است که با این حساب مرتبه کلی الگوریتم برابر logn می شود
دوست من پیدا کردن ریشه در یک ارایه مرتب اگه منظور میانه باشه از مرتبه یک خواهد بود در ثانی شما با مقایسه ۳ میانه فقط به این نتیجه میرسی که چه تعداد عناصر از بزرگتیرین میانه دومین بزرگترین میانه و میانه اخر کوچیکتره
عمل اضافه کردن ان عنصر به درخت کم کم ان لگاریتم ان زمان میبره ما از محتوای دو ارایه دیگه خبر نداریم
راه حل
ادغام با مرتبه ان
رابطه بازگشتی که اصلاح شد با مرتبه ان
کلا با مرتبه ان
پیدا کردن میانه که برابر n است ولی منطورم پیدا کردن میانه نبود.
محل اولین عنصر درخت دوم(بزرگترین عدد) را برای درج در درخت اول پیدا می کنیم. بقیه اعداد درخت دوم هم ،تک تک به عنوان گره ،بعد از عنصر اول اضافه می کنیم هر بارم متوازنش می کنیم. برای درخت های بعدی هم این کار را انجام می دهیم. اخر سرم یک درخت متوازن دودویی از ادغام سه تا درخت داریم
اینکه شما میگویی از مرتبه ان لگاریتم ان هست
در ضمن دوست من چیزی به عنوان ارایه دودویی نداریم درخت دودویی داریم
(اصلا چرا گیر دادی خودت گیچ کنی برادر یا خواهر من دم کنکور ریلکس باش)
(۱۴ بهمن ۱۳۹۲ ۰۸:۱۴ ب.ظ)atharrashno نوشته شده توسط: اینکه شما میگویی از مرتبه ان لگاریتم ان هست
در ضمن دوست من چیزی به عنوان ارایه دودویی نداریم درخت دودویی داریم
(اصلا چرا گیر دادی خودت گیچ کنی برادر یا خواهر من دم کنکور ریلکس باش)
اولا گفتم به نظرم این درست باشه که دیدم درست نیست
ارایه دودویی همون ارایه ای که اعضای ان به ترتیب درخت دودویی ذخیره شده باشد. مثلا عنصر اولش ریشه است و بعد عنصر دومش میشه گره سمت چپ و عنصر سومش میشه گره سمت راست و عنصر های بعدش به همین ترتیب. مرتبه ادغام این ارایه ها برابر با جستجوی عنصر ریشه سایر درخت ها در درخت اول و همینطور متوازن کردن هر گره جدید (اگر نیاز بود) را داریم. من بر این اساس گفتم logn
منبع فارسی که نداشت ان شا الله بعد کنکور منابع انگلیسیش ببینیم اولین بار بود میشنیدم
(۱۵ بهمن ۱۳۹۲ ۰۹:۱۳ ق.ظ)atharrashno نوشته شده توسط: منبع فارسی که نداشت ان شا الله بعد کنکور منابع انگلیسیش ببینیم اولین بار بود میشنیدم
همه منابع گفتن برای اینکه یک درخت در ارایه ذخیره کنیم باید اندیس ها را به این شکل قرار بدیم.
اما اگر درخت کامل نباشه مصرف حافظه زیاد میشه که بهتره از ارایه استفاده نکنیم.