سلام
ساخت bst دو حالت داره
حالت اول اینه که تمام کلیدها رو در ابتدا داشته باشیم یعنی n تا کلید به ما بدن بگن باهاشون bst بساز
حالت دوم اینه که تمام کلیدها رو با هم ندن و به تدریج کلیدها سر و کلشون پیدا بشه (مثل خیلی از کنفرانسها و کلاسها و جلساتی که توی ایران برگزار میشه
![Wink Wink](images/smilies/wink.gif)
)
در حالت اول کلیدها رو در زمان (O(nlgnمرتب می کنیم ، خوب حالا باید با این کلیدای مرتب شده درخت بسازیم
صورت سوال گفته درخت به ارتفاع n-1 یعنی همون درخت مورب که هر سطحش فقط یه گره داره
کارمون سادس ، کلیدهای مرتب شده رو به ترتیب (صعودی یا نزولیش فرق نمیکنه) زیر هم درج می کنیم که میشه از مرتبه (teta(n
پس کل عملیات شد مرتب سازی + درج گره ها
یعنی (teta(nlgn + n که با روش ماکسیمم گیری برابر میشه با (teta(nlgn
البته اگر مقادیر کلیدها تمامشون اعداد صحیح باشن میشه از روش مرتب سازی bucket sort استفاده کرد که یه روش مرتب سازی غیرمقایسه ای هست و عمل مرتب سازی رو در زمان (teta(n انجام میده که در این صورت میشه bst رو توی زمان (teta(n ایجاد کرد
روش دوم یه کم پیچیدگی داره اجازه بدین بیشتر فکر کنم یا از دوستان بپرسم بعدا پاسخش رو ارسال کنم
طبق معمول منتظر به چالش کشیده شدن هستم