با سلام
بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1 چه مرتبه ای میتونه داشته باشه؟؟؟
باتشکر
به نظرم در حالتی که همه کلید ها رو داشته باشیم و بعد inorder کنیم که درست نیست چون در این صورت ارتفاعش لگاریتمی میشه.
اگر کلید ها رو یکی یکی درج کنیم که میشه n*h. که با توجه به اینکه ارتفاع درخت رو n گرفتید پس مرتبه زمانی ان به توان دو میشه.
سلام
اگه مقادیر کلیدها صحیح باشند که میشه باکت سورت زدو توی زمان n مرتبشون کرد و توی زمان n هم bst بسازیم
پس داریم تتای n+n که همون n میشه
اگه مقادیر کلیدها صحیح نباشه که کمتر از nlgn نمیشه قطعا مگر اینکه کلیدها از قبل مرتب باشن
منتظر به چالش کشیده شدن هستم
ممنونم به نظرم حرف شما درست تره. بله اگه بشه با مرتبه n مرتب کرد مرتبه زمانیش کمتر میشه.
ممنونم از جوابتون.
البته یک نکته رو بگم که ممنون میشم نظرتون رو بگید این روشی که دوستمون گفتند n میشه به نظر من روش غیر عملیه که حتما باید در مرحله اول همه داده ها موجود باشند که بتونیم با مرتبه n مرتبشون کنیم. درسته این حرف؟
من که هنوز متوجه نشدم؟؟
آیا کسی هست که بتونه بهتر توضیح بده؟
سلام
ساخت bst دو حالت داره
حالت اول اینه که تمام کلیدها رو در ابتدا داشته باشیم یعنی n تا کلید به ما بدن بگن باهاشون bst بساز
حالت دوم اینه که تمام کلیدها رو با هم ندن و به تدریج کلیدها سر و کلشون پیدا بشه (مثل خیلی از کنفرانسها و کلاسها و جلساتی که توی ایران برگزار میشه
)در حالت اول کلیدها رو در زمان (O(nlgnمرتب می کنیم ، خوب حالا باید با این کلیدای مرتب شده درخت بسازیم
صورت سوال گفته درخت به ارتفاع n-1 یعنی همون درخت مورب که هر سطحش فقط یه گره داره
کارمون سادس ، کلیدهای مرتب شده رو به ترتیب (صعودی یا نزولیش فرق نمیکنه) زیر هم درج می کنیم که میشه از مرتبه (teta(n
پس کل عملیات شد مرتب سازی + درج گره ها
یعنی (teta(nlgn + n که با روش ماکسیمم گیری برابر میشه با (teta(nlgn
البته اگر مقادیر کلیدها تمامشون اعداد صحیح باشن میشه از روش مرتب سازی bucket sort استفاده کرد که یه روش مرتب سازی غیرمقایسه ای هست و عمل مرتب سازی رو در زمان (teta(n انجام میده که در این صورت میشه bst رو توی زمان (teta(n ایجاد کرد
روش دوم یه کم پیچیدگی داره اجازه بدین بیشتر فکر کنم یا از دوستان بپرسم بعدا پاسخش رو ارسال کنم
طبق معمول منتظر به چالش کشیده شدن هستم
حالت دوم که کلیدها به تدریج از راه میرسند
باید n کلید رو توی bst درج کنیم عمل درج در bst بدین صورته که عنصر مورد نظر رو جستجو می کنیم اگر پیدا شد که نیاز به درج نیست ولی اگر پیدا نشد باید در همون نقطه ای که عمل جستجو به پایان رسیده یه گره جدید ایجاد کنیم و مقدار موردنظر رو توی اون گره قرار بدیم این عمل از مرتبه (O(lgn هست چون درحالت متوسط ارتفاع bst از مرتبه lgn هست و جستجو هم نهایتا به اندازه ارتفاع درخت ، گره ها رو بررسی میکنه
پس درج n گره در حالت متوسط (O(nlgn و در بدترین حالت که گره ها مرتب شده هستند و ارتفاع درخت n-1 هست برابر میشه با n^2
اما اینجا یه مشکلی هست گره ها به تدریج وارد میشن و ممکنه bst هر شکلی پیدا کنه ولی ما باید درختمون مورب باشه پس بعد از هر عمل درج ممکنه لازم باشه بعضی گره ها رو دوران بدیم یعنی (O(n تا دوران داریم که مرتبه اونا رو نمی دونم فقط می دونم هر عمل دوران سه تا اشاره گر رو تغییر میده
اگر هر عمل دوران رو از مرتبه (teta(1 فرض کنیم n تا دوران میشه از مرتبه (teta(n که چون لزوما تمام درج ها به دوران نیاز ندارن داریم (O(n
پس کل عملیات میشه (O(nlgn + n که همون (O(nlgn هست
دوستان اگه نظری درمورد دوران دارن خوشحال میشم راهنمایی کنن